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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Sharp exponential edge bounds and flag constructions for multipartite intersecting hypergraphs

Yiming Liu
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Sharp exponential edge bounds and flag constructions for multipartite intersecting hypergraphs

Yiming Liu
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
University of South China (CN)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.