Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 51 min ago
PreprintarXiv licencearXiv

The number of C4-free graphs

  • Tianchi Yang
Open at sourcePDFDOICite

Abstract

Erdős, Frankl and Rödl showed that the number of graphs on n vertices with no copy of a non-bipartite graph H is 2(1+o(1))ex(n,H), whereas Morris and Saxton showed that this fails for C6. Answering a question of Erdős, we prove that the number of C4-free graphs on n vertices is 2(1+o(1))ex(n,C4). The proof combines a modified hypergraph container method that treats pairs of vertices with large codegree separately, with a new bound on the number of matchings in a graph.

Related

  1. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
    Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. The chromatic number of {ISK4, textupdiamond}-free graphs
    Qing Cui, Kaiyang Lan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A sharp bound on the binding number of Kk-free graphs and the Brandt conjecture
    Jifu Lin, Heng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The Exact Number of Pentagons in Book-Free Graphs
    Wentao Hu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yang2026number,
  title = {{The number of $C_4$-free graphs}},
  author = {Tianchi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.39595},
  eprint = {2610.39595},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39595},
}
RIS
TY  - UNPB
TI  - The number of C_4-free graphs
AU  - Tianchi Yang
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.39595
UR  - https://arxiv.org/abs/2610.39595
AB  - Erdős, Frankl and Rödl showed that the number of graphs on n vertices with no copy of a non-bipartite graph H is 2^(1+o(1))ex(n,H), whereas Morris and Saxton showed that this fails for C_6. Answering a question of Erdős, we prove that the number of C_4-free graphs on n vertices is 2^(1+o(1))ex(n,C_4). The proof combines a modified hypergraph container method that treats pairs of vertices with large codegree separately, with a new bound on the number of matchings in a graph.
ER  -