Skip to content
DraconiticResearch
Search Sources API
194,216 studies31 sourcesUpdated 17 min ago
PreprintarXiv licencearXiv

Tight connectivity and shadow densities in generalized Erdős--Rogers problems

  • Lulu Dai
  • Qizhong Lin
Open at sourcePDFDOICite

Abstract

Let F and G be r-uniform hypergraphs, and let fF,G(n) be the largest integer m such that every n-vertex G-free r-graph contains an induced F-free subgraph on m vertices. We prove that, for r≥3 and 2≤ k≤ r−1, if F is nonempty, G is k-tightly connected, and there is no homomorphism from G to F (that is, Gnot→ F), then fF,G(n)≤ C(log n)βF(k), βF(k)= max∅≠ P⊆∂kF e(P)/(v(P)−1). The case r=3 of our result resolves a conjecture of He and Nie. As a consequence, we obtain the Ramsey lower bound r(G,Knr)≥2Ω(n(r−1)/binom rk) for every k-tightly connected non-r-partite r-graph G. This extends a result of Conlon, Fox, Gunby, He, Mubayi, Suk, Verstraëte and Yu from the 3-uniform setting.

Related

  1. On Densities in the Erdős-Falconer Distance Problems over the Integers
    Eyvindur Ari Palsson, Jian-An Wang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  2. Symmetry Regularization of 1D Generalized Coulomb Problems
    Zhanqiang Bai, Junwei Ma, Guowu Meng
    arXivPreprintCC BY 4.0Full textMathematical physicsarXiv
  3. Stability Analysis of Generalized Multi-Source Weber Problems
    N. H. Hai, V. S. T. Long, N. M. Nam +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Inertial parameterized Douglas-Rachford for generalized DC programming problems
    Avinash Dixit, Pankaj Gautam, Sorin-Mihai Grad
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Generalized Turán problems for shorter even cycles
    Zhen Liu, Chuanshu Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dai2026tight,
  title = {{Tight connectivity and shadow densities in generalized Erdős--Rogers problems}},
  author = {Lulu Dai and Qizhong Lin},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2607.00732},
  eprint = {2607.00732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.00732},
}
RIS
TY  - UNPB
TI  - Tight connectivity and shadow densities in generalized Erdős--Rogers problems
AU  - Lulu Dai
AU  - Qizhong Lin
PY  - 2026
DA  - 2026/08/28
PB  - arXiv
DO  - 10.48550/arxiv.2607.00732
UR  - https://arxiv.org/abs/2607.00732
AB  - Let F and G be r-uniform hypergraphs, and let f_F,G(n) be the largest integer m such that every n-vertex G-free r-graph contains an induced F-free subgraph on m vertices. We prove that, for r≥3 and 2≤ k≤ r−1, if F is nonempty, G is k-tightly connected, and there is no homomorphism from G to F (that is, Gnot→ F), then f_F,G(n)≤ C(log n)^β_F^(k), β_F^(k)= max_∅≠ P⊆∂_kF e(P)/(v(P)−1). The case r=3 of our result resolves a conjecture of He and Nie. As a consequence, we obtain the Ramsey lower bound r(G,K_n^r)≥2^Ω(n^(r−1)/binom rk) for every k-tightly connected non-r-partite r-graph G. This extends a result of Conlon, Fox, Gunby, He, Mubayi, Suk, Verstraëte and Yu from the 3-uniform setting.
ER  -