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.
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.
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)$.
$K_5$ contains two edge-disjoint triangles (pink) and can be made triangle-free by removing the four dashed edges.
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$.
$F_7$ does not contain two disjoint triangles and can be made triangle-free by removing the three empty elements.
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:
Any pair of distinct points is contained in exactly one line;
Any pair of lines intersects in exactly one point; and
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$.
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$
A decomposition of $\mathrm{PG}(2,4)$ into seven triangles.
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.
