A Bound Below 2.8 for Tuza's Conjecture

Suppose that $uvz\in\mathcal{F}_{P}$ for some $z\neq y\text{.}$ Since $uz\notin B(P)$ while $ux\in B(P)\text{,}$ also $z\neq x\text{.}$ The triangle $uxy$ has blue edges $ux,uy$ and red edge $xy\text{,}$ so it belongs to $\mathcal{F}(H)\text{,}$ and it meets $E(P)$ only in $ux\text{,}$ because $uy\notin B(P)$ and $xy\notin R(P)\text{.}$ The triangle $uvz$ meets $E(P)$ only in $uv\text{.}$ As $z\notin\{x,y\}\text{,}$ the triangles $uxy$ and $uvz$ are edge-disjoint, so replacing $uvx$ by both of them gives a packing in $\mathcal{F}(H)$ larger than $P\text{.}$ ∎

Let $T\in\mathcal{T}$ avoid $C\text{.}$ If every book had a page edge-disjoint from $T\text{,}$ choosing such a page in each book would give a maximal packing in $\mathcal{T}$ to which $T$ could still be added, a contradiction. So $T$ meets every page of some book $B\text{.}$ Since all edges of a one-page book lie in $C\text{,}$ $B$ has two or three pages, and $T$ avoids its spine $uv\text{,}$ so $T$ contains $uz$ or $vz$ for every page $uvz$ of $B\text{.}$ If $B$ had three pages, these would be three edges of $T$ with distinct ends outside $\{u,v\}\text{,}$ but a triangle has only three vertices. So $B=\{uvx,uvy\}\text{,}$ and $T$ contains one of $ux,vx$ and one of $uy,vy\text{.}$ Two edges of a triangle share a vertex, so these are $ux,uy$ or $vx,vy\text{,}$ and $T$ is $uxy$ or $vxy\text{.}$ Finally, a book with $k$ pages contributes at most $4-k$ edges to the transversal. ∎

Let $r$ be the number of members of $Q$ whose red edge is private in $\mathcal{F}_{P}\text{.}$ We build two transversals of $\mathcal{F}\text{,}$ which give

and then combine these bounds, once directly and once after applying Equation 1 to $\mathcal{F}_{P}\text{.}$

The first transversal comes from books. Each member of $Q$ shares its red edge with exactly one member of $P\text{,}$ and the two form a book with that red edge as spine. Each unpaired member of $P$ forms a one-page book. No member of $P$ is paired twice, as $Q$ is a packing, and the supports are edge-disjoint, as the blue edges of $Q$ avoid $B(P)\text{.}$ Every selection of one page per book is a packing in $\mathcal{F}$ of size $p=\nu(\mathcal{F})\text{,}$ hence maximal. A member of $P$ whose red edge is private in $\mathcal{F}$ is unpaired, since a page of $Q$ on the same spine would be a second member of $\mathcal{F}$ containing that edge.

Let $C$ consist of the $3(p-q)$ edges of the one-page books and the $q$ spines. By Lemma 2.2, a member of $\mathcal{F}$ avoiding $C$ is $uxy$ or $vxy$ for a two-page book $\{uvx,uvy\}$ with $uvx\in P$ and $uvy\in Q\text{.}$ The two edges it shares with the pages are blue, so $xy$ is red, and $xy\notin R(P)$ since $R(P)\subseteq C\text{.}$ By Lemma 2.1, $uv$ is private in $\mathcal{F}_{P}\text{,}$ so $uvy$ is one of the $r$ members of $Q$ with a private red edge. Adding the opposite edges of these at most $r$ books to $C$ therefore gives a transversal of $\mathcal{F}\text{.}$ Finally, delete the red edges of the $u$ unpaired members of $P$ whose red edge is private in $\mathcal{F}\text{:}$ the only member of $\mathcal{F}$ containing such an edge is that member of $P\text{,}$ which is met by its blue edges in $C\text{.}$ The transversal now has at most $3(p-q)+q+r-u$ edges, which is the first bound.

The second transversal starts from $B(P)\cup E(Q)\text{.}$ A member of $\mathcal{F}$ avoiding $B(P)$ lies in $\mathcal{F}_{P}$ and, as $Q$ is maximal there, meets $E(Q)\text{.}$ So $B(P)\cup E(Q)$ is a transversal of $\mathcal{F}\text{.}$ Delete the red edges of the $r$ members of $Q$ whose red edge is private in $\mathcal{F}_{P}\text{:}$ a member of $\mathcal{F}$ avoiding the remaining edges lies in $\mathcal{F}_{P}$ and contains a deleted edge, so it is the corresponding member of $Q\text{,}$ which is met by its blue edges. The remaining $2p+3q-r$ edges give the second bound.

Twice the first bound plus the second gives $3\tau(\mathcal{F})\leq 8p-q+r-2u\leq 8p-2u\text{,}$ as $r\leq q\text{,}$ which is Equation 1. Next, $Q$ is a maximum packing in $\mathcal{F}(H-B(P))=\mathcal{F}_{P}\text{,}$ and $r$ of its members have a red edge that is private in $\mathcal{F}_{P}\text{,}$ so Equation 1 for the graph $H-B(P)$ gives $\tau(\mathcal{F}_{P})\leq\tfrac{8}{3}q-\tfrac{2}{3}r\text{.}$ Since $B(P)$ meets every member of $\mathcal{F}\setminus\mathcal{F}_{P}\text{,}$

Three times this bound plus the first bound gives $4\tau(\mathcal{F})\leq 9p+6q-u-r\leq 9p+6q-u\text{,}$ which is Equation 2. ∎

We follow Haxell’s construction [Hax99]: the packings below and the first transversal are taken from it, and the other three transversals rest on the lemmas of Section 2. Choose a maximum triangle packing $P$ in $G\text{,}$ and put $n=|P|=\nu(G)$ and $O=E(P)\text{.}$ Call edges in $O$ old and all other edges new. A triangle has type $j$ if it contains exactly $j$ old edges. By maximality of $P$ there are no type-0 triangles.

Choose a maximum packing $A$ of type-1 triangles and put $a=|A|\text{.}$ The first transversal comes from books formed by $P$ and $A\text{.}$ Pair each member of $A$ with the member of $P$ containing its old edge. If two members of $A$ met the same member of $P\text{,}$ replacing it by both would enlarge $P\text{,}$ since a type-1 triangle meets $E(P)$ only in its old edge. These pairs and the remaining members of $P$ form $n$ books with $n+a$ pages. Their supports are edge-disjoint, since the new edges of $A$ avoid $O\text{,}$ and every selection of one page per book is a packing of size $n=\nu(G)\text{,}$ hence maximal. Lemma 2.2 gives a transversal with at most $3(n-a)+2a$ edges, that is,

Put $G^{\prime}=G-E(A)$ and $O^{\prime}=O\setminus E(A)\text{.}$ Every type-1 triangle meets $E(A)$ by maximality of $A\text{,}$ so every triangle of $G^{\prime}$ has type $2$ or $3\text{,}$ and $|O^{\prime}|=3n-a\text{.}$ Each remaining transversal of $G$ consists of $E(A)$ and a transversal of $G^{\prime}\text{.}$ Color the new edges of $G^{\prime}$ red and its old edges blue. Then $\mathcal{F}(G^{\prime})$ is the family $\mathcal{F}_{2}$ of type-2 triangles of $G^{\prime}\text{.}$

Choose a packing $P^{\prime}$ in $G^{\prime}$ that maximizes first its number of type-2 members and then its size $m\text{.}$ Let $B^{*}$ be the set of type-2 members of $P^{\prime}$ and put $b=|B^{*}|\text{.}$ Any packing in $\mathcal{F}_{2}$ is a packing in $G^{\prime}\text{,}$ so $B^{*}$ is a maximum packing in $\mathcal{F}_{2}\text{.}$ The new edges of $P^{\prime}$ are the new edges of the members of $B^{*}\text{,}$ one for each. Let $N$ be their set, so that $R(B^{*})=N$ and $|N|=b\text{.}$ Since $A\cup P^{\prime}$ is a packing in $G\text{,}$ we have $a+m\leq n\text{.}$ The choice of $P^{\prime}$ makes every packing in $G^{\prime}$ with $m$ members, $b$ of them of type $2\text{,}$ maximal in $G^{\prime}\text{:}$ adding a triangle would give a packing with at least $b$ type-2 members and $m+1$ members.

Let $B(P^{\prime})$ be the set of old edges of $P^{\prime}\text{,}$ and put

the family of type-2 triangles of $G^{\prime}$ whose old edges avoid $E(P^{\prime})\text{.}$ Since $B(B^{*})\subseteq B(P^{\prime})\text{,}$ we have $\mathcal{S}\subseteq(\mathcal{F}_{2})_{B^{*}}=\mathcal{F}(G^{\prime}-B(B^{*}))\text{,}$ and since $B^{*}$ is a maximum packing in $\mathcal{F}_{2}\text{,}$ the red edge of every member of $\mathcal{S}$ lies in $R(B^{*})=N\text{.}$ Choose a maximum packing $Q$ in $\mathcal{S}\text{,}$ put $c=|Q|\text{,}$ and let $h$ be the number of members of $Q$ whose red edge is private in $\mathcal{S}\text{.}$

The second transversal combines books formed by $B^{*}$ and $Q$ with a random bipartition. Pair each member of $Q$ with the member of $B^{*}$ containing its red edge. No member of $B^{*}$ is paired twice, as $Q$ is a packing. These pairs and the unpaired members of $B^{*}$ form $b$ books, whose supports are edge-disjoint since the old edges of $Q$ avoid $E(P^{\prime})\text{.}$ Every selection of one page per book consists of $b$ type-2 triangles and is therefore a maximum packing in $\mathcal{F}_{2}\text{.}$ Let $W$ be the set of old edges of the one-page books, so $|W|=2(b-c)\text{.}$ The set $C$ of Lemma 2.2 for these books lies in $W\cup N\text{,}$ since spines are edges of $N$ and a one-page book has its old edges in $W$ and its new edge in $N\text{.}$

Assign each vertex of $G^{\prime}$ a bit, independently and uniformly at random, and call an edge crossing if its ends receive different bits. Select $W$ and every non-crossing edge of $O^{\prime}\text{,}$ then add the new edge of each triangle of $G^{\prime}$ not yet met. A type-3 triangle has two vertices with the same bit and hence a non-crossing old edge, so the selected edges meet every triangle of $G^{\prime}\text{.}$ Their expected number is $|W|+\frac{1}{2}(|O^{\prime}|-|W|)$ plus the expected number of added new edges, which we bound in two parts.

A new edge is added only if both old edges of its triangle are crossing, and then it is non-crossing. Each edge of $N$ is non-crossing with probability $\frac{1}{2}\text{,}$ so the expected number of added edges in $N$ is at most $\frac{b}{2}\text{.}$

Now let an edge $xy\notin N$ be added as the new edge of a type-2 triangle $T$ not yet met. Then $T$ contains no edge of $N$ and avoids $W\text{,}$ hence avoids $C\text{,}$ and Lemma 2.2 for these books and $\mathcal{F}_{2}$ shows that $T$ is $uxy$ or $vxy$ for a two-page book $\{uvx,uvy\}$ with $uvx\in B^{*}$ and $uvy\in Q\text{.}$ The two edges that $T$ shares with the pages are old, so its new edge $xy$ is the opposite edge of the book. Since $uvy\in\mathcal{S}\subseteq(\mathcal{F}_{2})_{B^{*}}$ and $xy$ is a red edge outside $R(B^{*})=N\text{,}$ Lemma 2.1 shows that $uv$ is private in $(\mathcal{F}_{2})_{B^{*}}\text{,}$ hence in $\mathcal{S}\text{,}$ so $uvy$ is one of the $h$ members of $Q$ with a private red edge. Such a book contributes an added edge only if $uxy$ or $vxy$ is not yet met, which requires $x$ and $y$ to receive the same bit and $u$ or $v$ a different one. As $u,v,x,y$ are distinct, this has probability $\frac{1}{2}-\frac{1}{8}=\frac{3}{8}\text{.}$ Distinct added edges come from distinct books, as each book has one opposite edge, so the expected number of added edges outside $N$ is at most $\frac{3}{8}h\text{.}$ The expected total is at most

so some assignment of bits gives a transversal of $G^{\prime}$ of at most this size. Adding $E(A)$ and using $|O^{\prime}|=3n-a$ gives

For the third transversal, we add a third page to some of these books and include the remaining members of $P^{\prime}\text{.}$ Choose a maximum packing $Q_{1}$ in $\mathcal{S}_{Q}=\mathcal{F}(G^{\prime}-B(P^{\prime})-B(Q))$ and put $d=|Q_{1}|\text{.}$ The red edge of each member of $Q_{1}$ lies in $R(Q)\text{,}$ and distinct members of $Q_{1}$ have distinct red edges. Add each member of $Q_{1}$ as a third page to the book whose spine is its red edge, and add the members of $P^{\prime}\setminus B^{*}$ as one-page books. The old edges of $Q_{1}$ avoid $E(P^{\prime})\cup E(Q)\text{,}$ so the supports remain edge-disjoint. Every selection of one page per book is a packing in $G^{\prime}$ with $m$ members, $b$ of them of type $2\text{,}$ hence maximal in $G^{\prime}\text{.}$ These $m$ books have $m+c+d$ pages, so Lemma 2.2 gives a transversal of $G^{\prime}$ of size at most $3m-c-d\text{.}$ Adding $E(A)$ and using $a+m\leq n$ gives

The fourth transversal consists of $E(A)\text{,}$ the old edges of $P^{\prime}\text{,}$ and a transversal of $\mathcal{S}\text{.}$ The first two sets have at most $3a+3m-b\leq 3n-b$ edges. A triangle avoiding them lies in $G^{\prime}-B(P^{\prime})$ and is not of type $3\text{,}$ since a type-3 triangle avoiding $B(P^{\prime})$ would avoid $E(P^{\prime})$ and could be added to $P^{\prime}\text{.}$ So it belongs to $\mathcal{S}\text{.}$ Lemma 2.3 applied to $G^{\prime}-B(P^{\prime})\text{,}$ with $Q\text{,}$ $Q_{1}\text{,}$ $c\text{,}$ $d\text{,}$ $h$ in the roles of $P\text{,}$ $Q\text{,}$ $p\text{,}$ $q\text{,}$ $u\text{,}$ gives $\tau(\mathcal{S})\leq\frac{9}{4}c+\frac{3}{2}d-\frac{1}{4}h$ by Equation 2, so

Multiply Equations 3, 4, 5 and 6 by $20,8,19,12\text{,}$ respectively, and add. The coefficients of $a,b,c,h$ cancel, giving