Metraipolis › archive › dc_03be302e14dc
The size-Ramsey numbers of $k$-uniform relaxed $\ell$-trees — arXiv:2609.04713
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.04713
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T23:20:54.410Z
- SHA-256 of the archived text
80e8260fefc23cc506294f86e9be768010340a95bb51ddc31788942d0308061e- Stable URL of this page
https://metraipolis.com/documento/dc_03be302e14dc
How to cite
The size-Ramsey numbers of $k$-uniform relaxed $\ell$-trees — arXiv:2609.04713 — arXiv (en), https://arxiv.org/abs/2609.04713 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_03be302e14dc (Metraipolis archive dc_03be302e14dc, sha256 80e8260fefc23cc506294f86e9be768010340a95bb51ddc31788942d0308061e)
BibTeX
@misc{dc03be302e14dc,
title = {The size-Ramsey numbers of $k$-uniform relaxed $ell$-trees — arXiv:2609.04713},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.04713},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_03be302e14dc; sha256 80e8260fefc23cc506294f86e9be768010340a95bb51ddc31788942d0308061e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04713. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The size-Ramsey number $\widehat{R}_k(\mathcal G)$ of a $k$-uniform hypergraph $\mathcal G$ is the minimum number of edges in a $k$-uniform hypergraph $\mathcal H$ such that every $2$-edge-coloring of $\mathcal H$ contains a monochromatic copy of $\mathcal G$. Fox asked whether, for fixed $2\le \ell<k$, the size-Ramsey number of every $k$-uniform relaxed $\ell$-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 $\ell+1\le k\le 2\ell-2$. More precisely, for every sufficiently large $n$, we construct a $k$-uniform relaxed $\ell$-tree $\bar{\mathcal T}_{n,\ell}^{(k)}$ on exactly $n$ vertices such that \[ \widehat{R}_k\bigl(\bar{\mathcal T}_{n,\ell}^{(k)}\bigr) \ge 2^{c_{k,\ell}n^{\,1-1/(2\ell-k)}}, \] where $c_{k,\ell}>0$ depends only on $k$ and $\ell$. Moreover, any two distinct edges of the construction intersect in at most $2\ell-k-1$ vertices. In contrast, for $k\ge 2\ell$, we prove that every $k$-uniform relaxed $\ell$-tree $\bar{\mathcal T}_{n,\ell}^{(k)}$ on $n$ vertices satisfies \[ \widehat{R}_k\bigl(\bar{\mathcal T}_{n,\ell}^{(k)}\bigr) =O_{k,\ell}(n^{2k}). \]
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.04713 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:03:13.243Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).