The next case of Andrásfai's conjecture

2023/08/11 by Tomasz Łuczak, Łuczak, Tomasz, Joanna Polcyn +3 · 1 citation
Computer Science · Mathematics · #05C35 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2308.06070

openalex publication_date 2023/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let ex(n,s) denote the maximum number of edges in a triangle-free graph on n vertices which contains no independent sets larger than s. The behaviour of ex(n,s) was first studied by Andrásfai, who conjectured that for s>n/3 this function is determined by appropriately chosen blow-ups of so called Andrásfai graphs. Moreover, he proved ex(n, s)=n²-4ns+5s² for s/n∈ [2/5, 1/2] and in earlier work we obtained ex(n, s)=3n²-15ns+20s² for s/n∈ [3/8, 2/5]. Here we make the next step in the quest to settle Andrásfai's conjecture by proving ex(n, s)=6n²-32ns+44s² for s/n∈ [4/11, 3/8].

Cited by

• Ramsey with purple edges

Related

• Extremal numbers of disjoint triangles in r-partite graphs
• On extremal numbers of the triangle plus the four-cycle
• Upper bounds on the extremal number of the 4-cycle
• The maximum number of triangles in F_k-free graphs
• Andrásfai--Erdős--Sós theorem for the generalized triangle