Hypergraphs of Low Degree Without Independent Transversals
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.22993
curl -X POST /api/v1/records/arxiv/2610.22993/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22993/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'