The maximum number of cliques in graphs with bounded odd circumference

Zequn Lv Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Department of Mathematical Sciences, Tsinghua University. Ervin Győri Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Zhen He Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Department of Mathematical Sciences, Tsinghua University. Nika Salia Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Chuanqi Xiao Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Department of Computer Science and Information Theory, Budapest University of Technology and Economics. Xiutao Zhu Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences. Department of Mathematics, Nanjing University.

Abstract

In this work, we give the sharp upper bound for the number of cliques in graphs with bounded odd circumferences. This generalized Turán-type result is an extension of the celebrated Erdős and Gallai theorem and a strengthening of Luo’s recent result. The same bound for graphs with bounded even circumferences is a trivial application of the theorem of Li and Ning.

1 Introduction

A central topic of extremal combinatorics is to investigate sufficient conditions for the appearance of given substructures. In particular, for a given graph $H$ and a set of graph $\mathcal{F}$ , the generalized Turán number ${\rm ex}(n,H,\mathcal{F})$ denotes the maximum number of copies of $H$ in a graph on $n$ vertices containing no $F$ as a subgraph, for every $F\in\mathcal{F}$ . In 1959, Erdős and Gallai [1] determined the maximum number of edges in a graph with a small circumference. For every integers $n$ and $k$ such that $n\geq k\geq 3$ , they proved

{\rm ex}(n,K_{2},\mathcal{C}_{\geq k})\leq\frac{(k-1)(n-1)}{2},

where $K_{k}$ denotes the complete graph with $k$ vertices and $\mathcal{C}_{\geq k}$ denotes the family of cycles of length at least $k$ . The bound is sharp for every $n$ congruent to one modulo $k-2$ . The equality is attained by graphs with $\frac{n-1}{k-2}$ maximal $2$ -connected blocks each isomorphic to $K_{k-1}$ . Recently Li and Ning [2] proved that in order to obtain the same upper-bound it is enough to forbid only long even cycles

{\rm ex}(n,K_{2},\mathcal{C}^{even}_{\geq 2k})\leq\frac{(2k-1)(n-1)}{2},

(1)

where $\mathcal{C}^{even}_{\geq 2k}$ denotes the family of even cycles of length at least $2k$ , that is $\{C_{2k},C_{2k+2},\dots\}$ . We also denote the family of odd cycles of length at least $2k+1$ by $\mathcal{C}^{odd}_{\geq 2k+1}:=\{C_{2k+1},C_{2k+3},\dots\}$ .

Note that by considering the complete balanced bipartite graph, one can not achieve a linear bound for edges in graphs with a small odd circumference. On the other hand, Voss and Zuluga [5] proved that every $2$ -connected graph $G$ with minimum degree at least $k\geq 3$ , with at least $2k+1$ vertices, contains an even cycle of length at least $2k$ . Even more, if $G$ is not bipartite then it contains an odd cycle of length at least $2k-1$ .

The celebrated Erdős and Gallai theorem is well studied and well understood. There are numerous papers strengthening, generalizing, and extending for different classes of graphs. Recently Luo [3] proved

{\rm ex}(n,K_{r},\mathcal{C}_{\geq k})\leq\frac{(n-1)}{k-2}\binom{k-1}{r},

(2)

for all $n\geq k\geq 4$ . This bound is a great tool for obtaining results in hypergraph theory. In order to highlight its significance, that bound was consequently reproved with different methods multiple times [4, 6]. In this paper, we strengthen Luo’s theorem. In particular, we obtain the tight same bounds for graphs with bounded odd circumferences. On the other hand, the result for graphs with bounded even circumference is trivial after applying Equation 1 and the following easy corollary of Equation 2,

{\rm ex}(n,K_{r},P_{k+1})\leq\frac{n}{k}\binom{k}{r},

where $P_{k+1}$ denotes the path of length $k$ . Since the graph $G$ does not contain a cycle of length $2k$ , for each vertex the neighborhood contains no path of length $2k-2$ . In particular, for all $r\geq 3$ we have

{\rm ex}(n,K_{r},\mathcal{C}^{even}_{\geq 2k})\leq\frac{1}{r}\sum_{v}\frac{d(v)}{(2k-2)}\binom{2k-2}{r-1}\leq\frac{1}{r}\frac{ex(n,K_{2},\mathcal{C}^{even}_{\geq 2k})}{(k-1)}\binom{2k-2}{r-1}\leq\frac{n-1}{2k-2}\binom{2k-1}{r}.

For graphs with small odd circumferences, we have the following theorem.

Theorem 1.

For integers $n,k,r$ satisfying $n\geq 2k\geq r$ and $k\geq 6$ ,

{\rm ex}(n,K_{r},\mathcal{C}^{odd}_{\geq 2k+1})\leq\frac{n-1}{2k-1}\binom{2k}{r}.

The equality holds if and only if $n-1$ is divisible by $2k-1$ for a connected $n$ -vertex graph which consists of $\frac{n-1}{2k-1}$ maximal $2$ -connected blocks isomorphic to $K_{2k}$ .

It is interesting to ask for which integers and for which congruence classes the same phenomenon still holds. In this direction, we would like to rise a modest conjecture.

Conjecture 1.

For an integer $k\geq 2$ and a sufficiently large $n$ . Let $G$ be an $n$ vertex $C_{3\ell+1}$ -free graph for every integer $\ell\geq k$ . Then for every $r\geq 2$ , the number of cliques of size $r$ in $G$ is at most

\frac{n-1}{3k-1}\binom{3k}{r}.

The equality holds if and only if $n-1$ is divisible by $3k-1$ for a connected $n$ -vertex graph which consists of $\frac{n-1}{3k-1}$ maximal $2$ -connected blocks isomorphic to $K_{3k}$ .

Moreover, we would like to propose the following conjecture. Let $p$ be a prime number and $\mathcal{C}_{\geq p}^{prime}$ be the family of all cycles of length at least $p$ .

Conjecture 2.

For integers $n$ , $r$ and a prime $p$ satisfying $r<p$ , we have

ex(n,K_{r},\mathcal{C}_{\geq p}^{prime})\leq\frac{n-1}{p-2}\binom{p-1}{r}.

The equality holds if and only if $n-1$ is divisible by $p-2$ , for a connected $n$ -vertex graph which consists of $\frac{n-1}{p-2}$ maximal $2$ -connected blocks isomorphic to $K_{p-1}$ .

2 Proof of the main result

Proof.

We prove Theorem 1 by induction on the number of vertices of the graph. The base cases for $n\leq 2k$ are trivial. Let $G$ be a graph on $n$ vertices where $n>2k$ . We assume that every $\mathcal{C}^{odd}_{\geq 2k+1}$ -free graph on $m$ vertices, for some $m<n$ , contains at most $\frac{m-1}{2k-1}\binom{2k}{r}$ copies of $K_{r}$ and the equality is achieved for the class of graphs described in the statement of the theorem.

If $\delta(G)$ , the minimum degree of $G$ , is at most $k+2$ then we are done by the induction hypothesis

K_{r}(G)\leq K_{r}(G[V(G)\setminus\{v\}])+\binom{k+2}{r-1}\leq\frac{n-2}{2k-1}\binom{2k}{r}+\binom{k+2}{r-1}<\frac{n-1}{2k-1}\binom{2k}{r},

since $k\geq 6$ . From here, we may assume $G$ is a graph with $\delta(G)>k+2$ , and each edge of $G$ is in a copy of $K_{r}$ .

Let $v_{1}v_{2}v_{3}\dots v_{m}$ be a longest path of $G$ such that $v_{1}$ is adjacent to $v_{t}$ and $t$ is the maximum possible among the longest paths.

Claim 2.

If $t\leq 2k$ , then $v_{t}$ is a cut vertex.

Proof.

Consider a family $\mathcal{P}$ contains all longest paths of $G$ on the vertex set $\{v_{1},v_{2},v_{3},\dots,v_{m}\}$ such that $v_{t}v_{t+1}\dots v_{m}$ is a sub-path of them. Let $T_{1}$ be the set of terminal vertices, excluding $v_{m}$ , of paths from $\mathcal{P}$ . If $T_{1}=\{v_{1},v_{2},\dots,v_{t-1}\}$ , then by the maximality of $t$ , the vertex $v_{t}$ is a cut vertex. Let the path $u_{1}u_{2}\cdots u_{t-1}u_{t}v_{t+1}\cdots v_{m}$ be a path from $\mathcal{P}$ such that $u_{r}\in T_{1}$ and $u_{r+1}\notin T_{1}$ minimizing $r$ . Note that $u_{t}=v_{t}$ and $\{v_{1},v_{2},\dots,v_{t}\}=\{u_{1},u_{2},\dots,u_{t}\}$ .

By the minimality of $r$ , the vertex $u_{1}$ is not adjacent to two consecutive vertices from $\{u_{r+1},u_{r+2},\dots,v_{t}\}$ . Since if $v_{1}$ is adjacent to $u_{i}$ and $u_{i+1}$ for $r+1\leq i\leq t$ , then

u_{2}u_{3}\cdots u_{r}u_{r+1}\cdots u_{i}u_{1}u_{i+1}\cdots u_{t}v_{t+1}\cdots v_{m}

forms a path from $\mathcal{P}$ , contradicting the minimality of $r$ .

Note that $u_{1}$ is not adjacent to vertices $u_{r+2},u_{r+3},\dots,u_{2r+1}$ . Otherwise, suppose $u_{1}$ is adjacent to $u_{i}$ for $r+2\leq i\leq 2r+1$ , then we get a path from $\mathcal{P}$

u_{i-1}u_{i-2}\dots u_{r+1}u_{r}\dots u_{1}u_{i}u_{i+1}\dots u_{t}v_{t+1}\dots v_{m},

contradicting the minimality of $r$ since $u_{r+1}\notin T_{1}$ .

Finally we have $d(u_{1})\leq(r-1)+\frac{t-(2r+1)+1}{2}=\frac{t-2}{2}<k$ , a contradiction. ∎

Claim 3.

We have $t\leq 2k$ .

Proof.

Suppose otherwise, $t>2k$ . Let $C$ denote the cycle $v_{1}v_{2}\dots v_{t}v_{1}$ . Since $G$ is $\mathcal{C}^{odd}_{\geq 2k+1}$ -free, $t$ is even and vertices $v_{t-3}$ and $v_{t-2}$ have no common neighbors in $G[V(G)\setminus V(C)]$ . On the other hand, since every edge is in a $K_{r}$ there is a vertex $v_{l}$ incident with both $v_{t-3}$ and $v_{t-2}$ . Let us denote $c:=t-2k$ . Since $G$ is $\mathcal{C}^{odd}_{\geq 2k+1}$ -free, $c-1\leq l\leq 2k-4$ holds. We take indices modulo $t$ in this claim.

There is no $i$ such that $v_{i}$ is adjacent with $v_{t-1}$ and $v_{i+1}$ is adjacent with $v_{1}$ . Since otherwise, the following cycle is odd with a length greater than $2k$ ,

v_{1}v_{2}\dots v_{i}v_{t-1}v_{t-2}\dots v_{i+1}v_{1}.

Note that, since $v_{t-1},v_{1}\in T_{1}$ and from maximality of $t$ , we have $N(v_{1}),N(v_{t-1})\subseteq V(C)$ . Therefore we have $N(v_{1})\cap N^{+}(v_{t-1})=\emptyset$ . Where $N^{+}(v_{t-1})$ denotes the following set $\{v_{i+1}:v_{i}\in N^{+}(v_{t-1})\}$ .

There is no such $i$ such that both $l<i<l+c-2$ and $v_{1}v_{i}$ is an edge of $G$ hold. Since otherwise, one of the following cycles is an odd cycle longer than $2k$ ,

v_{1}v_{2}\dots v_{l}v_{t-2}v_{t-3}\dots v_{i}v_{1}\mbox{~{}or~{}}v_{1}v_{2}\dots v_{l}v_{t-3}v_{t-4}\dots v_{i}v_{1}.

Similarly, there is no $i$ such that $l<i<l+c$ and $v_{t-1}v_{i}$ is an edge of $G$ . Finally, we have

N(v_{1})\cap\{v_{l+2},\dots,v_{l+c-3}\}=\emptyset.

Also, we have

N(v_{1})\cap N^{+}(v_{t-1})=\emptyset

and

N^{+}(v_{t-1})\cap\{v_{l+2},\dots,v_{l+c-3}\}=\emptyset.

Hence, we get

\left|{N(v_{1})}\right|\leq\left|{\{v_{1},v_{2},\dots,v_{2k+c}\}\setminus N^{+}(v_{t-1})\setminus\{v_{l+2},\dots,v_{l+c-3}\}}\right|\leq 2k+c-(k+3)-(c-5)<\delta(G),

a contradiction. ∎

From Claims 2 and 3, $G$ contains a $2$ -connected block of size at most $2k$ . By the induction hypothesis, we see that graph $G$ contains at most $\frac{n-1}{2k-1}\binom{2k}{r}$ edges. The equality is achieved if and only if every maximal $2$ -connected component of $G$ is isomorphic to $K_{2k}$ and the number of the maximal $2$ -connected components is $\frac{n-1}{2k-1}$ . ∎

3 Acknowledgements

The research of Győri is partially supported by the National Research, Development and Innovation Office – NKFIH, grant K116769, K132696 and SNN117879. The research of Salia was supported by the Institute for Basic Science (IBS-R029-C4). The research of Zhu was supported by program B for an outstanding Ph.D. candidate at Nanjing University.

References

[1] Paul Erdős and Tibor Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10(3-4):337–356, 1959.
[2] Binlong Li and Bo Ning. Eigenvalues and cycles of consecutive lengths. arXiv preprint arXiv:2110.05670, 2021.
[3] Ruth Luo. The maximum number of cliques in graphs without long cycles. Journal of Combinatorial Theory, Series B, 128:219–226, 2018.
[4] Bo Ning and Xing Peng. Extensions of the Erdős–Gallai theorem and Luo’s theorem. Combinatorics, Probability and Computing, 29(1):128–136, 2020.
[5] HJ Voss and C. Zuluga. Maximale gerade und ungerade kreise in graphen i. Wiss. Z. Tech. Hochschule Ilmenau, 4:57–70, 1977.
[6] Xiutao Zhu, Ervin Győri, Zhen He, Zequn Lv, Nika Salia, and Chuanqi Xiao. Stability version of dirac’s theorem and its applications for generalized tur $\backslash$ ’an problems. arXiv preprint arXiv:2207.12465, 2022.

E-mail addresses:
E. Győri: [email protected]
Z. He: [email protected]
J. Lv: [email protected]
N. Salia: [email protected]
C. Xiao: [email protected]
X. Zhu: [email protected]