The Discrete Math Seminar at Iowa State University is held on Wednesday at 3:20-4:10 pm in Carver 232 .
Some old talks are available on YouTube.
The seminar is organized by Ramón García, Owen Henderschedt and Bernard Lidický.
Sep 30 Alexander Clifton
Title: Backgammon Parking Functions
Abstract: We introduce a new parking scheme inspired by the game of backgammon. We consider a one-way street with $n$ parking spots and a queue of $n$ cars waiting to park.
Each car has a preferred parking spot on the street and enters in sequence to park in that spot if it is available. If a car finds its preferred spot occupied, it bumps the already parked car out of that spot and takes its place. The bumped car then returns to the start of the street and parks in the first available spot it encounters. Consequently, all the cars park.
For a given preference list $\alpha\in [n]^n$, the final order in which the cars park is some permutation in $\Sym_n$, which we call the outcome of $\alpha$. One key question is to determine how many preference lists yield a particular outcome. We show that this is bounded above by the Catalan number $C_n$, and determine all outcomes, including the identity permutation, which attain the maximum. Additionally, we show that the number of preference lists yielding the decreasing permutation $n\cdots321$ is the Motzkin number $M_n$.
Joint work with Pamela E. Harris and Maryam Khaqan.
Oct 7 Go see colloquium of Shira Zerbib on Oct 6
Title:
Abstract:
Oct 14
Title:
Abstract:
Oct 21 Ignacy Buczek
Title:
Abstract:
Oct 28 Asier Calbet
Title:
Abstract:
Nov 4 Daniel McGinnis (zoom)
Title: Multi-graded generic initial ideals, regularity, and the optimal colorful fractional Helly theorem for $d$-Leray complexes
Abstract: A celebrated result of Bayer and Stillman from 1987 states that for a homogeneous ideal $I$ of a polynomial ring $S$, the regularities of $S/I$ and $S/\textrm{GIN}(I)$ are the same under the reverse lexicographic monomial ordering, where $\textrm{GIN}(I)$ is the generic initial ideal. If $R$ is a polynomial ring whose variables are subdivided into disjoint blocks of variables $X_1,\dots,X_c$, there is a natural multi-grading on $R$, and one can analogously define a multi-graded version of the generic initial ideal for any multi-homogeneous ideal $I$ of $R$. However, the full strength of the Bayer--Stillman Theorem fails in the multi-graded setting; there are multi-homogeneous ideals $I$ such that the regularities are not preserved after passing to the multi-graded generic initial ideal no matter the choice of monomial ordering.
We prove lower bounds on the regularity of $R/I$ in terms of \textit{almost regular sequences} of the multi-graded generic initial ideal of $I$ restricted to each block of variables. Again, we use the reverse lexicographic monomial ordering, but interestingly, the lower bound result requires a particular choice of ordering on the variables.
As an application, we prove the \textit{optimal fractional Helly theorem for $d$-Leray simplicial complexes}, a problem stemming from the work of Kim in 2017.
Nov 11 Songling Shan (zoom)
Title:
Abstract:
Nov 18 Victor Falgas Ravry (11am) (Carver 401)
Title:
Abstract:
Dec 2
Title:
Abstract:
Dec 9
Title:
Abstract:
Previous talks in the Fall 2026 Seminar
Aug 26 Casey Tompkins (11am) (Carver 401)
Title: An Improved Lower Bound for Diamond-free families
Abstract: We consider an extremal problem for systems of finite subsets of $[n]=\{1,2,\dots,n\}$ avoiding a given subposet.
For a finite poset~$P$, a family $\mathcal F\subseteq 2^{[n]}$ contains a weak copy of~$P$ if there is an injective map $\psi\colon P\to \mathcal{F}$ such that, whenever $p<q$ in $P$, we have $\psi(p) \subset \psi(q)$. Katona and Tarj\'an introduced the following extremal function:
\[La(n,P)=\max\{|\mathcal F| : \mathcal F\subseteq 2^{[n]}\text{ contains no weak copy of }P\}.\]
While $La(n,P)$ has been investigated for many posets $P$, a notorious open case is the diamond poset $Q_2$ consisting of $4$ elements $w,x,y,z$ with the relations $w<x,y<z$. The family of subsets of $[n]$ consisting of just sets of two sizes closest to $n/2$ was widely believed to be optimal. We show, on the contrary that there are families of size roughly $2.147{n \choose n/2}$ avoiding $Q_2$. The construction is algebraic and related to the recent daisy-free hypergraph construction of Ellis, Ivan and Leader.
As time permits I will also discuss further variations on the method. For example, an improved lower bound on $La(n,O_6)$, the crown poset, as well as further general results on $La(n,P)$. This latter work is joint with Bal\'azs Patk\'os, and the ChatGPT model was fundamental to obtaining all constructions discussed in the talk.
Aug 26 Michal Dvořák (Carver 401)
Title: Pathfinding in Self-Deleting Graphs
Abstract: We study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices.
In particular, we study \emph{self-deleting graphs}, introduced by Carmesin et al.~\cite{carmesin2023hamiltonian}, which consist of a graph $G=(V, E)$ and a function $f\colon V\rightarrow 2^E$, where $f(v)$ is the set of edges that will be deleted after visiting the vertex $v$.
In the \textsc{(Shortest) Self-Deleting Path} problem we are given a self-deleting graph and its vertices $s$ and $t$, and we are asked to find a path from $s$ to $t$ (of at most a given length), such that it does not traverse an edge in $f(v)$ after visiting $v$ for any vertex $v$.
We prove that \textsc{Self-Deleting Path} is \NP-hard even if the given graph is outerplanar, bipartite, has maximum degree $3$, bandwidth $2$ and satisfies $|f(v)|\leq 1$ for each vertex $v$.
We show that \textsc{Shortest Self Deleting Path} is \W{1}-complete parameterized by the length of the sought path and that it is \W{1}-complete parameterized by the vertex cover number, feedback vertex set number and treedepth.
In order to obtain algorithmic results, we parameterize the problem by $\mu=\max_v |f(v)|$ -- the maximum size of $f(v)$ and the length of the sought path. By a nontrivial application of the color coding technique, we obtain \FPT algorithm for the combination of $\mu$ and the length of the sought path. This result allows us to obtain several \FPT algorithms for parameterization by a combination of $\mu$ and a structural parameter, such as shrub-depth or modular-width. These algorithms are obtained by reducing to a particular extremal question about density of edges in graphs containing hamiltonian paths.
Next, we show that under standard complexity theoretical assumptions, there is no polynomial kernel for \textsc{Shortest Self-Deleting Path} parameterized by the combination of vertex cover number, and $\mu$ already on $2$-outerplanar graphs.
Sep 2 Welcome all (Introduce yourself)
Sep 9 Owen Henderschedt
Title: A finite victory over de Bruijn - Erdős in interval discrepancy
Abstract: In this talk, we consider a finite form of the classical interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals have been produced. The discrepancy of such a process is the maximum, over all intermediate stages, of the ratio between the longest interval and the shortest interval. A theorem of de Bruijn and Erd\H{o}s from 1949 shows that this ratio must approach $2$ as $n\to\infty$, and they give a sharp construction achieving this bound. For fixed $n$, their construction gives the upper bound $\disc(n)\leq 2-\frac{3}{2n}+O(1/n^2)$. In this paper, we improve the first-order term of this bound. Specifically, we construct a strategy, called lex-merge, with $\disc(n)\leq 2-\frac{4\ln 2}{n}+O(1/n^2)$. We also show this bound is optimal. This is joint work with Jared DeLeo and Chris Wells.
Sep 16 Ramón García
Title: Counting hypergraphs without linear cycles of fixed length
Abstract: Let $C_k^{(r)}$ denote the $r$-uniform linear cycle with $k$ hyperedges. An $r$-graph is $C_k^{(r)}$-free if it contains no copy of $C_k^{(r)}$. Write $\text{ex}_r(n,C_k^{(r)})$ for the maximum number of hyperedges in an $n$-vertex $C_k^{(r)}$-free $r$-graph. Balogh, Narayanan and Skokan asked whether, for every pair of integers $r,k\ge 3$, the number of $C_k^{(r)}$-free $r$-graphs on $n$ labelled vertices is $2^{(1+o(1))\text{ex}_r(n,C_k^{(r)})}$.
Although the analogous statement fails for graphs ($r=2$), as shown by a construction of Morris and Saxton, the general question remained open for hypergraphs. Very recently, Jiang and Longbrake answered it affirmatively for $r\ge 5$.
In this talk, I will present a complete resolution of the problem, establishing an affirmative answer for all $r,k\ge 3$. Joint work with József Balogh and Abhishek Methuku.
Sep 23 Bernard Lidicky
Title: Pattern Boost and Axplorer
Abstract: Pattern Boost is a method developed for finding combinatorial constructions using machine learning. It combines local search and machine learning. It alternates between training a neural network to make examples and optimizing these examples using local search. While local search can get stuck in local optima easily, the neural network may extract some patters in the good constructions that help overcome the local optima problem. The original idea of Pattern Boost was recently reimplemented as Axplorer.
The aim of the talk is to introduce the main ideas behind the tools and how to use them. This is not a talk discussing research or results of the speaker.
Sep 18-19 The 66th Midwest Graph Theory Conference (MIGHTY LXVI)
Oct 24-25 Sectional AMS (Duluth)
Oct 23-25 MAAGC (Richmond, VA)
Jan 12-15 JMM (Chicago)
Mar 8-12 58th Southeastern International Conference on Combinatorics, Graph Theory & Computing (Boca)
Apr 17-18 Sectional AMS (Iowa City)
Jun 7-11 Workshop on Anti-Ramsey Problems (CMU) - apply by November 15
Jun 14-18 CanaDAM 2027 (Kelowna BC)
Jun 20-26 Bled Conference (Slovenia)
Summer Graduate Research Workshop in Combinatorics (GRWC 2027) (TBA)
Jul 26 to Aug 6, 2027 G2P2: Graphs and Groups, Probability and Permutations (Memphis) - apply for funding
Aug 4-7 MAA Mathfest (New Orleans)