The Maximum Number of Cliques in Graphs without Long Cycles

The Erdős-Gallai Theorem states that for \(k\geq 3\) every graph on \(n\) vertices with more than \((k-1)(n-1)/2\) edges contains a cycle of length at least \(k\). Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples \(H_{n,k,t}\) and \(H_{n,k,2}\). In this talk, the speaker generalizes the result of Kopylov to bound the number of \(s\)-cliques in a graph with circumference less than \(k\). Furthermore, the speaker shows that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, the speaker obtains the extremal number of \(s\)-cliques in a graph with no path on \(k\)-vertices.

Event Topic

Discrete Applied Math Seminar