← All problems

Independent-transversal degree and edge-bound problems

For every integer k≥3k\ge 3, does every finite kk-uniform hypergraph whose vertex set is partitioned into nn blocks, each of size at least nn, and whose maximum vertex degree satisfies Δ(G)<(1−1k)k−1nk−1\Delta(G)<\left(1-\frac{1}{k}\right)^{k-1}n^{k-1} necessarily contain an independent transversal, that is, an independent set containing exactly one vertex from each block?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 o(1)tr−1o(1)t^{r-1}, and its blow-up is claimed to violate a proposed threshold.

Known results

  • Wanless and Wood: every partition with blocks of size at least tt and maximum block-average degree at most t/4t/4 has an independent transversal.
  • The t/4t/4 threshold is sharp: for every ε>0\varepsilon>0, sufficiently large tt admits a forest with maximum block-average degree at most (1/4+ε)t(1/4+\varepsilon)t and no independent transversal.
  • For fixed r≥2r\ge 2, constructions exist with each part meeting at most (1+ε)(1+\varepsilon) times the asymptotic edge bound and no independent transversal.
  • A separate theorem gives independent-transversal blow-ups under part size at least (s+ε)D(s+\varepsilon)D 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 o(1)tr−1o(1)t^{r-1} 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.

Sources

Solutions 0

No solutions have been posted yet.