RECORD
On the generalized Tur\'an problem for odd cycles
Combinatorics · Submitted 22 Sep 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim As an extension of this result for longer cycles, we prove that for each odd $k\geq 7$, the balanced blow-up of $C_k$ (uniquely) maximises the number of $k$-cycles among $C_{k-2}$-free graphs on $n$ vertices, as long as $n$ is sufficiently large.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In 1984, Erd\H{o}s conjectured that the number of pentagons in any triangle-free graph on $n$ vertices is at most $(n/5)^5$, which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami, Hladk\'y, Kr\'al', Norine and Razborov. As an extension of this result for longer cycles, we prove that for each odd $k\geq 7$, the balanced blow-up of $C_k$ (uniquely) maximises the number of $k$-cycles among $C_{k-2}$-free graphs on $n$ vertices, as long as $n$ is sufficiently large. We also show that this is no longer true if $n$ is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd $k\geq 7$, the balanced blow-up of $C_k$ maximises the number of $k$-cycles among graphs with a given number of vertices and no odd cycles of length less than $k$. We further show that if $k$ and $\ell$ are odd and $k$ is sufficiently large compared to $\ell$, then the balanced blow-up of $C_{\ell+2}$ does not asymptotically maximise the number of $k$-cycles among $C_{\ell}$-free graphs on $n$ vertices. This disproves a conjecture of Grzesik and Kielak.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In 1984, Erd\H{o}s conjectured that the number of pentagons in any triangle-free graph on $n$ vertices is at most $(n/5)^5$, which is sharp by the balanced blow-up of a pentagon. | background 1.00 | 0.03 | 0.03 | asserted 0.56 |
| s1 | This was proved by Grzesik, and independently by Hatami, Hladk\'y, Kr\'al', Norine and Razborov. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s2 | As an extension of this result for longer cycles, we prove that for each odd $k\geq 7$, the balanced blow-up of $C_k$ (uniquely) maximises the number of $k$-cycles among $C_{k-2}$-free graphs on $n$ vertices, as long as $n$ is sufficiently large. | result 0.86 | 0.96 | 0.84 | asserted 1.00 |
| s3 | We also show that this is no longer true if $n$ is not assumed to be sufficiently large. | result 0.61 | 0.90 | 0.06 | asserted 1.00 |
| s4 | Our result strengthens results of Grzesik and Kielak who proved that for each odd $k\geq 7$, the balanced blow-up of $C_k$ maximises the number of $k$-cycles among graphs with a given number of vertices and no odd cycles of length less than $k$. | result 0.41 | 0.71 | 0.16 | asserted 1.00 |
| s5 | We further show that if $k$ and $\ell$ are odd and $k$ is sufficiently large compared to $\ell$, then the balanced blow-up of $C_{\ell+2}$ does not asymptotically maximise the number of $k$-cycles among $C_{\ell}$-free graphs on $n$ vertices. | result 0.98 | 0.96 | 0.12 | asserted 1.00 |
| s6 | This disproves a conjecture of Grzesik and Kielak. | interpretation 0.80 | 0.83 | 0.16 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In 1984, Erd\H{o}s conjectured that the number of pentagons in any triangle-free graph on $n$ vertices is at most $(n/5)^5$, which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami, Hladk\'y, Kr\'al', Norine and Razborov. As an extension of this result for longer cycles, we prove that for each odd $k\geq 7$, the balanced blow-up of $C_k$ (uniquely) maximises the number of $k$-cycles among $C_{k-2}$-free graphs on $n$ vertices, as long as $n$ is sufficiently large. We also show that this is no longer true if $n$ is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd $k\geq 7$, the balanced blow-up of $C_k$ maximises the number of $k$-cycles among graphs with a given number of vertices and no odd cycles of length less than $k$. We further show that if $k$ and $\ell$ are odd and $k$ is sufficiently large compared to $\ell$, then the balanced blow-up of $C_{\ell+2}$ does not asymptotically maximise the number of $k$-cycles among $C_{\ell}$-free graphs on $n$ vertices. This disproves a conjecture of Grzesik and Kielak.
Human review
How the literature uses it
2 arXiv papers cite this in 2 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 1 paper
-
More recently, Alon and Shikhelman [ref] systematically studied $(n, H_1, H_2)$ for other graphs $H_1$, and there have been a number of results in this direction (see e.g. [ref] ).
Generalized Ramsey--Tur\'an density for cliques · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.