Abstract:Let $g(r)$ be the minimum number of edges in an $r$-uniform intersecting hypergraph with cover number $r$. Erdős and Lovász proved the lower bound $g(r)\ge 8r/3-3$. We first give a completely elementary proof that $g(r)\ge 3r-4$. We then build on the same approach and apply Kahn's small-codegree hypergraph edge-colouring theorem to improve this to $g(r)\ge (61/20-o(1))r$. To the best of our knowledge, this is the first improvement over the Erdős-Lovász lower bound in about fifty years.
From: Varun Sivashankar [view email]
[v1]
Tue, 23 Jun 2026 17:55:10 UTC (35 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。