Discrete Seminar

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  Anna Halfpap, Grace McCourt and Bernard Lidický.

Spring 2025 


Title: Counting Monochromatic Solutions of 3-variable Linear Equations

Abstract: A famous result in arithmetic Ramsey theory says that for many linear homogeneous equations E there is a threshold value R_k(E) (the Rado number of E) such that for any k-coloring of the integers in the interval [1, n], with n ≥ R_k(E), there exists at least one monochromatic solution. But one can further ask, how many monochromatic solutions is the minimum possible in terms of n? Several authors have estimated this function before, here we offer new tools from integer and semidefinite optimization that help find either optimal or near optimal 2-colorings minimizing the number of monochromatic solutions of several families of 3-variable non-regular homogeneous linear equations. In the last part of the paper we further extend to three and more colors for the Schur equation, improving earlier work.


Past Seminars

Title: B-colorings of planar and outerplanar graphs 

Abstract: A coloring of the edges of a graph G in which every K_{1,2} is totally multicolored is known as a proper coloring and a coloring of the edges of G in which every K_{1,2} and every K_{2,2} is totally multicolored is called a B-coloring.

In this talk, we establish that a planar graph with maximum degree ∆ can be B-colored with max{2∆ ,32} colors. This is best-possible for large ∆ because K_{2,∆ } requires 2∆ colors. In addition, there is an example with ∆=4 that requires 12 colors.

We also establish that an outerplanar graph with maximum degree ∆ can be B-colored with max{∆ ,6} colors. This is almost best-possible because ∆ colors are necessary and there is an example with ∆=4 that requires 5 colors.

Title: Interval Generalizations of Parking Functions

Abstract: In 1966, Alan G. Konheim and Benjamin Weiss defined “parking functions.” Interval parking functions were introduced in 2020 by Colaric, Demuse, Martin, and Yin. In this talk, we share some results about interval parking functions and specialize to the case of \ell-interval parking functions (which are interval parking functions where all cars have a preference interval of length \ell). Inspired by work studying statistics of permutations, we examine equidistribution for the inversion statistic and the major index for \ell-interval parking functions (and general n). We end with a discussion of other parking function generalizations and statistics of interest.

Title: On saturation, semisaturation, and rainbow saturation numbers

Abstract: Saturation problems concern graphs which are edge-maximal with respect to a given property. A graph is H-semisaturated if adding any edge between nonadjacent vertices increases the number of subgraphs isomorphic to a fixed graph H. The minimum number of edges in an H-semisaturated graph on n vertices, called the semisaturation number of H, was first studied for cliques H by Erdős, Hajnal, and Moon and is witnessed by a unique (H-free) graph for every n. From this result stemmed the study of the saturation number of H, or the minimum number of edges in a maximally H-free graph on n vertices. Sixty years later, saturation and semisaturation numbers remain unknown for many seemingly simple graphs, like trees.

A version of the saturation number for properly edge-colored graphs was introduced in 2022 by Bushaw, Johnston, and Rombach, in analogy with the rainbow Turán number introduced by Keevash, Mubayi, Sudakov, and Verstraëte. A graph is rainbow H-saturated if it is maximal with respect to possessing a proper edge-coloring which is rainbow H-free (at least two edges receive the same color in every copy of H). In this talk, we determine the asymptotics of the saturation, semisaturation, and rainbow saturation numbers of double stars (trees of diameter 3). This includes a general lower bound for semisaturation numbers, and thus for saturation and rainbow saturation numbers as well. We also examine (semi)saturation for caterpillars of larger diameter whose internal vertices all have the same degree.

Title: An Eulerian Polynomial for Digraphs

Abstract: Permutation descents and the generating function thereof are a very subtle invariant of the symmetric group. One can generalize permutation descents to digraphs as follows. Given a digraph D and an ordering on its vertices, an edge is a descent if it is out-of-order with respect to the ordering. We study the resulting generating function, in particular its evaluation at x = -1, and highlight some extremal results and connections with spectral graph theory and algebraic combinatorics. This talk is from joint work with Kyle Celano and Sam Spiro. 

Title: Online Ramsey numbers of ordered graphs

Abstract: The online ordered Ramsey game is played between two players, Builder and Painter, on an infinite sequence of vertices with ordered graphs (G_1,G_2), which have linear orderings on their vertices. On each turn, Builder first selects an edge before Painter colors it red or blue. Builder's objective is to construct either an ordered red copy of G_1 or an ordered blue copy of G_2, while Painter's objective is to delay this for as many turns as possible. The online ordered Ramsey number r_o(G_1,G_2) is the number of turns Builder takes to win in the case that both players play optimally.

Few lower bounds are known for this quantity. In this paper, we introduce a succinct proof of a new lower bound based on the maximum left- and right-degrees in the ordered graphs. We also upper bound r_o(G_1,G_2) in two cases: when G_1 is a cycle and G_2 a complete bipartite graph, and when G_1 is a tree and G_2 a clique. This is joint work with Emily Heath, Dylan King, Hannah Sheats, and Justin Wisby.

Title: Rainbow Erd\H{o}s-S\'os Conjectures

 Abstract: An edge colored graph is said to contain rainbow-$F$ if $F$ is a subgraph and every edge receives a different color. In 2007, Keevash, Mubayi, Sudakov, and Verstra\"ete introduced the \emph{rainbow extremal number} $\mathrm{ex}^*(n,F)$, a variant on the classical Tur\'an problem, asking for the maximum number of edges in a $n$-vertex properly edge-colored graph which does not contain a rainbow-$F$. In the following years many authors have studied the asymptotic behavior of $\mathrm{ex}^*(n,F)$ when $F$ is bipartite. In the particular case that $F$ is a tree $T$, the infamous Erd\H{o}s-S\'os conjecture says that the extremal number of $T$ depends only on the size of $T$ and not its structure. After observing that such a pattern cannot hold for $\mathrm{ex}^*$ in the usual setting, we propose that the relative rainbow extremal number $\mathrm{ex}^*(Q_n,T)$ in the $n$-dimensional hypercube $Q_n$ will satisfy an Erd\H{o}s-S\'os type Conjecture and verify it for some infinite families of trees $T$.