Combinatorics Seminars
Nov 19, 2025 02:00 PM
ZOOM
Speaker: Noga Alon (Princeton University)
Title: Vantage Points and Sign Patterns
Abstract: Motivated by a possible application in Social Choice, I will discuss a recent work with Defant, Kravitz and Zhu that studies the number of ways to order points in the plane or in higher dimension according to the sum of their (Euclidean) distances from chosen vantage points.
A crucial mathematical tool here is an extension of results of Milnor and Warren about sign patterns of real polynomials, that have been used in the study of several problems in Discrete Mathematics and theoretical Computer Science, to a version that deals with sign patterns of more general functions.
DMS Combinatorics Seminar
Nov 12, 2025 02:00 PM
328 Parker Hall
Speaker: Xiaofan Yuan (Arizona State University)
Title: Tight minimum colored degree condition for rainbow connectivity
Abstract: Let \(G = (V, E)\) be a graph on \(n\) vertices, and let \(c : E \to P\), where \(P\) is a set of colors. Let \(\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}\) where \(d^c(v)\) is the number of colors on edges incident to a vertex \(v\) of \(G\). In 2011, Fujita and Magnant showed that if \(G\) is a graph on \(n\) vertices that satisfies \(\delta^c(G)\geq n/2\), then for every two vertices \(u, v\) there is a properly-colored \(u,v\)-path in \(G\). We show that for sufficiently large graphs \(G\) the same bound for \(\delta^c(G)\) implies that any two vertices are connected by a rainbow path.
This is joint work with Andrzej Czygrinow.
DMS Combinatorics Seminar
Nov 05, 2025 01:00 PM
328 Parker Hall
Title: Maximum in-general-position set in a random subset of \(\mathbb{F}_q^d\)
DMS Combinatorics Seminar
Oct 29, 2025 02:00 PM
ZOOM
Speaker: Michael Santana (Grand Valley State University, Allendale, Michigan)
Title: Sharpening and extending results on disjoint cycle structures
Abstract: In 1963, Corrádi and Hajnal verified a conjecture of Erdős by showing that for every \(k \in \mathbb{Z}\), if an \(n\)-vertex graph \(G\) satisfies \(n \ge 3k\) and \(\delta(G) \ge 2k\), then \(G\) will contain \(k\) disjoint cycles. This result is extremely tight and has served as the motivation behind a great deal of research in recent years. In this talk, we will discuss only a few of these extensions with an emphasis on their sharpness. Time permitting, we will also talk about recent extensions into hypergraphs.
Variety of the work mentioned is joint with Emily Marshall, Theodore Molla, and Elyse Yeager.
DMS Combinatorics Seminar
Oct 22, 2025 02:00 PM
328 Parker Hall
Speaker: Ariel Cook (Auburn University)
Title: Graph-Referential Colorings of Graphs
Abstract: Let \(G\) and \(H\) be finite, simple graphs on the same vertex set \(V\). A proper \(G\)-coloring of \(H\) is a proper list-coloring of \(H\) from the lists \(N_G(v)\), the open neighborhood of \(v \in V(G)\).
If a \(G\)-coloring of \(H\) exists, then we say that \(H\) is \(G\)-colorable. Further, we define a graph \(H\) to be maximally-\(G\)-colorable if \(H\) is \(G\)-colorable and for any edge \(e \in \overline{E(H)}\), \(H \cup e\) is not \(G\)-colorable. Similarly, we define a graph \(H\) to be minimally-not-\(G\)-colorable if \(H\) is not \(G\)-colorable and for any edge \(e \in E(H)\), \(H - e\) is \(G\)-colorable.
In this talk, we will discuss recent results regarding maximally-\(G\)-colorable graphs \(H\) and minimally-not-\(G\)-colorable graphs \(H\).
This is joint work with Dr. Peter Johnson and Dr. Joseph Briggs.
DMS Combinatorics Seminar
Oct 15, 2025 02:00 PM
328 Parker Hall
Speaker: Owen Henderschedt (Auburn University)
Title: List-orientations and total-coloring extensions of planar graphs
In this talk, I will discuss two problems in graph theory. I will briefly consider the first, which concerns finding orientations that satisfy prescribed out-degree restrictions. The second focuses on coloring extensions, asking when a graph with some precolored subgraphs can be totally colored without introducing additional colors. Inspired by vertex- and edge-coloring extension problems, we initiate the study of total-coloring extensions, proposing several conjectures and proving them for planar graphs.
This is joint work with Jessica McDonald.
DMS Combinatorics Seminar
Oct 08, 2025 02:00 PM
328 Parker Hall
Speaker: Chris Wells (Auburn University)
Title: An unfroggettable tale of longest common subsequences
Abstract:Suppose you stumble across two words and want to know how similar they are. For instance, maybe you are a spell-checker or a biologist wanting to compare two DNA sequences. One of the simplest ways to measure similarity is the length of the longest common subsequence (LCS) between the words. Even if the LCS between two words is large, it may be unclear whether this supposed similarity can be explained purely by random chance. This begs the following question raised by Chvátal and Sankoff in 1975: what is the expected LCS between two words of length \(n\) (large) which are sampled independently and uniformly from a fixed alphabet? Despite being 50 years old, we essentially know nothing about this question (even in the case of the binary alphabet)!
To simplify the question, we instead consider the LCS between a random word and a deterministic, periodic word. In this case, we can do a whole lot more! We approach this simplified question by imagining a bunch of frogs hopping around a ring of lily pads trying to escape the clutches of a randomized monster living in the depths of the pond! In this talk, we will discuss these "frog dynamics" and their relationship to the LCS problem, outline our major results obtained from their hopping, and discuss future directions, including extensions to other string-comparison metrics such as the Levenshtein distance.
(Based on joint work with Boris Bukh and also with Joe Briggs, Alex Parker, and Coy Schwieder)
DMS Combinatorics Seminar
Oct 01, 2025 02:00 PM
328 Parker Hall
Speaker: Joseph Briggs (Auburn University)
Title: Gromov’s Filling Area Conjecture, Discretized
Abstract: A classical problem in differential geometry asks whether the smallest surface bounded by a circle which does not introduce any strictly shorter paths is the hemisphere. It is only known for when the surface in question is homeomorphic to a disk (and some specializations I do not understand), suggesting that the main difficulty is topological in nature.
I will discuss some ideas towards a first general lower bound for arbitrary smooth manifolds by translating the problem into an unfaithful (but independently interesting) combinatorial setting.
This talk will assume no background beyond graph theory I, although some maturity from convex geometry or topology II may help.
Based on joint work with Chris Wells.
DMS Combinatorics Seminar
Sep 24, 2025 02:00 PM
ZOOM
Speaker: Mark Ellingham (Vanderbilt University)
Title: Maximum genus directed embeddings of digraphs
Abstract: In topological graph theory we often want to find embeddings of a given connected graph with minimum genus, so that the underlying compact surface of the embedding is as simple as possible. If we restrict ourselves to cellular embeddings, where all faces are homeomorphic to disks, then it is also of interest to find embeddings with maximum genus. For undirected graphs this is a very well-solved problem. For digraphs we can consider directed embeddings, where each face is bounded by a directed walk in the digraph. The maximum genus problem for digraphs is related to self-assembly problems for models of graphs built from DNA or polypeptides. Previous work by other people determined the maximum genus for the very special case of regular tournaments, and in some cases of directed 4-regular graphs the maximum genus can be found using an algorithm for the representable delta-matroid parity problem. We describe some recent work, joint with Joanna Ellis-Monaghan of the University of Amsterdam, where we have solved the maximum directed genus problem in some reasonably general situations.
DMS Combinatorics Seminar
Sep 17, 2025 02:00 PM
ZOOM
Speaker: Xiaonan Liu (Vanderbilt University)
Title: Counting \(k\)-cycles in \(5\)-connected planar triangulations
We show that every \(n\)-vertex \(5\)-connected planar triangulation has at most \(9n-50\) many cycles of length \(5\) for all \(n\geq 20\) and this upper bound is tight. We also show that for every \(k\geq 6\), there exists some constant \(C(k)\) such that for sufficiently large \(n\), every \(n\)-vertex \(5\)-connected planar graph has at most \(C(k) \cdot n^{\lfloor k/3 \rfloor}\) many cycles of length \(k\). This upper bound is asymptotically tight for all \(k\geq 6\).
Joint work with Gyaneshwar Agrahari and Zhiyu Wang.