Combinatorics Seminars
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)
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.
DMS Combinatorics Seminar
Sep 10, 2025 02:30 PM
ZOOM
NOTE TIME for BEGINNING is 2:30
Speaker: Guangming Jing, (University of Massachusetts, Lowell)
Title: Edge Coloring of Multigraphs
Abstract: Given a multigraph \(G=(V,E)\), the chromatic index \(\chi'(G)\) is the minimum number of colors needed to color the edges of \(G\) such that no two adjacent edges receive the same color. Let \(\Delta(G)\) be the maximum degree of \(G\) and let
\(\Gamma(G) = \max \left\{ \frac{2|E(U)|}{|U|-1} : U \subseteq V,\ |U|\geq 3\ \text{and odd} \right\}.\)
Then \(\Gamma(G)\) is called the density of \(G\). Clearly, the density is a lower bound for the chromatic index \(\chi'(G)\).
In this talk, we will discuss several density-related edge coloring problems on multigraphs.
DMS Combinatorics Seminar
Sep 03, 2025 02:00 PM
328 Parker Hall
Speaker: Jessica McDonald, Auburn University
Title: Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree
Abstract: It is easy to show that every graph \(G\) satisfies \(\chi(G)\leq \Delta(G)+1\), where \(\chi(G), \Delta(G)\) denote the chromatic number and maximum degree of \(G\), respectively. Brooks' Theorem says that if a connected graph \(G\) has \(\chi(G)=\Delta(G)+1\), then \(G\) is either \(K_{\Delta(G)+1}\) or an odd cycle. In this talk we discuss a new, uniform, and self-contained proof of the following result: if \(G\) is a connected graph with \(\chi(G) = \Delta(G)\) and \(G\neq \overline{C_7}\), then \(G\) contains either \(K_{\Delta(G)}\) or an odd hole where every vertex has degree at least \(\Delta(G)-1\) in \(G\). This was previously proved in a series of two papers by Chen, Lan, Lin, and Zhou, who used the Strong Perfect Graph Theorem for the cases \(\Delta(G)=4, 5, 6\).
This is joint work with Rachel Galindo and Songling Shan.
DMS Combinatorics Seminar
Aug 27, 2025 02:00 PM
328 Parker Hall
Speaker: Zach Walsh, Auburn University
Title: Delta-modular matroids
Abstract: An integer matrix is totally \(D\)-modular if the absolute value of the determinant of every square submatrix is at most \(D\). How many distinct columns can a rank-\(r\) totally \(D\)-modular matrix have? We will show how recent progress was made on this question via matroids, which are discrete structures that provide a combinatorial abstraction of linear independence.
This is joint work with Joseph Paat, Into Stallknecht, and Luze Xu.
DMS Combinatorics Seminar
Apr 23, 2025 02:00 PM
328 Parker Hall
Speaker: Arthur Tanyel (Auburn University)
Title: Some Conditions for Hamiltonicity in Tough Graphs
Abstract: This talk has two focuses, both concerning Hamiltonicity conditions in tough graphs. First, we present a \(t\)-closure lemma that generalizes a closure lemma of Bondy and Chvátal from 1976. In 1995, Hoàng generalized Chvátal's degree sequence condition for Hamiltonicity in 1-tough graphs and posed two \(t\)-tough analogues for any positive integer \(t \ge 1\). Hoàng confirmed his conjectures respectively for \(t \le 3\) and \(t=1\). We apply our \(t\)-closure lemma to confirm both conjectures for all \(t \ge 4\).
Second, we present that all 71-tough \((2P_2 \cup P_1)\)-free graphs of order at least three are Hamiltonian. This research is inspired by Chvátal's conjecture that there exists a constant \(t_0\) such that all \(t_0\)-tough graphs of order at least three are Hamiltonian. This conjecture is still open, but work has been done to find such a \(t_0\) for certain graph classes. With our result, the conjecture is confirmed for all \(F\)-free graphs where \(F\) is any five-vertex linear forest excepting \(P_5\).
DMS Combinatorics Seminar
Apr 09, 2025 02:00 PM
328 Parker Hall
Speaker: Josey Graves (Auburn University)
Title: Widths of Finite Posets under the Majorization Ordering
Abstract: We focus on the structural properties of two types of posets, \(P(n,m)\) and \(P'(n,m)\), both of which are ordered by the majorization ordering. Specifically, we consider those cases where \(1 \leq n \leq 4\). The poset \(P(n,m)\) consists of sequences of non-negative integers of length \(n\) that sum to \(m\). The second poset, \(P'(n,m)\), is a subposet of \(P(n,m)\) where we restrict to the decreasing sequences. We demonstrate that these posets exhibit Sperner-like properties. In particular, we show that the largest antichain in \(P(n,m)\) and \(P'(n,m)\) for \(1 \leq n \leq 4\) is realized by a "middle" "level," similar to that of the classical Sperner theorem. We use the term "middle" loosely here, as there may be many levels or induced levels which are maximal, and they all generally occur in the middle section of these posets. In the case of \(P(n,m)\), we provide explicit chain decompositions, while for \(P'(n,m)\) we give explicit chain decompositions for \(n \in \{1,2\}\). For \(P'(n,m)\) when \(n \in \{3,4\}\), we give an inductive proof of the existence of a minimal chain decomposition on the outer layer(s), with induction handling the smaller poset.
DMS Combinatorics Seminar
Apr 02, 2025 02:00 PM
328 Parker Hall
Speaker: Jared DeLeo (Auburn University)
Title: Edge-Regular Graphs and Uniform Shared Neighborhood Structures
Abstract: We explore various results about edge-regular graphs, which are a superset of the well-studied class of strongly regular graphs, and special induced subgraphs within these edge-regular graphs called ‘uniform shared neighborhood structures' (USNS for short). In particular, there exist graphs \(H\) such that \(H\) is not the USNS for any edge-regular graph \(G\), known as a USNS-forbidden graph. We will discuss these USNS-forbidden graph results, as well as using known graph products, including a “new" graph product, to produce new edge-regular graphs that have USNS. The “new" graph product, the unary shadow graph operator, is given special attention and is examined for regular, edge-regular, and strongly regular graphs.
DMS Combinatorics Seminar
Mar 26, 2025 02:00 PM
328 Parker Hall
Speaker: Jessica McDonald (Auburn University)
Title: Balanced-chromatic number and Hadwiger-like conjectures
Abstract: We introduce a signed version of Hadwiger's Conjecture, which relies on the notion of a balanced colouring of a signed graph. We show that our signed version is in fact equivalent to the original Hadwider's Conjecture, and we show its relationship to the Odd Hadwiger Conjecture. We also prove a result relating balanced colourings and subdivisions in signed graphs.
This is joint work with Andrea Jimenez, Reza Naserasr, Kathryn Nurse, and Daniel Quiroz.