Local constraints ensuring small representing sets: the local-to-global covering relation $(p,s)\underset{r}{\longrightarrow}t$ of Erdős–Hajnal–Tuza

How do local covering properties of a uniform hypergraph force its global transversal number to be small? Erdős, Hajnal and Tuza (J. Combin. Theory Ser. A 58 (1991) 78–84) formalized this by the relation $(p,s)\underset{r}{\longrightarrow}t$ : every $r$ -uniform set system in which each subfamily spanning at most $p$ points is coverable by $s$ points has a transversal of at most $t$ points. They settled much of the $s=1$ case — $p_0(r,r,1)=2r$ , $(3r-3,1)\underset{r}{\longrightarrow}r-1$ , sharp via projective planes when $r-1$ is a prime power — and raised the sets-bounded variant $h_r(k,\ell)$ .

Background

A set system (hypergraph) $\mathscr{F}$ is a collection of sets, called edges, drawn from an underlying point set; it is $r$ -uniform when every edge has exactly $r$ points. A transversal — also called a covering set, and in the source paper a representing set — is a set of points meeting every edge, and the transversal number $\tau(\mathscr{F})$ is the minimum size of a transversal. A classical theme going back to Helly's theorem on convex sets (if every $d+1$ members of a family of convex sets in $\mathbb{R}^d$ intersect, then the whole family has a common point) is to ask how a local regularity condition forces a global covering property.

Erdős, Hajnal and Tuza (1991) introduced a quantitative local-to-global question for uniform set systems. Write $(p,s)\underset{r}{\longrightarrow}t$ if every $r$ -uniform set system $\mathscr{F}$ in which every subfamily spanning at most $p$ points can be met by $s$ points satisfies $\tau(\mathscr{F})\le t$ ; let $p_0(r,t,s)$ be the least such $p$ and $t_0(p,r,s)$ the least $t$ forced by a given $p$ and $s$ ; for the case $s=1$ treated in the source paper we abbreviate $p_0(r,t)=p_0(r,t,1)$ . The paper determined much of the $s=1$ landscape. Pairwise-disjoint families show $(2r-1,1)\underset{r}{\not\longrightarrow}t$ for every fixed $t$ ; a pairwise-intersecting family is covered by any single edge, giving $(2r,1)\underset{r}{\longrightarrow}r$ and $p_0(r,r,1)=2r$ ; and $(3r-3,1)\underset{r}{\longrightarrow}r-1$ . A general upper bound $(\max\{3r-3,p(r,t)\},1)\underset{r}{\longrightarrow}t$ holds with the explicit function $p(r,t)=\max_{1\le m\le r-1}\bigl(\lceil m/t\rceil(r-m-t)+2r-m\bigr)$ , matched up to a small additive term by explicit 'central set plus disjoint wings' constructions — a central set augmented by pairwise disjoint 'wing' sets; consequently the least $t$ with $(kr,1)\underset{r}{\longrightarrow}t$ is of order $\Theta(r/k)$ for $k\le(r+2)^2/(4r)$ . Sharpness of the $t=r-1$ result uses the lines of a projective plane — an incidence structure of order $q$ with $q^2+q+1$ points and lines, $q+1$ points per line, and any two lines meeting in exactly one point, constructed whenever $q$ is a prime power. The lines form a $(q+1)$ -uniform family with $\tau=q+1$ in which any three lines span at least $3q$ points, so with $r=q+1$ one gets $(3r-4,1)\underset{r}{\not\longrightarrow}r-1$ whenever $r-1$ is a prime power. No projective plane of order $6$ or $10$ exists (by the Bruck–Ryser theorem — a number-theoretic obstruction implying that a plane of order $q\equiv1,2\pmod 4$ can exist only if $q$ is a sum of two integer squares, which rules out order $6$ — and by exhaustive computer search in the case of order $10$ , respectively), and order $12$ is a famous open case, which is exactly why the instances $r=7,11,13$ are exceptional.

The same paper raised the variant in which the local constraint bounds the number of edges rather than points: $h_r(k,\ell)$ is the maximum possible transversal number of an $r$ -uniform hypergraph in which any $k$ edges admit a cover of at most $\ell$ points. This variant was studied for $\ell=2$ by Erdős–Fon-Der-Flaass–Kostochka–Tuza (1992), Fon-Der-Flaass–Kostochka–Woodall (1999) and Kostochka (2002), and in general by Bucić–Korándi–Sudakov (2021), who proved $h_r(\ell+1,\ell)=r\ell$ , that $h_r(k,\ell)=\ell$ exactly when $k\ge\binom{\ell+r}{r}$ (via a classical set-pair inequality), and determined $h_r(k,r)$ up to constant factors across the whole range of $k$ , leaving in the middle of the range a multiplicative gap of about $\log(\ell/\log k)$ between their bounds (their own formulation), which they list as an open problem. Bucić–Korándi–Sudakov and subsequently Bradač–Bucić (2023) connected the $r$ -partite version of this variant (edges meeting each of $r$ fixed vertex classes once) to Ryser's conjecture — the assertion that an $r$ -partite $r$ -uniform hypergraph with matching number $\nu$ , the maximum number of pairwise disjoint edges, has $\tau\le(r-1)\nu$ — and to the problem of covering randomly coloured graphs by monochromatic trees. By contrast, the points-bounded relation $(p,s)\underset{r}{\longrightarrow}t$ beyond $s=1$ , the source paper's declared main open direction, has received no follow-up work.

Problem Statement

Determine the local-to-global covering relation for uniform set systems introduced by Erdős–Hajnal–Tuza (1991): writing $(p,s)\underset{r}{\longrightarrow}t$ if every $r$ -uniform set system in which every subfamily spanning at most $p$ points can be met by $s$ points has transversal number at most $t$ , characterize — for each uniformity $r$ — the trade-off between the local parameters $(p,s)$ and the forced global transversal $t$ ; equivalently, determine (exactly, or up to a stated constant factor or a stated asymptotic order) the threshold functions $p_0(r,t,s)=\min\{p:(p,s)\underset{r}{\longrightarrow}t\}$ and $t_0(p,r,s)=\min\{t:(p,s)\underset{r}{\longrightarrow}t\}$ . The source work settled the case $s=1$ except for components (2) and (3) below; together the four components below constitute the open core:

(1) $s\ge2$ (the paper's stated main question): for given $r$ and each $s\ge2$ , determine $p_0(r,t,s)$ and $t_0(p,r,s)$ — in particular, by how much the explicit function $p(r,t)=\max_{1\le m\le r-1}\bigl(\lceil m/t\rceil(r-m-t)+2r-m\bigr)$ entering the general upper bound $(\max\{3r-3,p(r,t)\},1)\underset{r}{\longrightarrow}t$ (the $s=1$ threshold $p_0(r,t)$ equals it only up to a small additive term) increases when subfamilies may be covered by $s$ points instead of one — the local hypothesis weakens, so larger subfamilies must be inspected to force the same global transversal — and which structures replace projective planes and the 'central set plus disjoint wings' systems as the extremal obstructions.

(2) Exceptional instance: determine the integer $p_0(7,6)$ , currently known only to satisfy $14\le p_0(7,6)\le18$ ; in particular decide whether $(14,1)\underset{7}{\longrightarrow}6$ and whether $(17,1)\underset{7}{\not\longrightarrow}6$ (the latter is the $r=7$ case of (3)).

(3) Essentiality of the prime-power hypothesis: determine the set of $r\ge3$ for which $(3r-4,1)\underset{r}{\not\longrightarrow}r-1$ holds, in particular whether it is all $r\ge3$ or exactly the $r$ for which $r-1$ is a prime power; note that no projective plane of order $6$ or $10$ exists while order $12$ is open, so for $r=7,11,13$ a counterexample must be non-geometric.

(4) Sets-bounded variant: determine $h_r(k,\ell)$ , the maximum transversal number of an $r$ -uniform hypergraph in which any $k$ edges admit a cover of at most $\ell$ points, in the regimes left open — close the middle-range multiplicative gap of about $\log(\ell/\log k)$ between the bounds of Bucić–Korándi–Sudakov, and determine exact values beyond $h_r(\ell+1,\ell)=r\ell$ , the threshold $k\ge\binom{\ell+r}{r}$ for $h_r(k,\ell)=\ell$ , and the $\ell=2$ results for $k\le6$ and the bounds at $k=7$ .

These components are instances of a single scientific objective — quantifying how local coverability forces small global transversals in uniform set systems. The objective concerns the relation for all $(p,s,r,t)$ in the points-bounded formulation and all $(k,\ell,r)$ in the sets-bounded formulation.

References

Paul Erdős, András Hajnal, Zsolt Tuza, Local constraints ensuring small representing sets, Journal of Combinatorial Theory, Series A 58 (1991), no. 1, 78–84. DOI: 10.1016/0097-3165(91)90074-q, https://doi.org/10.1016/0097-3165(91)90074-q
Matija Bucić, Dániel Korándi, Benny Sudakov, Covering graphs by monochromatic trees and Helly-type results for hypergraphs, Combinatorica 41 (2021), no. 3, 319–352. DOI: 10.1007/s00493-020-4292-9, arXiv:1902.05055, https://arxiv.org/abs/1902.05055
Domagoj Bradač, Matija Bucić, Covering random graphs with monochromatic trees, Random Structures & Algorithms 62 (2023), no. 3, 545–563 (published online November 2022). DOI: 10.1002/rsa.21120, arXiv:2109.02569, https://arxiv.org/abs/2109.02569
Alexandr V. Kostochka, Transversals in uniform hypergraphs with property (p,2), Combinatorica 22 (2002), no. 2, 275–285. DOI: 10.1007/s004930200013, https://doi.org/10.1007/s004930200013
Dmitry G. Fon-Der-Flaass, Alexandr V. Kostochka, Douglas R. Woodall, Transversals in uniform hypergraphs with property (7,2), Discrete Mathematics 207 (1999), no. 1–3, 277–284. DOI: 10.1016/S0012-365X(99)00114-4, https://doi.org/10.1016/S0012-365X(99)00114-4
P. Erdős, D. G. Fon-Der-Flaass, A. V. Kostochka, Zs. Tuza, Small transversals in uniform hypergraphs, Siberian Advances in Mathematics 2 (1992), 82–88. No DOI exists.
Zsolt Tuza, Helly property in finite set systems, Journal of Combinatorial Theory, Series A 62 (1993), no. 1, 1–14. DOI: 10.1016/0097-3165(93)90068-J, https://doi.org/10.1016/0097-3165(93)90068-J
Paul Erdős, A Selection of Problems and Results in Combinatorics, Combinatorics, Probability and Computing 8 (1999), no. 1–2, 1–6. DOI: 10.1017/S0963548398003496, https://doi.org/10.1017/S0963548398003496
Michael Krivelevich, $K^s$ -Free Graphs Without Large $K^r$ -Free Subgraphs, Combinatorics, Probability and Computing 3 (1994), no. 3, 349–354. DOI: 10.1017/S0963548300001243, https://doi.org/10.1017/S0963548300001243