Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles
Abstract
For every fixed k≥ 3, every finite nonempty clutter ℋ can be realized exactly as the family of inclusion-minimal terminal traces of the k-bad odd cycles, namely the odd cycles C satisfying χ(G[V(C)])≥ k+1. The host graph G may be chosen $2$-connected, with T=V(ℋ) independent, and with χ(G)=k+1, ω(G)=k, and |E(G)|≤ k|V(G)|. Given any integer B≥ 1, one realization simultaneously preserves the transversal number, the fractional packing number, and every integer c-packing number for 1≤ c≤ B. Thus chromatic richness on odd-cycle spans has the full packing-covering complexity of arbitrary finite set systems, even in sparse graphs whose chromatic number exceeds their clique number by one. As a consequence, for every b,N≥ 1 and every ε>0, there is such a graph with τk(G)=N, νk1/c(G)=c for every 1≤ c≤ b, and νk*(G)<1+ε. Hence every finite-congestion and fractional Erdős--Pósa property fails for k≥ 3, with an asymptotically optimal fractional obstruction. This contrasts sharply with k=2, where the relevant cycles are the ordinary odd cycles: the integral property fails, while Reed's theorem yields every congestion level at least two and the fractional property. We also characterize the shortest k-bad odd cycles by a single fixed witness graph.
Related
- The Erdős--Hajnal hypergraph Ramsey problem for r4(6,n)
- Spectral Erdős--Gallai Theorems for the 𝒜α-Tensor of the s-Clique Hypergraph
- Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
- Hitting time for loose Hamilton cycles in the random hypergraph process
- Erdös–Pósa property of cycles that are far apart
BibTeX
@misc{chen2026hypergraph,
title = {{Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles}},
author = {Shuyan Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26158},
eprint = {2609.26158},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26158},
}
RIS
TY - UNPB
TI - Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles
AU - Shuyan Chen
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26158
UR - https://arxiv.org/abs/2609.26158
AB - For every fixed k≥ 3, every finite nonempty clutter ℋ can be realized exactly as the family of inclusion-minimal terminal traces of the k-bad odd cycles, namely the odd cycles C satisfying χ(G[V(C)])≥ k+1. The host graph G may be chosen $2$-connected, with T=V(ℋ) independent, and with χ(G)=k+1, ω(G)=k, and |E(G)|≤ k|V(G)|. Given any integer B≥ 1, one realization simultaneously preserves the transversal number, the fractional packing number, and every integer c-packing number for 1≤ c≤ B. Thus chromatic richness on odd-cycle spans has the full packing-covering complexity of arbitrary finite set systems, even in sparse graphs whose chromatic number exceeds their clique number by one. As a consequence, for every b,N≥ 1 and every ε>0, there is such a graph with τ_k(G)=N, ν_k^1/c(G)=c for every 1≤ c≤ b, and ν_k^*(G)<1+ε. Hence every finite-congestion and fractional Erdős--Pósa property fails for k≥ 3, with an asymptotically optimal fractional obstruction. This contrasts sharply with k=2, where the relevant cycles are the ordinary odd cycles: the integral property fails, while Reed's theorem yields every congestion level at least two and the fractional property. We also characterize the shortest k-bad odd cycles by a single fixed witness graph.
ER -