Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 5 min ago
PreprintCC BY-NC-SA 4.0arXiv

The size-Ramsey numbers of k-uniform relaxed β„“-trees

  • Meng Ji
  • Yulai Ma
Open at sourcePDFDOICite

Abstract

The size-Ramsey number RΜ‚k(𝒒) of a k-uniform hypergraph 𝒒 is the minimum number of edges in a k-uniform hypergraph β„‹ such that every $2$-edge-coloring of β„‹ contains a monochromatic copy of 𝒒. Fox asked whether, for fixed 2≀ β„“<k, the size-Ramsey number of every k-uniform relaxed β„“-tree on n vertices is bounded by a polynomial in n, as recorded by Dudek, La Fleur, Mubayi and RΓΆdl. We give a negative answer when β„“+1≀ k≀ 2β„“βˆ’2. More precisely, for every sufficiently large n, we construct a k-uniform relaxed β„“-tree 𝒯̅n,β„“(k) on exactly n vertices such that RΜ‚k(𝒯̅n,β„“(k)) β‰₯ 2ck,β„“n 1βˆ’1/(2β„“βˆ’k), where ck,β„“>0 depends only on k and β„“. Moreover, any two distinct edges of the construction intersect in at most 2β„“βˆ’kβˆ’1 vertices. In contrast, for kβ‰₯ 2β„“, we prove that every k-uniform relaxed β„“-tree 𝒯̅n,β„“(k) on n vertices satisfies RΜ‚k(𝒯̅n,β„“(k)) =Ok,β„“(n2k).

Related

  1. Ordered Trees with Linear Off-Diagonal Ramsey Numbers
    Lior Gishboliner, Artur Kravtsov, Xiangyu Li
    arXivPreprintarXiv licenceFull 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. Multicolor Ramsey and list Ramsey numbers for star-like trees
    Qinghong Zhao, Yaping Mao, Xiangqian Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy
    Wen Chen, Zihan He, Qizhong Lin +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Size Ramsey numbers of star forests with two components on one side
    Chunlin You
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ji2026sizeramsey,
  title = {{The size-Ramsey numbers of $k$-uniform relaxed $\ell$-trees}},
  author = {Meng Ji and Yulai Ma},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.04713},
  eprint = {2609.04713},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.04713},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - The size-Ramsey numbers of k-uniform relaxed β„“-trees
AU  - Meng Ji
AU  - Yulai Ma
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.04713
UR  - https://arxiv.org/abs/2609.04713
AB  - The size-Ramsey number RΜ‚_k(𝒒) of a k-uniform hypergraph 𝒒 is the minimum number of edges in a k-uniform hypergraph β„‹ such that every $2$-edge-coloring of β„‹ contains a monochromatic copy of 𝒒. Fox asked whether, for fixed 2≀ β„“<k, the size-Ramsey number of every k-uniform relaxed β„“-tree on n vertices is bounded by a polynomial in n, as recorded by Dudek, La Fleur, Mubayi and RΓΆdl. We give a negative answer when β„“+1≀ k≀ 2β„“βˆ’2. More precisely, for every sufficiently large n, we construct a k-uniform relaxed β„“-tree 𝒯̅_n,β„“^(k) on exactly n vertices such that RΜ‚_k(𝒯̅_n,β„“^(k)) β‰₯ 2^c_k,β„“n^ 1βˆ’1/(2β„“βˆ’k), where c_k,β„“>0 depends only on k and β„“. Moreover, any two distinct edges of the construction intersect in at most 2β„“βˆ’kβˆ’1 vertices. In contrast, for kβ‰₯ 2β„“, we prove that every k-uniform relaxed β„“-tree 𝒯̅_n,β„“^(k) on n vertices satisfies RΜ‚_k(𝒯̅_n,β„“^(k)) =O_k,β„“(n^2k).
ER  -