Combinatorics Seminars
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.
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.
DMS Combinatorics Seminar
Mar 19, 2025 02:00 PM
328 Parker Hall
Speaker: Steve Butler (Iowa State University)
Title: Forming cospectral graphs by coalescing
Abstract: Spectral graph theory looks at the interplay between graphs and the eigenvalues of particular matrices associated with graphs. One way to understand the shortcomings of particular matrices is through the study of "cospectral graphs" (nonisomorphic graphs with the same eigenvalues). A well-known method of forming cospectral graphs is through coalescing, the act of gluing graphs by identifying vertices together. We give necessary and sufficient conditions for forming cospectral graphs by coalescing for matrices in the same family as the adjacency or Laplacian using cycle decomposition arguments. We also will give a sufficient condition for forming cospectral graphs by coalescing for the distance matrix using block similarity arguments.
This is based on work done in the 2022 and 2023 REUs at Iowa State University.
DMS Combinatorics Seminar
Mar 05, 2025 02:00 PM
328 Parker Hall
Speaker: Stephanie Dorough (Auburn University)
Title: Rainbow Connectivity and Proper Rainbow Connectivity
Abstract: A connected graph \(G\) is rainbow connected with respect to an edge coloring of \(G\) if each pair of distinct vertices of \(G\) are joined by a rainbow path; that is, a path with no color appearing on more than one edge of the path. \(G\) is strongly rainbow connected if each pair of distinct vertices of \(G\) are joined by a rainbow geodesic, a shortest path in \(G\) between the vertices. The (strong) rainbow connection number of \(G\), denoted \(\text{(s)rc}(G)\), is the smallest number of colors in an edge coloring of \(G\) with respect to which \(G\) is (strongly) rainbow connected.
This talk will consider two more recently introduced parameters, \(\text{prc}(G)\) and \(\text{psrc}(G)\), defined as \(\text{rc}(G)\) and \(\text{src}(G)\) were, with the additional requirement that the edge colorings be proper. We will then cover some relations among the four parameters and evaluate them on some classes of graphs, including some of the theta graphs.
DMS Combinatorics Seminar
Feb 26, 2025 02:00 PM
328 Parker Hall
Speaker: Ariel Cook (Auburn University)
Graph-Referential List-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)\). This definition descends from a question posed by Steve Hedetniemi, and opens the way to new, interesting questions regarding graph colorability. Our current research focuses on extremal problems associated with this definition, including maximal graphs \(H\) such that $H$ is \(G\)-colorable, minimal graphs \(H\) such that \(H\) is not \(G\)-colorable, minimal graphs \(G\) such that \(H\) is \(G\)-colorable, and maximal graphs \(G\) such that \(H\) is not \(G\)-colorable.
DMS Combinatorics Seminar
Feb 19, 2025 02:00 PM
328 Parker Hall
Speaker: Songling Shan (Auburn University)
Title: Linear arboricity of graphs with large minimum degree
Abstract: In 1980, Akiyama, Exoo, and Harary conjectured that any graph \(G\) can be decomposed into at most \(\lceil(\Delta(G)+1)/2\rceil\) linear forests. We confirm the conjecture for sufficiently large graphs with large minimum degree. Precisely, we show that for any given \(0<\varepsilon <1\), there exists \(n_0 \in \mathbb{N}\) for which the following statement holds: If \(G\) is a graph on \(n\ge n_0\) vertices of minimum degree at least \((1+\varepsilon)n/2\), then \(G\) can be decomposed into at most \(\lceil(\Delta(G)+1)/2\rceil\) linear forests.
This is joint work with Yuping Gao.
DMS Combinatorics Seminar
Feb 12, 2025 02:00 PM
ZOOM
Speaker: Grace McCourt (Iowa State University)
Title: Dirac-type results for Berge cycles in uniform hypergraphs
Abstract: The famous Dirac Theorem gives an exact bound on the minimum degree of an \(n\)-vertex graph guaranteeing the existence of a hamiltonian cycle. Dirac also gave a minimum degree bound on the circumference of a graph. Furthermore, he proved that each \(n\)-vertex 2-connected graph with minimum degree at least \(k\) contains a cycle of length at least \(\min\{2k,n\}\). We consider versions of these results in hypergraphs.
This work is joint with Alexandr Kostochka and Ruth Luo.
DMS Combinatorics Seminar
Feb 05, 2025 02:00 PM
328 Parker Hall
Speaker: Zach Walsh (Auburn University)
Title: Turán densities for matroid basis hypergraphs
Abstract: An \((r, s, t)\)-daisy is an \(r\)-uniform hypergraph that adds a "stem" to the complete \(s\)-uniform \(t\)-vertex hypergraph. Ellis, Ivan, and Leader recently showed that the limit as \(r\) tends to infinity of the Turán densities of \((r, s, t)\)-daisies is positive, disproving a conjecture of Bollabás, Leader, and Malvenuto. This raises the following question: Precisely what is this limit? The hypergraphs constructed by Ellis, Ivan, and Leader are matroid basis hypergraphs, and we show that their construction is best-possible within the class of matroid basis hypergraphs.
This is joint work with Michael Wigal and Jorn van der Pol.