Metraipolis › archive › dc_47a289aca291

Hypergraphs of Low Degree Without Independent Transversals — arXiv:2610.22993

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.22993
License (as archived)
CC0-1.0
Archived
2026-10-19T09:39:24.325Z
SHA-256 of the archived text
6acf72f5e44bf967ef0a78b73f193d621c92a433b39a6d730a0b9d3a2098a3a6
Stable URL of this page
https://metraipolis.com/documento/dc_47a289aca291

How to cite

Hypergraphs of Low Degree Without Independent Transversals — arXiv:2610.22993 — arXiv (en), https://arxiv.org/abs/2610.22993 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_47a289aca291 (Metraipolis archive dc_47a289aca291, sha256 6acf72f5e44bf967ef0a78b73f193d621c92a433b39a6d730a0b9d3a2098a3a6)
BibTeX
@misc{dc47a289aca291,
  title = {Hypergraphs of Low Degree Without Independent Transversals — arXiv:2610.22993},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.22993},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_47a289aca291; sha256 6acf72f5e44bf967ef0a78b73f193d621c92a433b39a6d730a0b9d3a2098a3a6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22993. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For every fixed $k\ge 3$ and every integer $b\ge 2$, we construct a finite vertex-partitioned $k$-uniform hypergraph with blocks of size $b$ and no independent transversal. We show that the maximum number of edges meeting a block is $\left(\frac{(k-1)^{k-1}}{k^k}+O_k(b^{-1})\right)b^k,$ while the maximum vertex degree is $\left(\frac{(k-2)^{k-2}}{(k-1)^{k-1}}+O_k(b^{-1})\right)b^{k-1}$. This shows that the known bound on the number of edges meeting a block is asymptotically sharp even when the leading constant in the maximum vertex degree tends to zero, which answers a problem of Groenland, Kaiser, Treffers, and Wales. By blowing up the same construction, we further obtain for arbitrarily large $n$, there exists a $k$-uniform hypergraph with $n$ blocks, each of size at least $n$, and $\Delta(G)<\left(1-\frac1k\right)^{k-1}n^{k-1}$, but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.22993 — 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-19T09:34:59.742Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).