On the Number of Pentagons in Triangle-Free Graphs

Details On the Number of Pentagons in Triangle-Free Graphs On the Number of Pentagons in Triangle-Free Graphs

2011-02-08

arxiv.org/abs/1102.1634v2

Mathematics

Combinatorics

13 pages

Scientific paper

Using the formalism of flag algebras, we prove that the maximal number of copies of pentagons in a triangle-free graph with 5n+a vertices (0\leq a\leq 4) is n^{5-a}(n+1)^a, and we show that the set of extremal graphs for this problem consists precisely of almost balanced blow-ups of a single pentagon. This settles a conjecture made by Erdos in 1984. For the transition from an asymptotic version of our result to the exact one, we introduce a new technique based on replacing finite objects by their infinite blow-ups which we expect to have further applications.

Affiliated with

Also associated with

No associations

Rating

On the Number of Pentagons in Triangle-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Number of Pentagons in Triangle-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Number of Pentagons in Triangle-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502729