Combinatorics Seminars
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.
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.
DMS Combinatorics Seminar
Jan 29, 2025 02:00 PM
ZOOM
Speaker: Ronald J. Gould (Emory University)
Title: Looking For Saturation in All Kinds of Places
Abstract: Given a graph \(H\), a graph \(G\) is \(H\)-saturated if \(G\) does not contain \(H\) as a subgraph, but the addition of any missing edge to \(G\) results in a graph containing \(H\) as a subgraph. An \(H\)-saturated graph with the maximum number of edges is called an extremal graph for \(H\) and for a given order \(n\), we denoted this as \(\ext(n, H)\). This is the well-known extremal number (or Turan number) of \(H\) and is a well-studied notion with a deep and beautiful history.
However, the focus of this talk will be the many other saturation questions that can be asked. These include, what is the minimum number of edges in an \(H\)-saturated graph? What values of $n$, other than the minimum or maximum, also allow \(H\)-saturated graphs? Is it possible to order the inclusion of missing edges so that at each stage more copies of \(H\) will be included? What about saturation in other settings such as in hypergraphs, edge colored graphs, random graphs, or within graphs other than the complete graph?
Keywords: saturation, saturation spectrum, weak saturation
DMS Combinatorics Seminar
Nov 20, 2024 02:00 PM
ZOOM
Speaker: Jeffrey Mudrock (University of South Alabama)
Title: Strongly and Robustly Critical Graphs
Abstract: In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. Critical and list-critical graphs occupy a prominent place in chromatic graph theory. A k-critical graph is a graph with chromatic number k whose proper subgraphs are (k-1)-colorable. List coloring is a well-known variation on classical vertex coloring where each vertex of a graph receives a list of available colors, and we seek to find a proper coloring of the graph such that the color used on each vertex of the graph comes from the list of colors corresponding to the vertex. In 2008, Stiebitz, Tuza, and Voigt introduced strongly critical graphs which are graphs that are k-critical yet properly colorable with respect to every non-constant assignment that assigns list of size (k-1) to each vertex in the graph.
In this talk we show how to construct large families of strongly critical graphs. We also strengthen the notion of strong criticality by extending it to the framework of DP-coloring which is a generalization of list coloring that has been studied by many researchers since its introduction in 2015. We call this strengthening of strong criticality robust criticality. We discuss some basic properties of robustly critical graphs and give a general method for generating large families of such graphs. As an application of these notions, we show how strong criticality (resp. robust criticality) can be used to give improved bounds on the list chromatic number (resp. DP chromatic number) of certain Cartesian products of graphs.
This is joint work with Anton Bernshteyn, Hemanshu Kaul, and Gunjan Sharma.