Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 55 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

Generalized Ramsey Numbers via Conflict-Free Hypergraph Matchings

  • Natasha Morrison
  • Andrew Lane
Open at sourcePDFDOICite

Abstract

Given graphs $G, H$ and an integer q ≥ 2, the generalized Ramsey number, denoted r(G,H,q), is the minimum number of colours needed to edge-colour G such that every copy of H receives at least q colours. In this paper, we prove that for a fixed integer k ≥ 3, we have r(Kn,Ck,3) = n/(k−2)+o(n). This generalizes the work of Joos and Muybayi, who proved r(Kn,C4,3) = n/2+o(n). We also provide an upper bound on r(Kn,n, Ck, 3), which generalizes a result of Joos and Mubayi that r(Kn,n,C4,3) = 2n/3+o(n). Both of our results are in fact specific cases of more general theorems concerning families of cycles.

Related

  1. Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
    Ali Ghalavand
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
    Eng Keat Hng
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. New bounds for off-diagonal hypergraph Ramsey numbers
    David Conlon, Xiaoyu He, Jiaxi Nie +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Multicolor Ramsey numbers of ordered matchings
    Xiangyu Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Star-critical Ramsey numbers involving large generalized books
    Peiyu Huang, Qizhong Lin, Lin Niu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{morrison2026generalized,
  title = {{Generalized Ramsey Numbers via Conflict-Free Hypergraph Matchings}},
  author = {Natasha Morrison and Andrew Lane},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/14492},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p2},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Generalized Ramsey Numbers via Conflict-Free Hypergraph Matchings
AU  - Natasha Morrison
AU  - Andrew Lane
PY  - 2026
DA  - 2026/10/09
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/14492
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p2
AB  - Given graphs $G, H$ and an integer q ≥ 2, the generalized Ramsey number, denoted r(G,H,q), is the minimum number of colours needed to edge-colour G such that every copy of H receives at least q colours. In this paper, we prove that for a fixed integer k ≥ 3, we have r(K_n,C_k,3) = n/(k−2)+o(n). This generalizes the work of Joos and Muybayi, who proved r(K_n,C_4,3) = n/2+o(n). We also provide an upper bound on r(K_n,n, C_k, 3), which generalizes a result of Joos and Mubayi that r(K_n,n,C_4,3) = 2n/3+o(n). Both of our results are in fact specific cases of more general theorems concerning families of cycles.
SN  - 1077-8926
ER  -