The Discrete Math Seminar at Iowa State University is held on Thursdays at 2:10-3:00 pm in Carver 401 .
Some old talks are available on YouTube.
The seminar is organized by Grace McCourt and Bernard Lidický.
Mar 5 Shira Zerbib
Title: Embedding polytopes and coloring graphs using equivariant topology.
Abstract: We will discuss applications of equivariant topology to problems concerning embeddings of polytopes in the Euclidean space, and present new generalizations of Tverberg’s theorem and the Borsuk-Ulam theorem. We will also see the connection of these results to the chromatic numbers of graphs.
Mar 12 Tung Nguyen (zoom)
Title: On gcd-graphs over a finite ring
Abstract: Gcd-graphs represent an interesting and historically important class of integral graphs. Since the pioneering work of Klotz and Sander, numerous incarnations of these graphs have been explored in the literature. In this talk, we will introduce a general notion of gcd-graphs that works for an arbitrary finite ring. We investigate the connectivity and diameter of these graphs. Additionally, when the ring is a finite Frobenius ring, we give an explicit description of the spectra of these gcd-graphs using the theory of Ramanujan sums. Our method provides a unified treatment of various results in the literature. This is based on various joint works with Nguyen Duy Tan.
Mar 19 (spring break)
Mar 26 David James
Apr 1-2 Francis Su (Aggie Ho Memorial Lecture Series and Departmental Colloquium)
Apr 9 Thiago Holleben
Apr 16
Apr 23
Apr 30 Sam Spiro
May 7
May 14 (exam week)
Jan 29 Ramón Iván García Alvarez
Title: Density of rainbow triangles and properly colored $K_4$’s
Abstract: T. W. Chao and H.-H. H. Yu showed in 2023 that a graph with $R$ red, $G$ green, and $B$ blue edges has at most $(2RGB)^{1/2}$ rainbow triangles. They proved this bound using entropy. In this talk, I will present a fully computer-free flag-algebra proof of their result, along with a translation of the argument into a classical counting proof. The ideas in our proof lead to an even shorter entropy proof. In addition, I will discuss a similar result that gives a sharp upper bound on the number of properly $3$-edge-colored $K_4$'s in graphs with $R$ red, $G$ green and $B$ blue edges. Joint work with József Balogh, Peter Bradshaw and Bernard Lidický.
Feb 5 Owen Henderschedt
Title: Some recent progress on total colorings and total coloring extensions in planar graphs
Abstract: A total coloring of a graph is an assignment of colors to both vertices and edges such that any pair of adjacent or incident objects (vertex–vertex, vertex–edge, or edge–edge) receive different colors. In the 1960s, Vizing and, independently, Behzad conjectured what is now known as the Total Coloring Conjecture, which asserts that every graph G admits a total coloring using at most \Delta(G)+2 colors, where \Delta(G) is the maximum degree of G. In this talk, I will survey some of the partial results toward this conjecture and discuss recent progress on extension problems in planar graphs. In particular, I will focus on questions of the following type: given a precolored subgraph, when can this coloring be extended to a total coloring of the entire graph? This is joint work with Jessica McDonald and Songling Shan.
Feb 10 Daniel Kráľ (colloquium, Carver 0001, 1:10pm)
Title: Analytic approach to extremal combinatorics
Abstract: Analytic tools to represent and study large discrete structures provided by the theory of combinatorial limits led to new views on a wide range of topics in mathematics and computer science. In this talk, we will briefly introduce the theory of combinatorial limits and showcase its methods on specific problems from Ramsey theory - Ramsey theory studies the existence of well-behaved substructures as given in the following classical statement proven by Ramsey in 1930: if N is sufficiently large, then for any partition of k-tuples of N points into finitely many classes, there exist n points such that all k-tuples formed by these n points belong to the same class. We will study quantitative versions of Ramsey type statements and present a solution of a 30-year-old problem on the existence of high chromatic graphs with small Ramsey multiplicity. In relation to general questions on the interplay of combinatorial limits and extremal combinatorics, we will present, among others, a counterexample to a conjecture of Lovász on finitely forcible optima of extremal problems.
Feb 19 Filip Kučerák
Title: Sidorenko property and forcing in regular tournaments
Abstract: We say that a graph has the Sidorenko property if it holds that the asymptotic minimizer of the number of copies of H among graphs with edge density p is a random graph, i.e., a graph where we include each edge independently with probability p.
A famous conjecture of Sidorenko and Erdős-Simonovits states that a graph has the Sidorenko property if and only if it is bipartite. The claim has been verified for various graph classes, such as even cycles, complete graphs, or trees; however, a general resolution seems out of reach.
In this talk, we survey the Sidorenko property in the setting of tournaments. In contrast to the graph setting, a complete characterization of tournaments that have the so-called tournament Sidorenko property is known. Noel, Ranganathan and Simbaqueba have shown, in their work on quasirandomness, that by requiring the random tournament to be the asymptotic minimizer only among the regular tournaments, we arrive at a weaker property. In their work, they present a finite set of tournaments satisfying only this weaker notion and leave the classification of such tournaments as an open problem. In joint work with Kráľ, Krnc, Lidický and Volec, we give a complete characterization of this set.
Feb 26 Ruoyu Meng
Title: When does quantum help function computation with side-information? A graph-theoretic approach
Abstract: We study zero-error function computation with side information: Alice observes a random variable X, Bob observes correlated side information Y, and Bob wants to compute a prescribed function f(X,Y) with absolutely no error while Alice sends a message over an error-free channel. A classical way to capture the zero-error constraint is via a confusion graph whose vertices represent Alice’s symbols and edges represent pairs that Bob cannot distinguish given Y; in the fixed-length setting, the minimum communication rate is governed by the growth of the chromatic number of an appropriate m-instance confusion graph. We then consider a quantum variant where Alice is allowed to transmit quantum states; in this case, the relevant graph parameter becomes the orthogonal rank of the complement of the m-instance confusion graph, which can be significantly smaller than the chromatic number and thus yield a quantum advantage. We illustrate the resulting range of behaviors with examples, including cases where a one-shot quantum advantage disappears in the asymptotic regime. Time permitting, we briefly discuss related quantum graph parameters such as the quantum chromatic number.
Mar 9-16 57th Southeastern International Conference on Combinatorics, Graph Theory & Computing (Boca)
Mar 27-29 Graduate Students Combinatorics Conference (Chicago)
May 1-3 Great Plains Combinatorics Conference (Lawrence)
May 2-3 The 11th Lake Michigan Workshop on Combinatorics and Graph Theory (Notre Dame)
May 16-17 34th Cumberland Conference on Combinatorics, Graph Theory, and Computing (Auburn)
Jun 9 to 11 EXCILL 5 (Urbana-Champaign)
Jun 22-25 SIAM Conference on Discrete Mathematics (San Diego)
July 27-Aug 6 Graduate Research Workshop in Combinatorics (GRWC 2026) (Iowa State)
Aug 5-8 MAA Mathfest (Boston)
Aug 10-14 Graduate Workshop in Logic and Combinatorics (Chicago)
Aug 19-21 Graph Drawing (Ontario, Canada)