# Online Talk: Ruth Luo

Time: Thursday, Mar 30, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: Ruth Luo, University of South Carolina
Title: A hypergraph analog of Dirac’s Theorem for 2-connected graphs

Abstract: Every graph with minimum degree $k \geq 2$ contains a cycle of length at least $k+1.$ Dirac proved that if the graph is also 2-connected then in fact we can find a cycle of length at least $min\{2k, n\}$. We prove a hypergraph version of this theorem: a minimum degree condition that forces the existence of long Berge cycles in 2-connected, uniform hypergraphs. This is joint work with Alexandr Kostochka and Grace McCourt.

# Online Talk: Matthew Kroeker

Time: Thursday, Mar 16, 3pm ET (beware of U.S./Canada time change on Mar 12!)
Zoom: https://uwaterloo.zoom.us/j/94977150195
pwd=LzRHN3NVcWtGbWlOVGNmakJQenF1Zz09

Passcode: kroeker1

Speaker: Matthew Kroeker, University of Waterloo
Title: Unavoidable Flats in Matroids Representable over a Prime Field

Abstract: The Sylvester-Gallai Theorem says that every rank-3 real-representable matroid contains a two-point line. A high-dimensional generalization of this result, due to Hansen, implies that every simple real-representable matroid of sufficiently high rank contains a rank-k independent flat. One only needs to look as far as the binary projective plane to see that such a result cannot hold for the class of matroids representable over a finite field. In light of this, we ask whether it is possible to determine a small list of “unavoidable” rank-k flats guaranteed to exist in a simple GF(q)-representable matroid of sufficiently high rank. We will answer this question for the case of prime fields: in particular, we show that, for any prime p and positive integer k, any simple GF(p)-representable matroid of sufficiently high rank contains a rank-k flat which is either independent, or is a projective or affine geometry. This is joint work with Jim Geelen.

# Tuza’s Conjecture

One of my favourite open problems in Tuza’s Conjecture, which relates triangle packings and triangle hitting sets in graphs.

Let $G$ be a graph. A triangle packing is a set of triangles in $G$ no two of which have an edge in common. The maximum size of a triangle packing is called the triangle packing number of $G$, for which we write $\nu(G)$.

A triangle-hitting set is a subset $X \subseteq E(G)$ with the property that removing $X$ from $G$ results in a triangle-free graph. We write $\tau(G)$ for the size of the smallest triangle-hitting set in $G$.

A straightforward argument shows that $\nu(G) \le \tau(G) \le 3\nu(G)$. Tuza conjectured that the upper bound can be improved.

Conjecture (Tuza, 1981): $\tau(G) \le 2\nu(G)$ for all graphs $G$.

In other words, a graph without $t+1$ edge-disjoint triangles can be made triangle-free by removing at most $2t$ edges.

The factor 2 in the conjecture, if true, is best possible: $K_4$ and $K_5$ are examples for which $\tau(G) = 2\nu(G)$.

# Geometric Tuza’s Conjecture

Tuza’s Conjecture, being formulated in terms in terms of edges and triangles only, can be naturally generalised to matroids. A triangle in a matroid $M$ is a restriction isomorphic to $U_{2,3}$. We define $\nu(M)$ to be the maximum number of disjoint triangles in $M$, and $\tau(M)$ to be the minimum size of a set $X$ such that $M\backslash X$ does not contain any triangles.

Unfortunately, the geometric version of Tuza’s Conjecture fails for matroids in general: For the Fano plane, $F_7 = \mathrm{PG}(2,2)$, we have $\tau(F_7) = 3$ and $\nu(F_7) = 1$.

Kazu Nomoto and I believe that, at least for binary matroids, the Fano plane is the only obstruction to a geometric version of Tuza’s Conjecture.

Conjecture (Nomoto–Van der Pol, 2021): Let $M$ be a simple binary matroid with no restriction isomorphic to $F_7$. Then $\tau(M) \le 2\nu(M)$.

As graphic matroids do not have restrictions isomorphic to $F_7$, the geometric version of Tuza’s conjecture implies the graphic version. We verified the conjecture for cographic matroids and several other classes of matroids.

# Projective planes

Moving beyond binary matroids, one could ask if Tuza’s Conjecture holds for other classes of matroids. Here, we ask if it holds for projective planes. We’ve already seen that the conjecture fails for the Fano plane. It fails spectacularly for all other finite projective planes as well. This result is closely related to classical results in projective geometry.

A finite projective plane is a set system $\Pi = (E,\mathcal{L})$ — the elements of $E$ are called points, and the elements of $\mathcal{L}$ are called lines — with the following properties:

1. Any pair of distinct points is contained in exactly one line;
2. Any pair of lines intersects in exactly one point; and
3. There are four points such that no line contains more than two of them.

For each finite projective plane $\Pi$ there is a number $q \ge 2$, the order of $\Pi$, such that every point is contained in $q+1$ lines, and every line contains $q+1$ points. It follows that a projective plane of order $q$ contains exactly $q^2 + q + 1$ points.

Well-known examples are the Desarguesian planes $\mathrm{PG}(2,q)$, whose points and lines are the 1- and 2-dimensional subspaces of $\mathbb{F}_q^3$, respectively, but there are other examples as well.

# Arcs

The lines in $\mathcal{L}$ form the collection of hyperplanes of a rank-3 matroid on $E$, so it makes sense to talk of $\tau(\Pi)$ and $\nu(\Pi)$ for finite projective planes $\Pi$.

An arc in $\Pi$ is a set $A$ of points such that no line intersects $A$ in more than two points. In our terminology, $A$ is a triangle-free restriction of $\Pi$. (Confusingly, the term triangle is also used for an arc of size 3, which is the opposite of our use of the term.)

The following result is well known in projective geometry.

Lemma: Let $\Pi$ be a projective plane of order $q$ and let $A$ be an arc. Then $|A| \le q+2$. If $q$ is odd, then $|A| \le q+1$.

Proof. Let $p \in A$ be any point, and let $\ell_1, \ell_2, \ldots, \ell_{q+1}$ be an enumeration of the lines incident with $p$. Each point in $\Pi$ is on one of those $q+1$ lines, and each line contains at most one point from $A$ other than $p$, so $|A| \le 1 + (q+1)$.

To prove the second bound, suppose for the sake of contradiction that $q$ is odd and $|A| = q+2$. Every line of $\Pi$ intersects $A$ in either $0$ or $2$ points; this is in particular true for all lines through a fixed point $p \not\in A$. It follows that $|A|$ is twice the number of lines incident with $p$ that intersect $A$, so $|A|$ must be even: a contradiction, so $|A| < q+2$. $\Box$

Arcs of size $q+1$ are called ovals, while arcs of size $q+2$ are called hyperovals. Constructions for ovals and hyperovals exist for the planes $\mathrm{PG}(2,q)$; Segre proved that in $\mathrm{PG}(2,q)$ of odd order, all ovals are nondegenerate conic sections.

By the lemma, sets containing more than $q+2$ points must contain a triangle, so $\tau(\Pi)$ is large.

Lemma: Let $\Pi$ be a projective plane of order $q$. If $q$ is even, then $\tau(\Pi) \ge q^2 – 1$. If $q$ is odd, then $\tau(\Pi) \ge q^2$.

Trivially, $\nu(\Pi) \le \frac{1}{3}(q^2+q+1)$. This is sufficient to show that Tuza’s conjecture fails for projective planes of sufficiently large order, as $\tau(\Pi) \sim 3\nu(\Pi)$ as $q \to \infty$.

The trivial upper bound on $\nu$ is correct, as can be shown by a simple construction.

Lemma: Let $\Pi$ be a projective plane of order $q \ge 3$. Then $\Pi$ can be decomposed into disjoint triangles and at most one point. Consequently, $\nu(\Pi) = \lfloor\frac{1}{3}(q^2+q+1)\rfloor$.

Proof. The exact construction depends on the remainder of $q$ modulo 3. Here, we only give the construction for the case $q = 3k+1$; the case $q = 3k+2$ allows a similar construction, while the case $q=3k$ is easier. See the figure following the proof for an illustration in the case $q=4$.

Let $p \in \Pi$ be any point, and let $\ell_0, \ell_1, \ldots, \ell_q$ be an enumeration of the lines incident with $p$. Let $e \in \ell_0$ be a point distinct from $p$, and let $\ell’ = {e, e’_1, \ldots, e’_q}$ and $\ell” = {e, e”_1, \ldots, e”_q}$ be two distinct lines incident with $e$ such that $e’_i, e”_i \in \ell_i$ for $i = 1, 2, \ldots, q$.

Consider the $(q+2)/3$ disjoint triangles

$\{e’_2, e’_3, e’_4\}, \{e’_5, e’_6, e’_7\}, \ldots, \{e’_{q-2}, e’_{q-1}, e’_q\},\quad\text{and}\quad\{e,e”_1, e”_2\}$,

and let $Z$ be the set of all points in those triangles. $Z$ contains exactly one point on each of the lines $\ell_i$, except that it contains two points of $\ell_2$. It follows that each of the sets $\ell_i\setminus (Z \cup {e})$ (for $i \neq 2$) and $\ell_2\setminus Z$ can be partitioned into triangles. $\Box$

It follows from the above results that

$\frac{\tau(\Pi)}{\nu(\Pi)} \ge \frac{q^2-1}{\frac{1}{3}(q^2+q+1)} \ge \frac{15}{7} > 2$

whenever the order $q$ of $\Pi$ is at least 4. For the (unique) projective geometry $\Pi = \mathrm{PG}(2,3)$ of order $q = 3$, we have $\tau(\Pi) = 9$ and $\nu(\Pi) = 4$, while for the (unique) projective geometry $\Pi = \mathrm{PG}(2,2)$ or order $q=2$ we have $\tau(\Pi)=3$ and $\nu(\Pi) = 1$, so Tuza’s Conjecture fails for all finite projective planes.

# Online Talk: Raphael Steiner

Abstract: Hadwiger’s conjecture, among the most famous open problems in graph theory, states that every graph that does not contain $K_t$ as a minor is properly (t1)-colorable. The purpose of this work is to demonstrate that a natural extension of Hadwiger’s problem to hypergraph coloring exists, and to derive some first partial results and applications. Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph $H_1$ is a minor of a hypergraph $H_2$, if a hypergraph isomorphic to $H_1$ can be obtained from $H_2$ via a finite sequence of vertex- and hyperedge-deletions, and hyperedge contractions. We first show that a weak extension of Hadwiger’s conjecture to hypergraphs holds true: For every positive integer t, there exists a finite (smallest) integer h(t) such that every hypergraph with no $K_t$-minor is h(t)-colorable, and we prove $$\lceil 3/2(t-1) \rceil \le h(t) \le 2g(t)$$ where g(t) denotes the maximum chromatic number of graphs with no $K_t$-minor. Using the recent result by Delcourt and Postle that $g(t) = O(t \log\log t)$, this yields $h(t) = O(t\log\log t)$. We further conjecture that $h(t) = \lceil 3/2(t-1) \rceil$, i.e., that every hypergraph with no $K_t$-minor is $\lceil 3/2(t-1) \rceil$-colorable for all t, and prove this conjecture for all hypergraphs with independence number at most 2. By considering special classes of hypergraphs, the above additionally has some interesting applications for ordinary graph coloring, such as:
-graphs of chromatic number $Ckt\log\log t$ contain $K_t$-minors with k-edge-connected branch-sets,-graphs of chromatic number $Cqt\log\log t$ contain $K_t$-minors with modulo-q-connected branch sets,-by considering cycle hypergraphs of digraphs we recover known results on strong minors in digraphs of large dichromatic number as special cases.