Tuza: Critical hypergraphs and intersecting set-pair systems

Full paper in Markdown.

---

Full paper in Markdown.

Zsolt Tuza, "Critical hypergraphs and intersecting set-pair systems," Journal of Combinatorial Theory, Series B, 39(2), 134-145, 1985. https://doi.org/10.1016/0095-8956(85)90043-7

Overview

Tuza develops a set-pair method for bounding the number of vertices, rather than edges, in critical hypergraphs. An intersecting set-pair system (ISP-system) consists of pairs $(A_i,B_i)$ satisfying $A_i\cap B_j=\varnothing$ exactly when $i=j$; an $(a,b)$-system additionally has $|A_i|=a$ and $|B_i|=b$ (Section 1, pp. 134–135). The extremal parameters $n(a,b)$ and $n_1(a,b)$ maximize, respectively, $|\bigcup_i(A_i\cup B_i)|$ and $|\bigcup_iA_i|$ over such systems (p. 135). The starting point is Bollobás's set-pairs inequality

$$\sum_i\binom{|A_i|+|B_i|}{|A_i|}^{-1}\leq1,$$

labelled $(*)$ in Section 2 (p. 136). Constructions 1 and 2 (p. 136) supply large ISP-systems, and the composition following Remark 3 proves

$$n_1(a'+a'',b'+b'')\geq a'+b'+\binom{a'+b'}{a'}n_1(a'',b'')$$

(pp. 136–137).

The central reduction is Lemma 4 (p. 137). If $\mathcal T$ is the family of transversal sets of a hypergraph $\mathcal H$ having size at most $t$, and if for every edge $E_i$ every subset of $E_i$ meeting all members of $\mathcal T$ has size at least $s_i=\min(s,|E_i|)$—condition $(**)$—then

$$\tau_s(\mathcal H)\leq n_1(t,s-1).$$

The proof takes a subsystem minimal with respect to $(**)$ and assigns to each retained $T_j$ a set $F^j$ of size at most $s-1$ which misses $T_j$ but meets every other retained member; the pairs $(T_j,F^j)$ form an ISP-system. This yields the symmetry identity

$$n_1(a,b-1)=n_1(b,a-1)$$

(Theorem 5, p. 137).

The principal numerical estimate is Theorem 6 (pp. 138–139). For $a\geq b$ and $a>0$ it gives an explicit binomial-sum upper bound for $n(a,b)$, lying below $\binom{a+b+1}{b+1}$, while for all $a\geq1$, $b\geq0$,

$$\frac14\binom{a+b+1}{b+1}<n_1(a,b)<\binom{a+b+1}{b+1}.$$

The lower estimate comes from Construction 1 with $a'=\lfloor ab/(b+1)\rfloor$; the upper estimate combines iterative pruning with $(*)$. Proposition 7 determines

$$n(a,0)=n_1(a,0)=a,\qquad n(a,1)=n_1(a,1)=\left\lfloor\left(\frac{a+2}{2}\right)^2\right\rfloor$$

(p. 139). The proposed exact descriptions in Problem 8 (pp. 139–140) are explicitly open; Proposition 9 proves only that $n_1(a,b)\ne n(a,b)$ when $b>4a+3$ (p. 140).

Section 3 applies the method to $\nu$-critical hypergraphs. Theorem 10 states that a $\nu$-critical hypergraph of rank $r$ satisfies

$$|V(\mathcal H)|\leq n_1(r\nu,r-1)<\binom{r\nu+r}{r}$$

(p. 140). The proof applies Lemma 4 with $s=r$ and $t=\nu r$ to the unions of $\nu$ pairwise disjoint edges and uses $|V(\mathcal H)|=\tau_r(\mathcal H)$, which the definition on p. 135 gives for rank-$r$ hypergraphs. Construction 11 (pp. 140–141) supplies a large intersecting, $\nu$-critical $r$-uniform example, leading to the two-sided estimate in Corollary 12 (p. 141). The proposed linear bound in $\nu$ for fixed rank remains Problem 13, not a theorem (p. 141).

Section 4 treats $\tau$-critical hypergraphs, where deleting any edge lowers the ordinary transversal number $t=\tau(\mathcal H)$. Each edge $E_i$ then has a certificate $T_i$ of size $t-1$ which misses $E_i$ and meets every other edge, so $(E_i,T_i)$ is an ISP-system (Section 4.1, p. 141). Conversely, Construction 15 completes any $(a,b)$-system to a generally nonuniform $\tau$-critical hypergraph $\mathcal H^*$ with $\tau(\mathcal H^*)=b+1$ and $\tau_a(\mathcal H^*)\geq|\bigcup_iA_i|$ (pp. 141–142). Theorem 17 consequently bounds the maximum order $n'_r$ of an $r$-uniform $\tau$-critical hypergraph with transversal number $t$ by

$$n'_r\leq n_1(r,t-1)<\binom{t+r}{r},$$

and gives $n'_r\geq\frac14\binom{t+r}{r}$ when $r\geq t-1$ (p. 142). The sharper formulas in Problem 18 are conjectural (pp. 142–143).

Finally, Section 4.3 studies the $s$-transversal number, a concept of Lehel that Tuza modifies slightly in Section 1: a set must, for each edge, contain it or meet it in at least $s$ vertices. For $\tau$-critical hypergraphs, Theorem 19 proves the exact identity and symmetry

$$m(s,t)=n_1(s,t-1)=m(t,s)$$

(p. 143), hence $\frac14\binom{s+t}{t}<m(s,t)<\binom{s+t}{t}$. For $k$-intersecting hypergraphs—meaning that every $k$ edges have a common vertex—Theorem 20 gives

$$\frac1k n_1(s,t-1)\leq m_k(s,t)\leq n_1(s,t-1),$$

and, for fixed $t,k\geq1$, $m_k(s,t)>\frac14n_1(s,t-1)$ for all sufficiently large $s$ (p. 144). These results concern criticality, common intersections, and multiple hits per edge; they do not study local two-point piercing directly.

Relation to E644

This source bears on Problem 644.

Write an E644 instance as a $k$-uniform hypergraph $\mathcal H$ and denote its local hypothesis by

$$P_r:\qquad \tau(\mathcal F)\leq2\quad\text{for every }\mathcal F\subseteq E(\mathcal H),\ |\mathcal F|=r.$$

Then $f(k,r)$ is the desired universal upper bound on the ordinary transversal number $t=\tau(\mathcal H)$ under $P_r$. This must not be confused with Tuza's $\tau_2(\mathcal H)$: for a $k$-uniform hypergraph, the latter is the minimum size of one set meeting every edge in at least two vertices (definition on p. 135), whereas $P_r$ says that each $r$-edge subhypergraph has an ordinary transversal of size at most two.

Tuza's directly usable reduction applies to a finite E644 instance. Choose an edge-minimal subhypergraph $\mathcal G\subseteq\mathcal H$ with $\tau(\mathcal G)=t$. Then $\mathcal G$ is $\tau$-critical, remains $k$-uniform, and inherits $P_r$. Section 4.1 (p. 141) provides, for every $E_i\in E(\mathcal G)$, a set $T_i$ with

$$|T_i|=t-1,\qquad T_i\cap E_i=\varnothing,\qquad T_i\cap E_j\ne\varnothing\quad(j\ne i).$$

Thus $(E_i,T_i)$ is a $(k,t-1)$ ISP-system. Bollobás's inequality $(*)$ on p. 136 immediately gives the finite critical-kernel bound

$$|E(\mathcal G)|\leq\binom{k+t-1}{k},$$

while Theorem 17 (p. 142) gives

$$|V(\mathcal G)|\leq n_1(k,t-1)<\binom{k+t}{k}.$$

Construction 15 (pp. 141–142) does not preserve $k$-uniformity or guarantee $P_r$. Theorem 20 is not directly applicable: its hypothesis that every specified number of edges has a common vertex is strictly a different condition from their being jointly pierceable by two vertices.

Consequently, the paper supplies the critical-core/ISP framework and quantitative bounds conditional on the unknown global value $t$, but it neither proves $f(k,7)=(3/4+o(1))k$ nor proves the existence of constants $c_r$. In particular, substituting $t=\Theta(k)$ into Theorem 17 only yields an exponential-size bound on the critical core and gives no constraint on the coefficient of $k$. The paper also works in a finite-hypergraph framework and does not address passage from the possibly infinite families allowed by E644's formulation.