Sharp exponential edge bounds and flag constructions for multipartite intersecting hypergraphs
We construct strictly t-intersecting r-partite r-uniform hypergraphs with fixed ratio r/t = 3 and arbitrarily large vertex cover number, answering Problem 1 of Bishnoi, Das, Morris and Szabo. The construction attains a sharp universal edge bound: every finite, nonempty, simple hypergraph in this multipartite class whose distinct edges meet in at least t vertices, with 1 <= t <= r <= 3t, satisfies |E(H)| >= 2^tau(H)-1. For tau(H) >= 2, equality forces r = 3t, exact intersection size t, and positive degrees 2^(tau(H)-1), ..., 1 in every part. Complete flags over the binary field attain equality for every cover number at least two. Further results include an incidence-matrix bound in terms of intersection excess, tau(H) <= t+1 for the strictly intersecting subclass at r = 3t, and a covering consequence of Deza's theorem. Version 1.2.0 reorganizes the abstract and introduction around the universal sharp bound and matching infinite family. It adds a fully derived, rounded greedy comparison, a precise comparison with Lemma 3.3 of Bishnoi et al., and the distinction between sharpness in the edge-count/cover-number relation and the growth of the all-flags family in r. The Deza discussion now compares against the stronger direct greedy baseline as well as the classical Lovasz/Nagy estimate. All five references were verified. Four verification programs passed, including enumeration of all 9,765 complete flags in dimension five with intersection and cover certificates. The package includes the ten-page manuscript, source, actual results, source diff, bibliographic audit and a fifteen-item response to the supplied review. 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.23180258
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint