Sharp exponential edge bounds and flag constructions for multipartite intersecting hypergraphs
Let H be a finite, nonempty, simple r-partite r-uniform hypergraph with pairwise intersections of size at least t, where t <= r <= 3t. We prove |E(H)| >= 2^tau(H)-1 and determine necessary equality conditions. Binary complete flags attain equality with unbounded cover number at fixed ratio r/t = 3, answering the construction direction of Problem 1 of Bishnoi, Das, Morris and Szabo. An incidence-matrix inequality relates cover number and minimum positive degree to intersection excess. Local witness arguments imply tau(H) <= t+1 for strictly t-intersecting (3t,t)-graphs and give necessary conditions for counterexamples with varying intersections. Combining the exponential edge theorem with Deza's sunflower theorem yields tau(H) <= floor(log2(r^2-r+2)) in the strictly intersecting subclass. At r = 3t, the two covering bounds combine as their minimum, with the logarithmic term stronger for t >= 9. Version 1.1.0 adds the Deza consequence with an analytic proof, comparison with the classical covering estimate recorded by Nagy, verified references, and supplementary checks. It builds on the two internal AI-assisted review/revision cycles documented with version 1.0.0. Source, verification programs, results and revision history are included. Documents and result data: CC BY 4.0. Python verification programs: Apache License 2.0, as specified in LICENSES.txt.
Authors
- Yiming Liu
Institutions
- University of South China (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-06
- DOI
- https://doi.org/10.5281/zenodo.23179211
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint