Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 9 min ago
PreprintarXiv licencearXiv

Maximizing Kr + Ir in graphs with fixed edge density

  • József Balogh
  • Andrzej Grzesik
  • Bernard Lidický
  • Theodore Molla
  • Dhruv Mubayi
  • Jan Volec
Open at sourcePDFDOICite

Abstract

For every integer r≥4, and ρ∈ [0,1], we asymptotically determine the maximum proportion of r-element sets of vertices that induce either a clique or an independent set in a large graph with density ρ. This generalizes a result of Olpp for r=3. After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.

Related

  1. Maximizing Crossword Grids with a Fixed Minimum Clue Length
    Kelly Isham, Abigail Schnitzer
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion
    Zeru Zhu, Marco Gamarra, Ji Liu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  3. Maximizing the number of cliques in Kr+1-free graphs with forbidden properties
    Aleyah Dawkins, Rachel Kirsch
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Trace-minimal graphs maximizing the number of spanning trees
    Pablo Romero, Louis Petingi
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The Fixed-q Edge Limit of the q-Krawtchouk Ensemble
    Pavel Nikitin
    arXivPreprintarXiv licenceFull textAnalysis & PDEsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{balogh2026maximizing,
  title = {{Maximizing $K_r + I_r$ in graphs with fixed edge density}},
  author = {József Balogh and Andrzej Grzesik and Bernard Lidický and Theodore Molla and Dhruv Mubayi and Jan Volec},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08194},
  eprint = {2609.08194},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08194},
}
RIS
TY  - UNPB
TI  - Maximizing K_r + I_r in graphs with fixed edge density
AU  - József Balogh
AU  - Andrzej Grzesik
AU  - Bernard Lidický
AU  - Theodore Molla
AU  - Dhruv Mubayi
AU  - Jan Volec
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08194
UR  - https://arxiv.org/abs/2609.08194
AB  - For every integer r≥4, and ρ∈ [0,1], we asymptotically determine the maximum proportion of r-element sets of vertices that induce either a clique or an independent set in a large graph with density ρ. This generalizes a result of Olpp for r=3. After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.
ER  -