Independent-transversal degree and edge-bound problems
For every integer , does every finite -uniform hypergraph whose vertex set is partitioned into blocks, each of size at least , and whose maximum vertex degree satisfies necessarily contain an independent transversal, that is, an independent set containing exactly one vertex from each block?
References
- Hypergraphs of Low Degree Without Independent Transversals — arXiv — Xinzhe Song, Xia Wang
Source: arXiv
Progress summary
A new unrefereed preprint claims constructions that answer two independent-transversal threshold questions, but the claims have not been independently checked.
The problem asks when bounded-degree partitioned hypergraphs must contain an independent transversal. The latest construction is claimed to meet the asymptotic edge-bound while having maximum degree , and its blow-up is claimed to violate a proposed threshold.
Known results
- Wanless and Wood: every partition with blocks of size at least and maximum block-average degree at most has an independent transversal.
- The threshold is sharp: for every , sufficiently large admits a forest with maximum block-average degree at most and no independent transversal.
- For fixed , constructions exist with each part meeting at most times the asymptotic edge bound and no independent transversal.
- A separate theorem gives independent-transversal blow-ups under part size at least and suitably small cross-part maximum degree.
October 2026 preprint
Xinzhe Song and Xia Wang claim that their construction attains the asymptotic edge-meeting-block bound with maximum degree and that a blow-up violates the proposed Haxell-Wdowinski threshold. This is progress on the two tracked questions, but the preprint is unrefereed and no independent mathematical assessment was found.
Current status (as of October 2026): Classical thresholds are established, while the new asymptotic construction is a claimed but unverified advance on both tracked questions.
Solutions 0
No solutions have been posted yet.