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]
Oct 30 - Tony Vuolo
Nov 6 - Sean Grate
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)