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ý.
Aug 28 - Introduce yourself
Sep 4 - Sydney Miyasaki
Title: Phylogenetic Conflicts
Abstract: In computational genetics, the perfect phylogeny model is a simple but fundamental model of how speciation occurs under Darwinian evolution. Reconstructing an evolutionary history from observed characteristics of living species under this model is a well-studied and useful technique in the study of evolutionary lineages. However, this model does not always agree with data. In particular, a certain "three-gamete condition" captures all such disagreements. In this work, we use tools from extremal graph theory, namely flag algebras, to determine the asymptotically maximum number of such three-gamete conflicts that any set of observational data may have. In addition, we provide an asymptotic characterization of such observational data. This talk is based on joint work with Oliver Eulenstein, Anastasia Halfpap, Bernard Lidický, Florian Pfender, Jan Volec.
Sep 11 - Matt Burnam
Title: Spectrum of the q-Laplacian of a graph
Abstract: Given a finite graph G and a real number q, then q-Laplacian of G is the matrix qD + A where D is the diagonal degree matrix and A the adjacency matrix. The q-Laplacian is a generalization of several well-studied graph matrices: the adjacency matrix (q=0), the negative of the Laplacian (q=-1), and the signless Laplacian (q=1). Notably, the signless Laplacian is positive semi-definite and it relates to the line graph of G. We generalize this to the q-Laplacian for q = 1/(n-1). A graph is called K_n-decomposable if its edge set can be partitioned into edge-disjoint copies of K_n. The K_n-line graph of G is the line graph of the hypergraph whose edges are the disjoint copies of K_n. We show that the 1/(n-1)-Laplacian is positive semi-definite for K_n-decomposable graphs, and that its eigenvalues correspond to the eigenvalues of the K_n-line graph of G.
Sep 18 - Bernard Lidický
Title: Hypergraph Turán Problems
Abstract: Hypergraph Turán Problems became more approachable due to flag algebras. In this talk we will first focus on tight cycles without an edge. A tight k-cycle minus an edge C_k^- is the 3-graph on the vertex set [k], where any three consecutive vertices in the string 123...k1 form an edge. We show that for every k >= 5, k not divisible by 3, the extremal density is 1/4. Moreover, we determine the extremal graph up to O(n) edge edits. The proof is based on flag algebra calculations.
Then we describe new developments in solving large semidefinite programs that allows for improving several other bounds on Turán densities.
This talk is based on joint work with Connor Mattes, Florian Pfender and Jan Volec.
Sep 25 - Coy Schwieder
Title: Odd Ramsey numbers of bipartite graphs using conflict-free hypergraph matchings
Abstract: Given a (hyper)graph $G$ and a sub(hyper)graph $H$ of $G$, the odd Ramsey number $r_{odd}(G,H)$ is the minimum number of colors needed to edge-color $G$ so that every copy of $H$ intersects some color class in an odd number of edges. Generalizing a result of Bennett, Heath, and Zerbib, in this talk we discuss $r_{odd}(K_{n,n}, K_{2,t}) \leq \frac{n}{t} + o(n)$ for all $t \geq 2$ using a version of the conflict-free hypergraph matching method.
Oct 2 - no seminar
Oct 9 - Alec Helm (University of South Carolina) [Zoom]
Title: A Quantitative Kuratowski Theorem
Abstract: A planar graph is a graph which can be drawn in the plane such that edges do not intersect each other. This nice graph family is described by Kuratowski's celebrated 1930's theorem which states that a finite graph is planar if and only if it contains no subgraphs which are subdivisions of a K_5 or a K_{3,3}; we call such graphs Kuratowski subgraphs. The notion of crossing number of a graph allows for the quantification of a graph's failure to be planar. The crossing number of a graph is the minimum number of edge intersections needed to draw the graph in the plane, and thus a graph is planar if and only if its crossing number is zero. In this context, a finite graph has positive crossing number if and only if it contains a Kuratowski subgraph. We ask the following question: can we bound the crossing number of graphs with a fixed number of Kuratowski subgraphs. We answer this in the affirmative and answer some questions about the crossing number of graphs with exactly k Kuratowski subgraphs for various k.
Oct 16 - John Byrne (University of Delaware)
Title: Nonabelian Sidon sets and extremal problems on digraphs
Abstract: An Sk-set is a subset of a group whose k-tuples have distinct products. We give explicit constructions of large Sk-sets in the groups Sym(n) and Alt(n) and of large S2-sets in Sym(n) x Sym(n) and Alt(n) x Alt(n), as well as some probabilistic constructions for 'nice' groups. We also give various upper bounds; in particular, if k is even and the group has a normal abelian subgroup with bounded index then the trivial upper bound can be improved by some constant multiplicative factor. Next, we describe some connections between Sk-sets and extremal graph theory. We determine up to a constant factor the largest possible minimum outdegree in a digraph without certain directed cycles. Interestingly, the extremal minimum outdegree is much larger for any one of these cycles than for the whole family. We count the directed Hamilton cycles in one of our constructions to improve the upper bound for a problem on Hamilton paths posed by Cohen, Fachini, and Körner. This talk is based on joint work with Michael Tait.
Oct 23 - Swaroop Hegde (University of Georgia) [Zoom]
Title: An inverse result for Ruzsa's inequality on triple sumsets
Abstract: Ruzsa's inequality on triple sumsets states that if A is a finite subset of a commutative group then |A+A+A| is at most |A+A|^{3/2}. Ruzsa has constructed a family of examples which show that this inequality is sharp asymptotically, upto a constant factor. In this talk, I will present a new proof of this inequality which improves the constant in the upper bound to (\sqrt{2}/3 + o(1)). This proof shows a connection to Kruskal-Katona type results while also allowing us to obtain a stability version of Ruzsa's inequality which describes near optimal structures. I will then present an inverse result which gives structural information about A even if |A+A+A| is much farther from the upper bound than required in the stability result.
Oct 30 - Tony Vuolo
Title: N-courts: All kings oriented graphs
Abstract: A "king" in a tournament T is a vertex from which every other vertex in T is reachable by a path of length at most 2. The notion of a king can be extended to oriented graphs with no further work. We call an "n-court" any n-vertex oriented graph where all vertices are kings. Define \Upsilon(n) = \min{|E(C)| : C is an n-court}.
In this talk, we will show that the \Upsilon function is well-defined on \mathbb{N}^+ - {2,4}, compute \Upsilon(n) for small n, find asymptotic upper bounds on \Upsilon(n), and examine the structure of n-courts.
Nov 6 - Sean Grate
Title: The stable Tamari lattice
Abstract: The stable Tamari lattice was introduced by Haiman through the lens of invariant polynomials, extended by Bergeron-Preville-Ratelle, and is a variation of the Tamari lattice. Stemming from the AMS MRC: Algebraic Combinatorics in the summer of 2024, I will describe some work in progress joint with Anna Pun, Herman Chau, Spencer Daugherty, and Juan Carlos Martínez Mori where we describe the combinatorics of this lattice. Namely, I will present properties of the lower order ideals of this lattice, the cover relations, and some enumeration problems (related to Catalan numbers and parking functions) we are tackling. I will discuss this data through some examples and Python code.
Nov 13 - Jiaxi Nie (Georgia Tech)
Nov 20 - Flo Pfender (CU Denver)
Dec 4 - Dylan King (Caltech)
Dec 11
Nov 14-15 MAA Sectional meeting in Ames at ISU (local, come)
Jan 4-7 Joint Math Meetings
Mar 9-16 57th Southeastern International Conference on Combinatorics, Graph Theory & Computing (Boca)
Mar 27-29 Graduate Students Combinatorics Conference (Chicago)
Jun 22-25 SIAM Conference on Discrete Mathematics
Aug 5-8 MAA Mathfest (Boston)
TBA (April?) The 11th Lake Michigan Workshop on Combinatorics and Graph Theory)
TBA (Summer) Graduate Research Workshop in Combinatorics (GRWC 2026)