The maximum number of triangles in K_1,s,t-free graphs

2025/08/14 by Calbet, Asier, Goenka, Ritesh
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.10611

Abstract

We consider the following generalized Turán problem: For 2 ≤ s ≤ t, what is the maximum number of triangles in a K_1,s,t-free graph on n vertices? The previously best known lower and upper bounds are Ω(n²) and o(n^3-1/s), respectively. To the best of our knowledge, all known proofs of the upper bound use the triangle removal lemma. We give a new elementary proof that avoids the use of the triangle removal lemma and improves the upper bound to O(n^3-1/s(log n)^-1+1/s).

Citations

• Survey of generalized Turán problems -- counting subgraphs
• The number of cliques in hypergraphs with forbidden subgraphs
• On the maximum number of r-cliques in graphs free of complete r-partite subgraphs
• A survey of Turán problems for expansions
• A new proof of the graph removal lemma
• On extremal problems of graphs and generalized graphs

Related

• The maximum number of triangles in F_k-free graphs
• A note on the maximum number of triangles in a C₅-free graph
• Turán number of disjoint triangles in 4-partite graphs
• Triangles in C₅-free graphs and Hypergraphs of Girth Six
• Some extremal results on K_s,t-free graphs