Hypergraphs of Low Degree Without Independent Transversals
Abstract
For every fixed k≥ 3 and every integer b≥ 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 (((k−1)k−1)/kk+Ok(b−1))bk, while the maximum vertex degree is (((k−2)k−2)/((k−1)k−1)+Ok(b−1))bk−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 Δ(G)<(1−1/k)k−1nk−1, but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.
Related
- Independent transversals in hypergraphs with low codegrees
- The ℓ-degree Turán densities of hypergraphs: infinite families and their finite subfamilies
- Rational values and non-principality for ℓ-degree Turán densities of hypergraphs
- On Counting Independent Sets in Regular Hypergraphs
- Extremal hypergraphs without generalized 4-cycles
BibTeX
@misc{song2026hypergraphs,
title = {{Hypergraphs of Low Degree Without Independent Transversals}},
author = {Xinzhe Song and Xia Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22993},
eprint = {2610.22993},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22993},
}
RIS
TY - UNPB
TI - Hypergraphs of Low Degree Without Independent Transversals
AU - Xinzhe Song
AU - Xia Wang
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22993
UR - https://arxiv.org/abs/2610.22993
AB - For every fixed k≥ 3 and every integer b≥ 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 (((k−1)^k−1)/k^k+O_k(b^−1))b^k, while the maximum vertex degree is (((k−2)^k−2)/((k−1)^k−1)+O_k(b^−1))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 Δ(G)<(1−1/k)^k−1n^k−1, but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.
ER -