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 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
Title:
Abstract:
Sep 23
Title:
Abstract:
Sep 30 Alexander Clifton
Title:
Abstract:
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
Title:
Abstract:
Nov 4
Title:
Abstract:
Nov 11
Title:
Abstract:
Nov 18
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 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 14-18 CanaDAM 2027 (Kelowna BC)
Summer Graduate Research Workshop in Combinatorics (GRWC 2027) (TBA)
Aug 4-7 MAA Mathfest (New Orleans)