An Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension
summary
Shows that a 3‑uniform hypergraph with VC_2-dimension ≤ k admits a Frankl–Rödl style regular decomposition whose number of edge‑colors ℓ is polynomial in 1/ε (ε the density/regularity parameter), replacing the usual Wowzer bound for ℓ; the vertex part count t is inherited from Frankl–Rödl and remains Wowzer in the proof. Proof sketch: apply Frankl–Rödl regularity, use the counting lemma to force triad densities near 0 or 1, form a reduced quotient graph with locally bounded VC and apply Haussler‑style packing to amalgamate partitions. Open: can t be reduced, and must ℓ be Wowzer in full generality?
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:28Background
- 4:17Special graph regularity: bounds
- 11:20Hypergraphs version
- 18:02Generalizations of partitions
- 28:11Regularity Lemma
- 32:33Special Regularity: bounds
- 35:32Poly bounds
- 39:14Special graph regularity: irregular pairs
- 41:57Special Hypergraph Regularity
related talks
23mTowards General and Tight Hardness Results for Graph Problems
46mLocal Graph Coloring
56mSatisfiability Algorithms II
35mDistributed Vertex Cover Reconfiguration
01h 00mHardness for Dynamic Problems; Conclusion and Future Research
23mA New Connection Between Node and Edge Depth Robust Graphs
10mQuery, Communication and Discrepancy
25mLower Bounds for Problems Parameterized by Clique-width