Combinatorics Seminars
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.
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\).
DMS Combinatorics Seminar
Oct 23, 2024 02:00 PM
328 Parker Hall
Speaker: Andrei Pavelescu (University of South Alabama)
Title: Topological Properties of Graphs and Connected Domination
Abstract: The connected domination number \(\gamma_c(G)\) of \(G\) is the minimum cardinality of dominating sets \(S\) of \(G\) which induces a connected subgraph \(G[S]\) of \(G\). We present some sharp bounds for \(\gamma_c(G)\), together with some open questions. We show how the connected domination can be used to establish results about topological properties of graphs and their complements. A graph \(G\) is called bi-knotlessly embeddable (bi-nIK), if both \(G\) and its complement, \(\overline{G}\), admit an embedding in \(\mathbb{R}^3\) with every cycle represented by a trivial knot. By size arguments, for large enough order \(n\), the complete graph \(K_n\) cannot be bi-nIK. We are asking for the smallest order \(n\), such that \(K_n\) is not bi-nIK. We prove that every graph of order 15 or more cannot be bi-nIK.
DMS Combinatorics Seminar
Oct 16, 2024 02:00 PM
328 Parker Hall
Speaker: Zach Walsh (Auburn University)
Title: Delta-Wye exchange for matroids over pastures
Abstract: Delta-Wye exchange is a fundamental graph operation that preserves many natural embeddability properties of graphs. This operation generalizes to matroids, and preserves many natural representability properties of matroids. We will present a result showing that Delta-Wye exchange preserves matroid representability over any pasture, which is an algebraic object that generalizes partial fields and hyperfields. We will assume no knowledge of matroid theory.
This is joint work with Matt Baker, Oliver Lorscheid, and Tianyi Zhang.
DMS Combinatorics Seminar
Oct 09, 2024 02:00 PM
328 Parker Hall
Speaker: Songling Shan (Auburn University)
Title: Total coloring graphs with large maximum degree
Abstract: We prove that for any graph \(G\), the total chromatic number of \(G\) is at most \(\Delta(G)+2\lceil \frac{|V(G)|}{\Delta(G)+1} \rceil\).
This saves one color in comparison with a result of Hind from 1992 In particular, our result says that if \(\Delta(G)\ge \frac{1}{2}|V(G)|\), then \(G\) has a total colouring using at most \(\Delta(G)+4\) colors. When \(G\) is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any \(0<\varepsilon <1\), there exists \(n_0\in \mathbb{N}\) such that: if \(G\) is an \(r\)-regular graph on \(n \ge n_0\) vertices with \(r\ge \frac{1}{2}(1+\varepsilon) n\), then \(\chi_T(G) \le \Delta(G)+2\). This confirms the Total Coloring Conjecture for such graphs \(G\).
This is joint work with Aseem Dalal and Jessica McDonald.
DMS Combinatorics Seminar
Oct 02, 2024 02:00 PM
328 Parker Hall
Speaker: Nicholas Gaubatz (Auburn University)
Title: Minimal Sizes of Out-Neighborhoods in the \(F\)-Lattice
Abstract: The classical isoperimetry problem is to determine the shape with minimal perimeter among all shapes of fixed volume. Analogs of this problem have been studied in the setting of lattices and polyominoes. We will discuss a variation of this problem posed by Joe Briggs, where we compute the sizes of minimal out-neighborhoods in the \(F\)-lattice. We will present some results toward this end via examples, focusing on the minimum values attained and the minimizers.
This is joint work with Haile Gilroy and Sean Grate.
DMS Combinatorics Seminar
Sep 25, 2024 02:00 PM
328 Parker Hall
Speaker: Shira Zerbib (Iowa State University)
Title: Bounds on piercing numbers and line-piercing numbers in families of convex sets in the plane
Abstract: A family \(F\) of sets has the \((p,q)\) property if amongst any \(p\) members of it some \(q\) intersect. \(F\) has the \(T(k)\) property if every \(k\) sets in \(F\) are intersected by a line. We prove that if \(F\) is a family of convex sets in the plane with the \((p+1,2)\) property then there are \( \lfloor p/2\rfloor +1\) lines whose union intersects all the sets in \(F\), and this bound is tight. We use this result to prove new bounds on the piercing numbers in families of convex sets in the plane with the \((p,2)\) property, in terms of the matching numbers of their pairwise intersection families. We further prove a conjecture of Eckhoff from 1993, asserting that if a family of convex sets in the plane has the \(T(3)\) property then there are 3 lines whose union intersects all the sets in it. Rainbow versions of these results are also proved. The proofs use the topological KKM theorem and its colorful generalization.
Partly joined with Daniel McGinnis.
DMS Combinatorics Seminar
Sep 18, 2024 02:00 PM
328 Parker Hall
Speaker: Owen Henderschedt (Auburn University)
Title:On orientations of graphs with forbidden out-degrees
Abstract: When does a graph admit an orientation with some desired properties? This question has been extensively studied for many years and across many different properties. Specifically, I will talk about properties having to do with degree restrictions, and progress towards a conjecture of Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati dealing with a list-type of degree restriction. This is all joint work with Jessica McDonald.
DMS Combinatorics Seminar
Sep 11, 2024 12:55 PM
328 Parker Hall
Speaker: Arthur Tanyel (Auburn University)
Title: Degree sequence condition for Hamiltonicity in tough graphs
Abstract: Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvátal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a graph. Hoàng in 1995 generalized Chvátal's degree sequence condition for 1-tough graphs and conjectured a \(t\)-tough analogue for any positive integer \(t\ge 1\). Hoàng in the same paper verified his conjecture for \(t\le 3\) and recently Hoàng and Robin verified the conjecture for \(t=4\). In this talk, we present a proof of the conjecture for all \(t\ge 4\). The proof depends on two newly established results on cycle structures in tough graphs, which hold independent interest.
DMS Combinatorics Seminar
Sep 04, 2024 02:00 PM
328 Parker Hall
Speaker: Joseph Briggs (Auburn University)
Title: Colored ball sorting
Abstract: I will describe an algorithmic problem arising from a recently popularized puzzle format, and a beautiful extremal question asked by a large group of theoretical computer scientists. Graph-theoretic tools resolve one nontrivial instance, but otherwise, the problem is wide open.
DMS Combinatorics Seminar
Aug 28, 2024 02:00 PM
328 Parker Hall
Speaker: Chris Kapulkin, University of Western Ontario
Title: Effective computations of discrete homologyAbstract: Discrete homology is a graph invariant, known for its discerning power in analysis of social and technological networks. This talk will report on joint work with Nathan Kershaw on creating software for effective computations of this invariant. I will explain what discrete homology is and how it can be used in a variety of applied contexts, e.g., as an alternative to persistence homology in topological data analysis or as a poset invariant in systems biology.
In addition to presenting our techniques for effective computations, I will discuss some open problems of a combinatorial nature that would lead to further improvements in the software.
No prior knowledge of homology will be assumed.