Combinatorics Seminars
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.
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.
DMS Combinatorics Seminar
Nov 13, 2024 02:00 PM
328 Parker Hall
Speaker: Jessica McDonald (Auburn University)
Title: Strong Colouring with \(K_3\)'s and \(K_4\)'s
Abstract: If \(H\) is a graph, and \(G\) is obtained from \(H\) by gluing on vertex-disjoint copies of \(K_t\), then when can we guarantee that \(G\) is \(t\)-colourable? The Strong Colouring Conjecture posits that \(\chi(G)\leq t\) whenever \(t\geq 2\Delta(H)\). We'll discuss this seemingly very difficult conjecture, with particular focus on the elusive case of \(\Delta(H)=2\). We'll describe new joint work with Dalal and Shan where the "cycles plus \(K_4\)'s" problem is reduced to a problem about "strong colouring" with \(K_3\)'s.
DMS Combinatorics Seminar
Nov 06, 2024 02:00 PM
328 Parker Hall
Speaker: Sean Grate (Auburn University)
Title: The stable Tamari lattice
Abstract: The stable Tamari lattice was introduced by Haiman through the lens of invariant polynomials, extended by Bergeron-Preville-Ratelle and is a variation of the Tamari lattice. Stemming from the AMS MRC: Algebraic Combinatorics this past summer, I will describe some work in progress joint with Anna Pun, Herman Chau, Spencer Daugherty, and Juan Carlos Martínez Mori where we describe the combinatorics of this lattice. Namely, I will present properties of the lower order ideals of this lattice, the cover relations, and some enumeration problems we are tackling. I will discuss this data through some examples and Python code.
DMS Combinatorics Seminar
Oct 30, 2024 02:00 PM
328 Parker Hall
Speaker: Rachel Galindo (Auburn University)
Title: Vertex Coloring and Clique Containment
Abstract: This talk will consist of two separate, but related topics.
The first: An equivalent version of the Borodin-Kostochka Conjecture, due to Cranston and Rabern, says that any graph with \(\chi = \Delta = 9\) contains \(K_3 \lor E_6\) as a subgraph. In this talk, we will discuss several results in support of this conjecture, where vertex-criticality and forbidden substructure conditions get us either close or all the way to containing \(K_3 \lor E_6\).
The second: The Ore Degree is a graph parameter which has been proven to serve as an upper bound for the chromatic number. We define two new Ore-type graph parameters and present preliminary results towards showing they also can serve as upper bounds on \(\chi\).