Abstract:Let $k\ge2$ be fixed. We study the integer lower bound $\ell(G)$ obtained by inverting the classical counting inequality for Turán systems. For a $k$-uniform hypergraph with $n$ vertices and $m$ edges, the bound can be evaluated exactly by binary search in time polynomial in the binary lengths of $n$ and $m$. We exhibit separations from the Turán-Spencer and Caro-Tuza bounds for every fixed $k\ge3$, and from the Csaba-Plick--hokoufandeh bound in the $3$-uniform case. For the Caro-Tuza comparison, the separation grows linearly in $k$ on infinitely many regular $k$-uniform hypergraphs.
From: Marco Aldi [view email]
[v1]
Mon, 17 Feb 2025 14:04:11 UTC (5 KB)
[v2]
Wed, 16 Sep 2026 12:43:07 UTC (13 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。