Discrete Seminar

The Discrete Math Seminar at Iowa State University is held on Fridays at 3:20-4:10 pm in Carver 128 .

Some old talks are available on YouTube.

The seminar is organized by Bryan Curtis, Emily Heath, and Bernard Lidický.

Spring 2024

Title: Graphs with No Long Claws: From Structure to Quasi-Polynomial Time Algorithm

Abstract: Hereditary graphs, i.e., graph classes closed undertaking induced subgraphs, are one of the most fundamental objects to study in graph theory. Hereditary graph class $\mathcal{G}$ is characterized by a (potentially infinite) list of forbidden induced subgraphs $\mathcal{H}$. We call $G\in\mathcal{G}$ $\mathcal{H}$-\emph{free} in that case. Many computationally hard problems become tractable on various $\mathcal{H}$-free graphs. Surprisingly, for many core problems in graph theory, such as 3-coloring or maximum independent set, the complexity is not yet fully determined even when restricted to classes characterized by a single forbidden induced subgraph $H$. We denote such as $H$-\emph{free} graphs. This talk will focus on the \emph{maximum independent set} (MIS) problem, i.e., finding a maximum edgeless subset of vertices. It is well-known that the MIS problem is NP-complete on $H$-free graphs unless $H$ is a (disjoint union of) a path on $t$ vertices $P_t$ and/or a \emph{subdivided claw} $S_{t,t,t}$. That is a graph created from three paths on $t$ edges by identifying one endpoint of each path into a single vertex. Recently, a quasi-polynomial algorithm for $P_t$-free graphs was developed, proving that a vertex in a Gyárfás' path provides good progress for the branching algorithm. However, it was unclear what structure could be exploited to make good progress on $S_{t,t,t}$-free graphs. We developed a useful tool that provides us with a logarithmically small set $X$ such that graph with the neighborhood of $X$ removed admits an extended strip decomposition structure with multiplicatively smaller particles, which could be used in a recursion yielding, for example, a quasi-polynomial time approximation scheme. We further extended the structure given above to all vertices of $G$ unless we obtained a small balanced separator. This is already a good enough structure to be used together with involved branching to finally obtain a quasi-polynomial time algorithm for $S_{t,t,t}$-free graphs. By this, we complete the dichotomy of the complexity of MIS in $H$-free graphs into NP-hard cases and cases solvable in quasi-polynomial time.

Joint work with Peter Gartland, Konrad Majewski, Jana Masaříková, Daniel Lokshtanov, Karolina Okrasa, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski, Marek Sokołowski.


Title: Dominant Patterns in Graph Homomorphisms 

Abstract: A central notion at the intersection of combinatorics and statistical physics is graph homomorphism. We say a function $f: V(G)\rightarrow V(H)$ is a homomorphism from $G$ to $H$, if the map preserves adjacencies, i.e., $(f(u), f(v))\in E(H)$ for all $(u,v)\in E(G)$. From the perspective of combinatorics, graph homomorphisms provide a unified framework for many important graph theory concepts; at the same time, they naturally arise in the study of spin models and their critical phenomena within statistical physics. 

In this talk, I will discuss some recent studies that reveal, for certain $G$ and $H$, a typical graph homomorphism exhibits a strong concentration behavior. More specifically, there exist dominant patterns, such that almost all homomorphisms aligns with one of them, albeit with small defects. Consequently, this leads to numerous important enumeration results in combinatorics. Towards the end of the talk, I will also briefly mention some other interesting studies in my research program.


Title: Chain Poset Saturation 

Abstract: The extremal number of a graph G is the maximum number of edges that can exist on n vertices without containing a subgraph isomorphic to G. The dual problem of this is the saturation number, the minimum number of edges such that the graph does not contain G, but where adding any edge forces G to exist as a subgraph.

We can extend this concept to the environment of partially ordered sets, and various results exist for both extremal and saturation numbers for certain poset structures. In this talk, I will discuss the saturation number of one family of posets in particular, the chains of length k, defined as a collection of k subsets A_i such that A_i is a proper subset of A_{i+1} for all 1 <= i <= k.


Title: On lower bounds for co-Sidon pairs

Abstract: Two sets $A,B \subseteq \{0,1\}^d$ are co-Sidon if $|A||B| = |A + B|$. We present a general method for improving existing co-Sidon pairs. This method has information theoretical applications regarding the zero-error capacity region for uniquely decodable codes in binary adder channels. Our results improve the previously known lower bounds in this setting as well. 

Joint work with József Balogh, The Nguyen, Patric Östergård, and Ethan White.


Title: On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

Abstract: We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number $\mis(n)$ of maximal independent sets in an $n$-vertex graph was determined by Miller and Muller and independently by Moon and Moser. The maximum number $\mis_\bigtriangleup(n)$ of maximal independent sets in an $n$-vertex triangle-free graph was determined by Hujter and Tuza. We give a common generalization of these results by determining the maximum number $\mis_t(n)$ of maximal independent sets in an $n$-vertex graph containing no induced triangle matching of size $t+1$. This also improves a stability result of Kahn and Park on $\mis_\bigtriangleup(n)$. Our second result is a new (short) proof of a second stability result of Kahn and Park on the maximum number $\mis_{\bigtriangleup,t}(n)$ of maximal independent sets in $n$-vertex triangle-free graphs containing no induced matching of size $t+1$. Joint work with Cory Palmer (Montana).


Title: New Lower Bounds on Crossing Numbers of $K_{m,n}$ from Permutation Modules and Semidefinite Programming

Abstract: In this talk, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph $K_{m,n}$, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624].

We exploit the full symmetry of the problem by developing a block-diagonalization of the underlying matrix algebra, and use it to improve bounds on several concrete instances. Our results imply that $\mathrm{cr}(K_{10,n}) \geq  4.87057 n^2 - 10n$, $\mathrm{cr}(K_{11,n}) \geq 5.99939 n^2-12.5n$, $\mathrm{cr}(K_{12,n}) \geq 7.25579 n^2 - 15n$, $\mathrm{cr}(K_{13,n}) \geq 8.65675 n^2-18n$ for all~$n$. The latter three bounds are computed using a new relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite. Our lower bound on $K_{13,n}$ implies that for each fixed $m \geq 13$, $\lim_{n \to \infty} \text{cr}(K_{m,n})/Z(m,n) \geq 0.8878 m/(m-1)$. Here $Z(m,n)$ is the Zarankiewicz number: the conjectured crossing number of $K_{m,n}$. 

This talk is based on joint work with Sven Polak, which recently appeared in Mathematical Programming (https://doi.org/10.1007/s10107-023-02028-1).


Title: Correspondence coloring with locally sparse covers

Abstract: We introduce a more general notion of local sparsity by defining graphs $G$ to be (k, F)$-locally-sparse for some graph $F$ if for each vertex $v \in V(G)$, the subgraph induced by its neighborhood contains at most $k$ copies of $F$.  We show that for every bipartite graph $F$, if $G$ is $(k, F)$-locally-sparse, then the correspondence chromatic number of $G$ is at most $8\Delta /\log\left(\Delta k^{-1/|V(F)|}\right)$. In fact, our results hold when the local sparsity constraint is on the correspondence cover of $G$ as opposed to $G$ itself.

This is based on joint work with James Anderson and Aiya Kuchukova.


Title: Equitable Coloring in 1-Planar Graphs

Abstract: An r-coloring of a graph G is an assignment of colors from {1, . . . , r} to the vertices of G such that no two adjacent vertices receive the same color. An r-coloring is equitable if the sizes of the color classes differ by at most 1. A result of Zhang shows that every 1-planar graph G with ∆(G) ≥ 17 has an equitable ∆(G)-coloring. We strengthen the bound on the maximum degree to ∆(G) ≥ 13.


Title: Crossing numbers of complete bipartite graph

Abstract: In this talk we explore applications of flag algebras to crossing numbers. Flag algebras is a framework developed by Razborov in 2007. It enables to find proofs that are based on sum of squares of densities of small substructures. It allows for computer assisted while utilizing semidefinite programming The number of crossings in a fixed drawing of a graph G can be counted by checking every quadruple of vertices and checking if the induce a crossing. This leads to a density problem that can be formulated using flag algebras. In this talk, we introduce the method and visit several applications of the method to crossing numbers.

This is based on joint work with J. Balogh, S. Norin, F. Pfender, G. Salazar, S. Spiro.


Title: A New Characterization of Strongly Chordal Graphs (and why we care)

Abstract: A simple graph G = (V,E) is chordal if every cycle has a chord.  It is strongly chordal if every even cycle of length at least 6 has an even chord.  Strongly chordal graphs have several equivalent characterizations, including Farber’s result that G is strongly chordal if and only if G has a simple (vertex) elimination order if and only if G is chordal and is n-trampoline-free for n at least 3.  We give a new characterization of strongly chordal graphs via a certain edge ordering that is not easily deduced from the known results. 

The motivation comes from the work of June Huh et. al. who recently proved the Dowling-Wilson Top Heavy Conjecture for geometric lattices.  (This result is partially why June Huh was awarded a Fields Medal in 2022.). One of the key tools in the proof is the graded Moebius algebra of a geometric lattice.  We prove that for the lattice of flats of a graphic matroid associated to a graph G, this algebra is Koszul (an algebraic property related to free resolutions) if and only if G is strongly chordal.  The above characterization of strongly chordal graphs grew naturally out of this work, which is joint with Adam LaClaire (Purdue), Matt Mastroeni (ISU), and Irena Peeva (Cornell).


Title: Envy-free distributions in high dimensions

Abstract: In fair partition results, we aim to distribute resources among several competing players.  One family of problems, known as mass partition problems, studies scenarios where we can guarantee that every player agrees that the value of each part is the same.  Another type of results are envy-free partitions, in which each player agrees that they received the best part according to their subjective preferences.  Envy-free partitions are well studied in dimension 1, and often allow us to satisfy more players than those in mass partition results.  In this talk, we discuss common generalizations to both types of results.  We focus on partitions in R^2 with few lines, and partitions in R^d into convex parts.


Title: Triangles in the Plane

Abstract: A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of n points in the plane. Since then a great variety of extremal problems in finite planar point sets have been studied. Here, we look at such questions concerning triangles. Among others we answer the following question asked by Erdős and Purdy almost 50 years ago: Given n points in the plane, how many triangles can be approximate congruent to equilateral triangles?

For our proofs we use hypergraph Turán theory. This is joint work with Balogh and Dumitrescu.


Title: Induced Saturation for Complete Bipartite Posets

Abstract: Given $s,t\in\mathbb{N}$, a complete bipartite poset $\mathcal{K}_{s,t}$ is a poset, whose Hasse diagram consists of $s$ pairwise incomparable vertices in the upper layer and $t$ pairwise incomparable vertices in the lower layer, such that every vertex in the upper layer is larger than all vertices in the lower layer. A family $\mathcal{F}\subseteq2^{[n]}$ is called induced $\mathcal{K}_{s,t}$-saturated if $(\mathcal{F},\subseteq)$ contains no induced copy of $\mathcal{K}_{s,t}$, whereas adding any set from $2^{[n]}\backslash\mathcal{F}$ to $\mathcal{F}$ creates an induced $\mathcal{K}_{s,t}$. Let $\mathrm{sat}^{*}(n,\mathcal{K}_{s,t})$ denote the smallest size of an induced $\mathcal{K}_{s,t}$-saturated family $\mathcal{F}\subseteq2^{[n]}$. It was conjectured that for any fixed $s,t\geqslant2$, $\mathrm{sat}^{*}(n,\mathcal{K}_{s,t})$ is a superlinear function of $n$. When $s=t=2$, this conjecture has been refuted by Keszegh, Lemons, Martin, P\'{a}lv\"{o}lgyi, and Patk\'{o}s. 

In this talk, we shall construct an induced $\mathcal{K}_{s,t}$-saturated family of linear size and hence show that $\mathrm{sat}^{*}(n,\mathcal{K}_{s,t})=O(n)$ for all $s,t\geqslant2$.


Title: Loose Hamiltonian Cycles in 3-graphs

Abstract: Dirac's Theorem states that for all n > 2, any n-vertex graph G with minimum degree at least n/2 contains a Hamiltonian cycle – that is, a cycle which contains all vertices of G. It is natural to ask for hypergraph extensions of Dirac's Theorem: in an r-uniform hypergraph, what conditions analogous to minimum degree will guarantee the existence of a spanning cycle? Many results exist in this direction, partially because there are multiple natural ways to define both cycles and minimum degree when r > 2. In this talk, our hypergraph analog of minimum degree will be the minimum positive co-degree parameter. 

Given a 3-graph H, the minimum co-degree of H is the largest integer k such that any 2 vertices are contained in at least k 3-edges. The minimum positive co-degree of H is the largest integer k such that whenever 2 vertices are contained in at least one 3-edge, they are contained in at least k 3-edges. Minimum positive co-degree has recently been considered as reasonable analog to minimum degree in r-graphs, and in some cases seems a nicer parameter than minimum co-degree; in particular, many hypergraph analogs to bipartite graphs, blow-ups, and other natural graph constructions have minimum co-degree 0 but maintain high minimum positive co-degree. In this talk, we discuss minimum positive co-degree versions of Dirac's Theorem, focusing on a new result which uses the absorbing method to asymptotically determine the positive co-degree threshold for loose Hamiltonian cycles in 3-graphs. This is joint work with Van Magnan and Ryan Wood.


Title: The Rainbow Connection

Abstract: An edge-coloured graph is said to be rainbow if every edge in the graph has a distinct colour. Given a graph H, an edge-coloured graph G is H-rainbow saturated if G does not contain a rainbow copy of H, but the addition of any non-edge, in any colour, creates a rainbow copy of H. The rainbow saturation number, denoted by rsat(n,H), is the minimum number of edges in an H-rainbow saturated graph on n vertices. We show that, for any non-empty graph H, the rainbow saturation number is linear in n, thus proving a conjecture of Girão, Lewis, and Popielarz. Based on work with Natalie Behague, Tom Johnston, Shoham Letzter, and Natasha Morrison.


Title: Quasirandom Boolean Functions

Abstract: We organize a number of analytic and combinatorial properties of Boolean functions into a hierarchy of equivalence classes in a similar style as  quasi-random graphs, but depending on  `local' parameters. We construct quasi-random Boolean functions that separate different levels of the quasi-random hierarchy. In addition, we will briefly survey various well known notions of pseudo-randomness for Boolean functions and explore their relations to the quasi-random hierarchy