PreprintCC BY-NC-ND 4.0arXiv
Independent transversals in hypergraphs with low codegrees
Abstract
We prove that for every fixed r≥3, k>0 and ε∈(0,1), there is γ>0 such that the following holds for all sufficiently large b. An r-uniform hypergraph ℋ whose vertex set is partitioned into parts of size at least b contains at least ⌈(1−ε)b⌉ pairwise vertex-disjoint independent transversals, provided that the average degree in each part is at most kbr−1 and maximum j-codegree Δj(ℋ)≤γbr−j for 2≤ j<r. Under the same average degree, if q is the minimum part size and Δj(ℋ)=o(qr−j) for 2≤ j<r, the maximum number of pairwise vertex-disjoint independent transversals is $(1-o(1))q$ as q→∞. We develop an iterative halving reduction for partitioned hypergraphs to apply the theorem of Delcourt and Postle on matchings avoiding forbidden submatchings.
Related
BibTeX
@misc{dai2026independent,
title = {{Independent transversals in hypergraphs with low codegrees}},
author = {Hanle Dai and Luyining Gan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28468},
eprint = {2610.28468},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28468},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Independent transversals in hypergraphs with low codegrees
AU - Hanle Dai
AU - Luyining Gan
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28468
UR - https://arxiv.org/abs/2610.28468
AB - We prove that for every fixed r≥3, k>0 and ε∈(0,1), there is γ>0 such that the following holds for all sufficiently large b. An r-uniform hypergraph ℋ whose vertex set is partitioned into parts of size at least b contains at least ⌈(1−ε)b⌉ pairwise vertex-disjoint independent transversals, provided that the average degree in each part is at most kb^r−1 and maximum j-codegree Δ_j(ℋ)≤γb^r−j for 2≤ j<r. Under the same average degree, if q is the minimum part size and Δ_j(ℋ)=o(q^r−j) for 2≤ j<r, the maximum number of pairwise vertex-disjoint independent transversals is $(1-o(1))q$ as q→∞. We develop an iterative halving reduction for partitioned hypergraphs to apply the theorem of Delcourt and Postle on matchings avoiding forbidden submatchings.
ER -