Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 1 h ago
PreprintCC BY 4.0arXiv

Sharp asymmetric vertex-Ramsey properties of graphs

  • Robert Hancock
  • Joseph Hyde
  • Mael Kupperschmitt
Open at sourcePDFDOICite

Abstract

In 1992, Łuczak, Ruciński and Voigt showed that for any graph H, a parameter m1(H) - called the 1-density - governs the threshold at which the binomial random graph G(n,p) inherits the vertex-Ramsey property. In 2000, Friedgut and Krivelevich showed this threshold is sharp for graphs satisfying a natural balancedness condition. In 1996, Kreuter showed that for any graphs H1, …, Hr with m1(H1) ≥ ⋯ ≥ m1(Hr), a parameter dependent only on H1 and H2 governs the threshold at which G(n,p) inherits the `asymmetric' vertex-Ramsey property. We prove this threshold is sharp for graphs respecting natural balancedness conditions, including in the analogous hypergraph setting.

Related

  1. Non-isomorphic graphs have distinct vertex-Ramsey classes
    Maria Axenovich, Patrick Schmitteckert
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Sharp Bounds on Torsional Rigidity of Metric Graphs with Signed Delta-Vertex Strengths
    Sedef Özcan
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  3. Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
    Trung Chau, Tran Quang Hoa, Dang Thi Kieu Uyen
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Sharp vertex connectivity of the Markoff graphs modulo p
    Jie Ma, Mengxi Yang, Zichen Yang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Ramsey properties of maximal (outer)planar graphs
    Adriana Baldacchino, Yair Caro, Xandru Mifsud
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hancock2026sharp,
  title = {{Sharp asymmetric vertex-Ramsey properties of graphs}},
  author = {Robert Hancock and Joseph Hyde and Mael Kupperschmitt},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.32677},
  eprint = {2610.32677},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.32677},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Sharp asymmetric vertex-Ramsey properties of graphs
AU  - Robert Hancock
AU  - Joseph Hyde
AU  - Mael Kupperschmitt
PY  - 2026
DA  - 2026/10/23
PB  - arXiv
DO  - 10.48550/arxiv.2610.32677
UR  - https://arxiv.org/abs/2610.32677
AB  - In 1992, Łuczak, Ruciński and Voigt showed that for any graph H, a parameter m_1(H) - called the 1-density - governs the threshold at which the binomial random graph G(n,p) inherits the vertex-Ramsey property. In 2000, Friedgut and Krivelevich showed this threshold is sharp for graphs satisfying a natural balancedness condition. In 1996, Kreuter showed that for any graphs H_1, …, H_r with m_1(H_1) ≥ ⋯ ≥ m_1(H_r), a parameter dependent only on H_1 and H_2 governs the threshold at which G(n,p) inherits the `asymmetric' vertex-Ramsey property. We prove this threshold is sharp for graphs respecting natural balancedness conditions, including in the analogous hypergraph setting.
ER  -