On the maximum number of r-cliques in graphs free of complete r-partite subgraphs

2024/02/26 by Balogh, József, Jiang, Suyun, Luo, Haoran · 3 citations
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2402.16818

Abstract

We estimate the maximum possible number of cliques of size r in an n-vertex graph free of a fixed complete r-partite graph K_{s1, s2, …, sr}. By viewing every r-clique as a hyperedge, the upper bound on the Turán number of the complete r-partite hypergraphs gives the upper bound O(n^r - 1/∏_i=1^r-1s_i). We improve this to o(n^r - 1/∏_i=1^r-1s_i). The main tool in our proof is the graph removal lemma. We also provide several lower bound constructions.

Cited by

• The Exponential Hyper-Zagreb Indices and Structural Properties of Trees and Bipartite Graphs
• The maximum number of triangles in K_1,s,t-free graphs
• Generalized Turan number with given size

Related

• The number of cliques in hypergraphs with forbidden subgraphs
• The maximum number of cliques in disjoint copies of graphs
• The typical structure of graphs with no large cliques
• The maximum number of cliques in graphs without long cycles
• Maximum cliques in a graph without disjoint given subgraph