2024 – 2025 Academic Year
Organized by: George Brooks (ghbrooks@email.sc.edu) and Utku Okur (uokur@email.sc.edu)
This page will be updated as new seminars are scheduled. Make sure to check back each week for information on upcoming seminars.
Many of the presentations of this seminar are recorded with the speaker's permission. These recordings can be found on the UofSC Discrete Mathematics Seminar YouTube channel.
An email is sent out each week with specifics about the upcoming talk which includes information about format, time, place, etc. If you would like to receive these emails or have other questions, please contact George Brooks or Utku Okur.
It is well known that every tournament contains a spanning path. We study a generalization to fully directed hypergraphs, where each edge comes with a total ordering of its vertices. For \( 0 \leq k \leq r! \), an \((r,k)\)-tournament is a fully directed hypergraph such that each set of \( r \) vertices spans \( k \) edges. A \((2,1)\)-tournament is just a conventional tournament. Let \( f(n,r,k) \) be the minimum, over all \((r,k)\)-tournaments \( G \) with \( n \) vertices, of the maximum size of a (tight) path in \( G \). In our language, the statement that every tournament has a spanning path becomes \( f(n,2,1) = n \).
As \( k \) increases from \( 0 \) to \( r! \), longer paths are forced. We are interested in the values of \( k \) where the growth behavior of \( f \) shifts. For example, for each \( r \), what is the minimum \( k \) such that \( f(n,r,k) \to \infty \) as \( n \to \infty \)? We call this \( k \) the growing path threshold. We show that the growing path threshold equals one plus the maximum size of an acyclic set of vertices in a particular digraph and is between \[ (1 - (1/r) - O(1/r^{2-\varepsilon}))r! \] and \[ (1 - (1/r) - (1/r!))r!. \]
We define the linear path threshold and the spanning path threshold analogously and show that these are at most \[ (1 - (1/r) + (1/r!))r! \] and \[ (1 - 1/(4(r-1)) + (1/r!))r! \] respectively. In the case \( r=3 \), specialized arguments show that \[ \Omega((\log n)^{1/4 - o(1)}) \leq f(n,3,3) \leq O(\log n), \] that \[ f(n,3,4) \geq \Omega(n^{1/5}), \] and that \[ f(n,3,5) = n. \]
Ramsey Numbers of \( k \)-Books vs. Cycles
For positive integers \( k \) and \( n \), a \( k \)-book with \( n \) pages is a graph which consists of \( n \) \((k+1)\)-cliques sharing a common \( k \)-clique.
In this talk, I will introduce our results on the Ramsey number of \( k \)-books versus cycles.
A tight ℓ-cycle minus an edge \(C_{\ell}^{-}\) is the 3-graph on the vertex set \([\ell]\), where any three consecutive vertices in the string \(123\ldots\ell1\) form an edge. We show that for every \(\ell \geq 5\), \(\ell\) not divisible by 3, the extremal number is:
\[ \text{ex}(C_{\ell}^{-},n) = \frac{1}{24} n^3 + O(n \ln n) = \left(\frac{1}{4} + o(1)\right) (n^3). \]
We determine the extremal graph up to \(O(n)\) edge edits. The proof is based on flag algebra calculations.
This is a joint work with Connor Mattes and Florian Pfender.
If \( G \) is an abelian group and \( A \) and \( B \) are subsets of \( G \), then one can define the addition of these two sets as \[ A + B = \{a + b : a \in A, b \in B\}, \] a quantity called the sumset of \( A \) and \( B \). While seemingly abstract at first, sumsets turn out to be quite useful for applications to various other areas of mathematics.
One typical style of question asks for describing the structure of \( A \) and \( B \) assuming the sumset \( A + B \) grows slowly with respect to \( |A| \) and \( |B| \). In this talk, we will focus on the case when \[ |A + B| \leq |A| + 2|B| - 4, \] assuming \( |B| \leq |A| \), particularly for \( G = \mathbb{Z} \) or modulo a prime \( p \).
There are quite good bounds for the structure in the case \( G \) is the integers. Achieving similar results in the torsion setting, particularly for high-density sets, is an ongoing project tackled by many researchers. In this talk, I'll discuss the current status, the many reasonably advanced tools used to achieve this, and some quick applications. This will include recent improvements done by myself, building upon earlier collaborative work done with Candela and Gonzalez-Sanchez.
Date: January 31, 2025 at 2:30 p.m.
Speaker: Sean English
Location: LeConte 346
Abstract:
The extremal number of the graph \(F\), denoted \(\text{ex}(n,F)\), is the maximum number of edges in an \(F\)-free graph on \(n\) vertices.
The inverse rational exponent conjecture (perhaps first posed by Erd\(\H{o}\)s and Simonovits in 1981) postulates that for each rational number \(r \in [1,2]\), there exists some graph \(F\) such that: \[ \text{ex}(n,F) = \Theta(n^r). \] Recently, Bukh and Conlon proved a slightly weaker version of this conjecture—if one allows for finite families of forbidden graphs, then such a family does exist for each rational \(r\).
We will show that a generalization of this conjecture also holds. Given two graphs \(F\) and \(H\), the generalized extremal number \(\text{ex}(n,H,F)\) is the maximum number of copies of \(H\) in an \(F\)-free graph on \(n\) vertices (note that \(\text{ex}(n,F) = \text{ex}(n,K_2,F)\)).
We will explore which rational exponents are realizable for some different graphs \(H\), and in particular show that every reasonable rational number is realizable for all cliques \(K_{\ell}\). Upper bounds will be derived from a particular counting scheme, while lower bounds will stem from a random algebraic construction.
This is joint work with Anastasia Halfpap and Bob Krueger.
When: January 24, 2025 at 2:30 pm
Speaker: Linyuan Lu
Location: LeConte 346
Abstract:
In this presentation, we will discuss several recent findings on graphs with positive Ricci curvature. These include Bonnet-Myers sharp graphs, a precise bound on the order of \( C_3 \)- and \( C_5 \)-graphs, and a comprehensive classification of outerplanar graphs with a minimum degree of at least 2.
When: Friday, January 17, 2025 at 2:30 p.m.
Speaker: Abhishek Methuku (University of Illinois Urbana-Champaign)
Location: Virtual via Zoom
Abstract: I will talk about new methods for constructing nearly Hamilton cycles in sublinear expanders, and new techniques for regularizing sublinear expanders. I will also briefly discuss how to use these methods to make progress towards some longstanding open problems. This is joint work with Shoham Letzter and Benny Sudakov.
When: Friday, December 6, 2024, at 2:30 p.m.
Speaker: Ruth Luo (University of South Carolina)
Location: LeConte 346
Abstract: A jellyfish in a graph G is a cycle C and a set of vertices X in G-C that are all adjacent to a common vertex in C. We present sufficient degree conditions for the existence of a spanning jellyfish in connected graphs. This is joint work with J. Kim and A. Kostochka.
When: Friday, November 22, 2024, at 2:30 p.m.
Speaker: George Brooks (University of South Carolina)
Location: LeConte 346
Abstract:
The spread of a graph \( G \) is the difference \( \lambda_1 - \lambda_n \) between the largest and smallest eigenvalues of its adjacency matrix. Breen, Riasanovsky, Tait, and Urschel recently determined the graph on \( n \) vertices with maximum spread for sufficiently large \( n \). In this paper, we study a related question of maximizing the difference \( \lambda_{i+1} - \lambda_{n-j} \) for a given pair \( (i,j) \) over all graphs on \( n \) vertices.
We give upper bounds for all pairs \( (i,j) \), exhibit an infinite family of pairs where the bound is tight, and show that for the pair \( (1,0) \), the extremal example is unique. These results contribute to a line of inquiry pioneered by Nikiforov aiming to maximize different linear combinations of eigenvalues over all graphs on \( n \) vertices. Based on joint work with William Linz and Linyuan Lu.
When: Friday, November 15, 2024, at 2:30 p.m.
Speaker: Josh Cooper (University of South Carolina)
Location: LeConte 346
Abstract:
Motivated by the problem of generalizing the Graham-Pollack Theorem on determinants of trees’ distance matrices, we consider the sign of the hyperdeterminant of trees’ Steiner distance hypermatrices of higher orders than 2. Previously, with Tauscheck and Du, we showed that this hyperdeterminant is 0 for odd orders, but we conjecture that the sign is \( (-1)^{n-1} \) for even order, where \( n \) is the number of vertices of the tree.
Let \( H \) denote that codimension 1 subspace of \( \mathbb{R}^n \) orthogonal to the all-ones vector. A matrix \( M \) is "conditionally strictly negative definite" – or CSND – if, for all nonzero vectors \( v \in H \), \( v^T M v < 0 \). If \( M \in \mathbb{R}^{n \times n} \) is CSND, then the sign of \( \det(M) \) is \( (-1)^{n-1} \).
We show that even-order Steiner distance hypermatrices of trees are also CSND. The proof also demonstrates that they diagonalize on \( H \) by rewriting with respect to a combinatorially interesting basis. Joint work with Zhibin Du.
When: Friday, November 8, 2024, at 2:30 p.m.
Speaker: Alec Helm (University of South Carolina)
Location: LeConte 346
Abstract: A tanglegram is a pair of rooted binary trees along with a perfect matching of their leaf sets. Tanglegrams are drawn with straight lines in the plane such that their trees are drawn as plane trees with their leaves placed on two parallel lines, and the strip between these lines contains only the edges of the leaf matching. The crossing number of such a drawing is the number of unordered pairs of edges which intersect each other. In this talk I will present a characterization of tanglegrams with crossing number at least two. This characterization will include bounding the size of characteristic substructures of such tanglegrams as well as a thorough computer-assisted search.
When: Friday, November 1, 2024, at 2:30 p.m.
Speaker: Vladislav Taranchuk (University of Delaware)
Location: Virtual via Zoom
Abstract: In this talk, we will introduce a family of graphs commonly referred to as algebraically defined graph. We will see how these graphs relate to other fields in discrete mathematics and how they have been used to provide best-known bounds various extremal questions, such as the Turan number ex(n,Ck). We will also mention some open questions regarding these graphs.
When: Friday, October 25, 2024, at 2:30 p.m.
Speaker: Himanshu Gupta (University of Regina)
Location: Virtual via Zoom
Abstract: In 1995, Lazebnik and Ustimenko introduced the family ofq-regular graphsD(k,q), which is defined for any positive integerkand prime powerq. The connected components of the graphD(k,q)have provided the best-known general lower bound on the size of a graph for any given order and girth to this day. Furthermore, Ustimenko conjectured that the second largest eigenvalue ofD(k,q)is always less than or equal to2q, indicating that the graphsD(k,q)are almost Ramanujan graphs. In this talk, we will discuss some recent progress on this conjecture. This includes the result that the second largest eigenvalue ofD(5,q)is less than or equal to2qwhenqis an odd prime power. This is joint work with Vladislav Taranchuk.
When: Friday, October 11, 2024, at 2:30 p.m.
Speaker: Josiah Reiswig (Anderson University)
Location: LeConte 346
Abstract: In 1957, while investigating questions related to Steiner triple systems, Thoralf Skolem examined the existence of integer sequences of the form \(a_1,a_2,\ldots,a_{2n}\) satisfying the following three conditions:
- \(1\leq a_i\leq n\) for each \(1\leq i\leq 2n\),
- For each integer \(1\leq m\leq n\), there are exactly two distinct indices \(1\leq i,j\leq 2n\) with \(a_i=a_j=m\), and
- If \(a_i=a_j=m\) with \(i\neq j\), then \(|i-j|=m\). For \(n=4\), an example of such a sequence is \(41134232\).
Such sequences are known as Skolem sequences and exist if and only if \(n\equiv 0,1
\mod 4\). Since a sequence may be thought of as a labeled path, Nabil Shalaby, in
his 1991 PhD thesis, introduced the notion of Skolem labelings to graphs. We will
extend the definition of Skolem labelings to Steiner \(k\)-Skolem labelings using
the Steiner distance of graphs and prove the existence of Steiner \(k\)-Skolem labelings
for paths (i.e. sequences) and extend some results of Shalaby for general graphs.
Open problems will also be discussed.
This is a joint work with Inne Singgih and Zhiyu Wang.
When: Friday, October 4, 2024, at 2:30 p.m.
Speaker: Anna Halfpap (Iowa State University)
Location: Virtual via Zoom
Abstract: Given two graphs \(F\), \(G\), we say that \(G\) is \(F\)-saturated if \(G\) does not contain \(F\) as a subgraph, but for any \(e \not\in E(G)\), the graph \(G+e\) contains a copy of \(F\). Consideration of \(F\)-saturated graphs makes up a cornerstone of classical extremal combinatorics: the well-studied Turán and saturation numbers \(\mathrm{ex}(n,F)\) and \(\mathrm{sat}(n,F)\) ask for, respectively, the maximum and minimum number of edges in an \(n\)-vertex, \(F\)-saturated graph. More recently, a number of variations and generalizations of Turán and saturation questions have become popular, asking for the maximum or minimum number of edges (or of another fixed subgraph) subject to an appropriately modified saturation condition. In particular, a graph \(G\) is (properly) rainbow F-saturated if \(G\) admits a proper edge-coloring which contains no rainbow copy of \(F\) (i.e., no copy of \(F\) in which all edges receive different colors), but for any non-edge \(e\) of \(G\), every proper edge-coloring of \(G+e\) contains a rainbow copy of \(F\). The rainbow Turán number \(\mathrm{ex^*}(n,F)\), introduced by Keevash, Mubayi, Sudakov, and Verstraetë, asks for the maximum number of edges in an \(n\)-vertex, properly rainbow \(F\)-saturated graph. The (proper) rainbow saturation number \(\mathrm{sat^*}(n,F)\) is the minimum number of edges in an \(n\)-vertex, properly rainbow \(F\)-saturated graph, recently introduced by Bushaw, Johnston, and Rombach. In this talk, we discuss several recent results which asymptotically determine the rainbow saturation numbers for a variety of graphs. Joint work with Bernard Lidick´y and Tomáš Masařík, and with the 2024 Iowa State RTG research group.
When: Friday, September 27, 2024, at 2:30 p.m.
Speaker: William Linz (University of South Carolina)
Location: Virtual via Zoom
Abstract: For a \(k\)-uniform hypergraph \(\mathcal{H}\), the codegree squared sum is the square of the \(\ell_2\)-norm of the codegree vector of \(\mathcal{H}\), and for a family \(\mathscr{F}\) of \(k\)-uniform hypergraphs, the codegree squared extremal number is the maximum codegree squared sum of a hypergraph on \(n\) vertices which does not contain any hypergraph in \(\mathscr{F}\). Balogh, Clemen and Lidický recently introduced the codegree squared extremal number and determined it for a number of \(3\)-uniform hypergraphs. We show several exact or asymptotic results for the codegree squared extremal number, including the first exact results for \(k\)-uniform hypergraphs. Based on joint work with George Brooks.
When: Friday, September 20, 2024, at 2:30 p.m.
Speaker: Van Magnan (University of Vermont)
Location: Virtual via Zoom
Abstract: The minimum positive co-degree of a non-empty \(r\)-graph \(H\), denoted \(\delta_{r-1}^+(H)\), is the largest integer \(k\) such that if a set \(S \subset V(H)\) of size \(r-1\) is contained in at least one \(r\)-edge of \(H\), then \(S\) is contained in at least \(k\) \(r\)-edges of \(H\). Motivated by several recent papers which study minimum positive co-degree as a reasonable notion of minimum degree in \(r\)-graphs, we asymptotically determine the minimum positive co-degree threshold for loose Hamiltonian cycles in \(3\)-graphs, and discuss the proof (and absorbing method used) in this talk.
When: Friday, September 13, 2024, at 2:30 p.m.
Speaker: Sam Spiro
Location: Virtual via Zoom
Abstract: Let \(G_{n,p}\) denote the random \(n\)-vertex graph obtained by including each edge independently and with probability \(p\). Given a graph \(F\), let \(\mathrm{ex}(G_{n,p},F)\) denote the size of a largest \(F\)-free subgraph of \(G_{n,p}\). When \(F\) is non-bipartite, the asymptotic behavior of \(\mathrm{ex}(G_{n,p},F)\) is determined by breakthrough work done independently by Conlon-Gowers and by Schacht, but the behavior for bipartite \(F\) remains largely unknown. We will discuss some recent developments that have been made for bipartite \(F\), as well as for the analogous problem on \(r\)-partite \(r\)-graphs which turns out to have a surprising connection to Sidorenko's conjecture. Based on various joint works with Jiaxi Nie, Gwen McKinley, and Jacques Verstraete.
When: Friday, September 6, 2024, at 2:30 p.m.
Speaker: Jan Hladky (The Czech Academy of Sciences)
Location: Virtual via Zoom
Abstract: In a mammoth project starting in 2005, Bollobás, Janson, and Riordan introduced a broad class of random graph models called "inhomogeneous random graphs." Just as the study of the "giant component" phenomenon in classical Erdős-Rényi random graphs is reflected in certain Galton-Watson branching processes, the study of the giant component in inhomogeneous random graphs is linked with certain inhomogeneous Galton-Watson branching processes. We characterize inhomogeneous random graph models that yield the same inhomogeneous Galton-Watson branching process (and hence have a similar component structure).
When: Friday, August 30, 2024, at 2:30 p.m.
Speaker: Utku Okur (University of South Carolina)
Location: LeConte 346
Abstract: The Heaps of Pieces framework, discovered by Viennot in 1986, can be applied to an
Eulerian digraph \(D\) with distinguishable multi-edges, where the pieces are directed
cycles, and the concurrence relation is sharing a vertex. For a given edge \(e\in
E(D)\), we describe a one-to-one correspondence between \(e\)-pyramids, i.e., heaps
with a unique maximal piece containing \(e\), and the closed walks of \(D\), ending
at \(e\). We also prove that a cancellation property is satisfied, namely, that the
alternating sum, over \(t\geq 1\), of \((-1)^t\) times the number of decompositions
of Eulerian circuits of \(D\) into \(t\) parts is zero, unless \(D\) is a single directed
cycle.
Previous Years
When: April 19th at 2:30 p.m.
Speaker: Jonad Pulaj (Davidson College)
Location: Virtual via Zoom
Abstract: In the first part of this talk we give a brief overview of computer-assisted results in combinatorics, before focusing on building safe computational frameworks for Frankl's conjecture combining mixed integer and linear programming (MILP) with satisfiability modulo theories (SMT). The conjecture states that for any finite union-closed family of sets which contains a non-empty set, there exists an element in the union of sets of the family that is present in at least half the sets in the family. Our framework facilitates and/or inspires various results including the following. We find new values and bounds for the least integer m such that any family containing m distinct k-sets of an n-set X satisfies Frankl's conjecture with an element of X. Furthermore, we settle an older question of Vaughan about symmetry in union-closed families and we prove a recent question posed by Ellis, Ivan and Leader.
In the last part of this talk we focus on general best practices and desirable standards for computer-assisted results, before focusing on the verification of answers obtained from MILP certificates using SMT solvers. We present an SMT-based tool that checks the VIPR certificate, the first proof format for the correctness of answers produced MILP solvers. This checker is based on the equivalence between the correctness of a VIPR certificate and the satisfiability of a formula in the theory of linear/integer real arithmetic. Finally we demonstrate the effectiveness of this approach and its variations by evaluating them on existing benchmark instances.
Collaborators in these projects include Hammurabi Mendes, Kenan Wood, Haoze (Andrew) Wu, and Runtian (Daniel) Zhou.
When: April 12th at 2:30 p.m.
Speaker: Michael Levet (College of Charleston)
Location: LeConte 103
Abstract: The Graph Isomorphism problem takes as input two finite graphs \(G\) and \(H\), and asks if \(G \cong H\). It is a longstanding open problem whether Graph Isomorphism is solvable in polynomial-time. In this talk, we will discuss recent advances in the computational complexity of identifying graphs of bounded rank-width, a class of dense graphs for which isomorphism testing has only recently been shown to belong to \(\textsf{P}\). Precisely, we will show that \(O(\log n)\) rounds of the constant-dimensional Weisfeiler--Leman algorithm serves as a complete isomorphism test for this family. This, in particular, improves the complexity-theoretic upper bound from \(\textsf{P}\) to \(\textsf{TC}^{1}\). We then leverage the Weisfeiler--Leman algorithm as a subroutine, to obtain a \(\textsf{TC}^{2}\) algorithm to compute canonical labelings for this family.
This is joint work with Puck Rombach and Nicholas Sieger.
When: April 5th at 2:30 p.m.
Speaker: Maria-Romina Ivan (University of Cambridge)
Location: Virtual via Zoom
Abstract: The Turán density of an \(r\)-uniform hypergraph \(H\), denoted by \(\pi(H)\), is the limit of the maximum density of an \(n\)-vertex \(r\)-uniform hypergraph not containing a copy of \(H\), as \(n\) tends to infinity. An \(r\)-daisy is an \(r\)-uniform hypergraph consisting of the six \(r\)-sets formed by taking the union of an \((r-2)\)-set with each of the \(2\)-sets of a disjoint \(4\)-set. Bollobás, Leader and Malvenuto, and also Bukh, conjectured that the Turán density of the \(r\)-daisy is zero. A folklore Turán-type conjecture for hypercubes states that for fixed \(d\) the smallest set of vertices of the \(n\)-dimensional hypercube \(Q_n\) that meets every copy of \(Q_d\) has density \(1/(d+1)\) as \(n\) goes to infinity. In this talk, we show that the Turán density for daisies is positive, and, by adapting our construction, we also disprove the hypercube conjecture mentioned above. Joint work with David Ellis and Imre Leader.
When: March 29th at 2:30 p.m.
Speaker: Zhiyu Wang (Louisiana State University)
Location: Virtual via Zoom
Abstract: The oriented diameter of an undirected graph \(G\) is the minimum diameter of an orientation of \(G\) over all strongly connected orientations of \(G\). In this talk, we will discuss some recent progress on the oriented diameter of some graph classes including connected graphs with minimum degree \(\delta\) and planar triangulations.
When: March 22nd at 2:30 p.m.
Speaker: Megan Cream (Lehigh University)
Location: Virtual via Zoom
Abstract: This talk explores various conditions that imply certain cycle properties in graphs. A graph G of order n is called pancyclic if it contains a cycle of every possible length from 3 to n, and a cycle C is chorded if there is an edge between two vertices that are non-adjacent on C. In this talk, we define multiple relaxations of pancyclic graphs and we extend those cycle properties to chorded cycle properties. In 1971, Bondy proposed a meta-conjecture stating that any condition implying hamiltonicity in a graph will also imply pancyclicity. In 2017, we extended this meta-conjecture to say any condition implying hamiltonicity will also imply chorded pancyclicity. The results discussed in this talk are evidence that support this new meta-conjecture.
When: March 15th at 2:30 p.m.
Speaker: Lina Li (Iowa State University)
Location: Virtual via Zoom
Abstract: The Acyclic Edge Coloring Conjecture, posed independently by Fiamčik in 1978 and Alon, Sudakov and Zaks in 2001, states that every graph can be properly edge colored with \(\Delta+2\) colors such that there is no bicolored cycle. Over the years, this conjecture has attracted much attention. We prove that the conjecture holds asymptotically, that is \((1+o(1))\Delta\) colors suffice. This is joint work with Michelle Delcourt and Luke Postle.
When: March 1st at 2:30 p.m.
Speaker: Michael Tait (Villanova University)
Location: LeConte 103
Abstract: A subset of integers A is a \(B_k[g]\) set if the number of multisets of A of size k which sum to any fixed integer is bounded above by g. How large can a \(B_k[g]\) set of integers up to n be? We will discuss what is known about \(B_k[g]\) sets and how these objects are related to extremal graph theory. This is joint work with Griffin Johnston and Craig Timmons.
When: February 23rd at 2:30 p.m.
Speaker: Stephan Wagner (Uppsala University)
Location: Virtual via Zoom
Abstract: We consider random digraphs in a directed version of the classical Erdős–Rényi model: given n vertices, each possible directed edge is inserted with probability p, independently of the others. It turns out that these graphs undergo a phase transition when p is about 1/n, which can be seen in the answer to questions such as: what is the probability that there are no directed cycles (equivalently, that all strongly connected components are singletons)? Using methods from analytic combinatorics, we obtain very precise asymptotic answers to questions of this kind.
When: February 16th at 2:30 p.m.
Speaker: Nika Salia (King Fahd University)
Location: Virtual via Zoom
Abstract: In our talk, we study embeddings of planar graphs on a plane and explore the limits of deviating from optimal behavior. We introduce the concept of a plane-saturated subgraph for a planar graph, defined as a subgraph where adding any edge would compromise planarity or no longer maintain its status as a subgraph. Our focus lies on quantifying this phenomenon through the plane-saturation ratio, denoted as \(psr(G)\), which measures the minimum ratio of edges in a plane-saturated subgraph to the total edges in the original graph \(G\). While some planar graphs have arbitrarily small \(psr(G)\), we show that for all twin-free planar graphs, \(psr(G)>1/16\), and that there exist twin-free planar graphs where \(psr(G)\) is arbitrarily close to \(1/16\).
Joint work with Dr. Alexander Clifton, Institute for Basic Science.
When: February 9th at 2:30 p.m.
Speaker: George Brooks (University of South Carolina)
Location: LeConte 103
Abstract: In differential geometry, the Ricci curvature of a Riemannian manifold is, roughly speaking, a measure of how much the manifold differs from Euclidean space. Curvature in the continuous setting has been studied in depth throughout the past 200 years, and more recent interest has arisen in establishing analogous results in the discrete setting. While Riemannian manifolds generally behave quite differently than graphs, we can use random walks to define the Ricci curvature on graphs. In this talk, we'll review Lin-Lu-Yau curvature and consider the question: Can we determine an upper bound on the order for all positively curved graphs in graph class?
When: February 2nd at 2:30 p.m.
Speaker: Utku Okur (University of South Carolina)
Location: LeConte 103
Abstract: We show that, in general, the characteristic polynomial of a hypergraph is not determined by its "polynomial deck", the multiset of characteristic polynomials of its vertex-deleted subgraphs, thus settling the "polynomial reconstruction problem" for hypergraphs in the negative. The proof proceeds by showing that a construction due to Kocay of an infinite family of pairs of 3-uniform hypergraphs which are non-isomorphic but share the same hypergraph deck, in fact, have different characteristic polynomials. The question remain unresolved for ordinary graphs.
When: January 26th at 2:30 p.m.
Speaker: Carl Yerger (Davidson College)
Location: LeConte 103
Abstract: Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration of pebbles, at least one pebble can be moved to a specified target vertex. In this talk, we will give a survey of several streams of research in pebbling, including describing a theoretical and computational framework that uses mixed-integer linear programming to obtain bounds for the pebbling numbers of graphs. We will also discuss improvements to this framework through the use of newly proved weight functions that strengthen the weight function technique of Hurlbert. Finally, we will discuss some open extremal problems in pebbling, specifically related to Class 0 graphs and describe how structural graph theoretic techniques such as discharging can be used to obtain results.
Collaborators on these projects include Dan Cranson, Dominic Flocco, Luke Postle, Jonad Pulaj, Chenxiao Xue, Marshall Yang, Daniel Zhou.
When: January 19th at 2:30 p.m.
Speaker: Tom Kelly (Georgia Tech)
Location: LeConte 346
Abstract: In this talk, we will discuss robustness results which lie in the intersection of both extremal and probabilistic combinatorics.
In joint work with Kang, Kühn, Methuku, and Osthus, we proved the following: If \(p\geq{C\log^2n/n}\) and \(L_{i,j}\subseteq[n]\) is a random subset of \([n]\) where each \(k\in[n]\) is included in \(L_{i,j}\) independently with probability \(p\) for each \(i,j\in[n]\), then asymptotically almost surely there is an order-\(n\) Latin square in which the entry in the \(i\)th row and \(j\)th column lies in \(L_{i,j}\). We prove analogous results for Steiner triple systems and \(1\)-factorizations of complete graphs. These results can be understood as stating that these "design-like" structures exist "robustly".
In joint work with Kang, Küuhn, Osthus, and Pfenninger, we proved various results stating that if \(\mathcal{H}\) is an \(n\)-vertex \(k\)-uniform hypergraph satisfying some minimum degree condition and \(p=\Omega(n^{-k+1}\log n)\), then asymptotically almost surely a \(p\)-random subhypergraph of \(\mathcal{H}\) contains a perfect matching. These results can be understood as "robust" versions of hypergraph Dirac-type results as they simultaneously strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem on the threshold for when a binomial random \(k\)-uniform hypergraph contains a perfect matching. In joint work with Müyesser, and Pokrovskiy, we proved similar results for hypergraph Hamilton cycles.
All of these results utilize the recent Park—Pham Theorem or one of its variants. A crucial notion for this is that of the spreadness of a certain type of probability distribution.
When: January 12th at 2:30 p.m.
Speaker: Leslie Hogben (Iowa State University)
Location: Virtual via Zoom
Abstract: Zero forcing is an iterative process that repeatedly applies a rule to change the
color of vertices of a graph G from white to blue. The zero forcing number is the minimum number of initially blue
vertices that are needed to color all vertices blue through this process. Standard
zero forcing was introduced about fifteen years ago in the control of quantum systems
and as an upper bound for maximum multiplicity of an eigenvalue (or maximum nullity)
among matrices having off-diagonal nonzero pattern described by the edges of the graph
G, and rediscovered later both as part of power domination and as fast-mixed graph
searching.
Whether a set is a zero forcing set can be tested using a certain type of set called
a fort, which obstructs zero forcing. The maximum number of disjoint forts (fort
number) provides another lower bound for the zero forcing number; results about
fort number will be discussed. Forts can be used in integer programs to determine
the zero forcing number and fort number. The relaxation of these integer programs
leads to dual linear programs that define the fractional zero forcing number, or equivalently,
the fractional fort number, and results about these parameters will be discussed.
There is a well-known upper bound for the zero forcing number of a Cartesian product
in terms of the zero forcing numbers and orders of the constituent graphs. The question
of a lower bound for the zero forcing number of a Cartesian product has recently been
studied. It is easy to see that there is a Vizing-like lower bound when the constituent
graphs of the Cartesian product both have maximum nullity equal to zero forcing number.
Fractional zero forcing and fort number provide additional lower bounds on the the
zero forcing number of a Cartesian product in terms of parameters of the constituent
graphs.
When: December 8th at 2:30 p.m.
Speaker: Gabor Hetyei (UNC Charlotte)
Location: LeConte 103
Abstract: The tensor product of a graph and of a pointed graph is obtained by replacing each
edge of the first graph with a copy of the second. In this expository talk we will
explore a colored generalization of Brylawski's formula for the Tutte polynomial
of the tensor product of a graph with a pointed graph and its applications. Using
Tutte's original (activity-based) definition of the Tutte polynomial we will provide
a simple proof of Brylawski's formula. This can be easily generalized to the colored
Tutte polynomials introduced by Bollobas and Riordan. Consequences include formulas
for Jones polynomials of (virtual) knots and for invariants of composite networks
in which some major links are identical subnetworks in themselves.
All results presented are joint work with Yuanan Diao, some of them are also joint
work with Kenneth Hinson. The relevant definitions and the fundamental results used
will be carefully explained.
When: December 1st at 2:30 p.m.
Speaker: Miles Bakenhus (Illinois Institute of Technology)
Location: Virtual via Zoom
Abstract: The set of nonnegative integer lattice points in a polytope, also known as the fiber of a linear map, makes an appearance in several applications including optimization and statistics. We address the problem of sampling from this set using three ingredients: an easy-to-compute lattice basis of the constraint matrix, a biased sampling algorithm with a Bayesian framework, and a step-wise selection method. The bias embedded in our algorithm updates sampler parameters to improve fiber discovery rate at each step chosen from previously discovered elements. We showcase the performance of the algorithm on several examples, including fibers that are out of reach for the state-of-the-art Markov bases samplers. Potential applications in integer optimization are considered as well.
When: November 17th at 2:30 p.m
Speaker: David Galvin (University of Notre Dame)
Location: LeConte 103
Abstract: In the late 1980's, motivated by a problem from combinatorial group theory, Andrew
Granville asked "at most how many independent sets can a regular graph admit?" This
has proven to be a remarkably fruitful question, and one amenable to a remarkable
variety of techniques, including graph containers, entropy and linear programming.
Although Granville's initial question has by now been completely resolved (first by
Kahn, for regular bipartite graphs, then by Zhao for all regular graphs), many related
open questions remain.
I'll discuss this problem, and some of its relatives, including maximizing the count
of H-colorings of a regular graph, minimizing the count of H-colorings of a tree,
and maximizing the count of independent sets in a regular graph in the presence of
a bound on the largest independent set in the graph.
When: November 10th at 2:30pm
Speaker: Nicholas Sieger (University of California; San Diego)
Location: Virtual via Zoom
Abstract: We introduce a random graph model for clustering graphs with a given degree sequence. Unlike many previous random graph models, we incorporate clustering effects into the model. We show that random clustering graphs can construct graphs with a power-law expected degree sequence, small diameter, and any desired clustering coefficient. Our results follow from a general theorem on subgraph counts which may be of independent interest.
When: November 3rd at 2:30pm
Speaker: Clifford Smyth (UNC Greensboro)
Location: Virtual via Zoom
Abstract: The reciprocal of \(e^{-x}\) is \(e^x\) and \(e^{x} = sum_{n=0}^\infty x^n/n!\) is
"totally non-negative" in the sense that it has a power series with all non-negative
coefficients.
What about "thinned versions" of \(e^{-x} = 1 + \sum_{n=1}^\infty (-1)^n x^n/n!\),
i.e. functions of the form \(f_A(x) = 1 + \sum{n \in A} (-1)^n x^n/n!\) where \(A\)
is some subset of the positive integers? For which \(A\) does \(f_A\) have a totally
non-negative reciprocal? Gessel showed that \(A = \{1,2,...,2m\}\) does not work,
but \(A = \{0,1,...,2m+1\}\) does. In fact, he showed that in the latter case, \(1/f_A(x)
= \sum_n c(n) x^n/n!\) where \(c(n)\) counts the number of elements in class \(C(n)\)
of combinatorially defined objects. \(C(n)\) turns out to be the permutations of
\(\{1,...,n\}\) in which the length of every maximal increasing subsequence is congruent
to 0 or 1 mod 2m. Thus, Gessel showed that \(1/f_A(x)\) is totally non-negative for
a "combinatorially interesting" reason when \(A = \{1,...,2m+1\}\).
We extend this result by showing that \(1/f_A(x)\) is totally non-negative for any
\(A\) that contains 1 and is "odd-ended". By odd-ended, we mean that \(A\) has all
of its maximal intervals of consecutive members ending in odd integers, like \(A =
\{1,2,3\} \cup \{5,6,7\} \cup \{11\} \cup \{15,16,...., \infty\}\). We too give combinatorially
interesting reasons for this. For each such \(A\), we show that \(1/f_A(x) = \sum_n
c(A,n) x^n/n!\) where \(c(A,n)\) counts the number of elements in a class \(C(A,n)\)
of combinatorially defined objects. We push things a little further than that as
well, finding a lot more "good" \(A\)'s than the odd-ended ones.
This is joint work with David Galvin of the University of Notre Dame and John Engbers
of Marquette University.
When: October 27th at 2:30pm
Speaker: Stacie Baumann (College of Charleston)
Location: Virtual via Zoom
Abstract: An (n,k,t)-graph is a graph on n vertices in which every set of k vertices contain a clique on t vertices. Turán's Theorem (complemented) states that the unique minimum (n,k,2)-graph is a disjoint union of cliques. We prove that minimum (n,k,t)-graphs are always disjoint unions of cliques for any t (despite nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al. This is joint work with Joseph Briggs.
When: October 6th at 2:30pm
Speaker: Ryan Martin (Iowa State University)
Abstract: Basic Turan theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Turan question asks how many copies of a fixed subgraph \(H\) the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of \(bf N_{\mathcal P}(n,H)\), which denotes the maximum number of copies of \(H\) in an \(n\)-vertex planar graph. In particular, we will focus on the case where \(H\) is a cycle. It was determined that \(bf N_{\mathcal P}(n,C_{2m}) = (n/m)^m + o(n^m)\) for small values of \(m\) by Cox and Martin and resolved for all \(m\) by Lv, Gy\H{o}ri, He, Salia, Tompkins, and Zhu. The case of \(H=C_{2m+1}\) is more difficult and it is conjectured that \(bf N_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m)\). We will duscuss recent progress on this problem, including verification of the conjecture in the case where \(m=3\) and \(m=4\) and a lemma which reduces the solution of this problem for any \(m\) to a so-called ''maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory. This is joint work with Emily Heath and Chris (Cox) Wells.
When: September 29th at 2:30pm
Speaker: Grace McCourt (University of Illinois at Urbana-Champaign)
Abstract: Dirac 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 a hypergraph version of this result. A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges v1,e2,v2, ... , ec, v1 such that {vi,vi+1} ⊆ ei for all i (with indices taken modulo c). We prove that for n ≥ k ≥ r+2 ≥ 5, every 2-connected r-uniform n-vertex hypergraph with minimum degree at least {k-1 \choose r-1} + 1 has a Berge cycle of length at least min{2k, n}. The bound is exact for all k ≥ r+2 ≥ 5. This is joint work with Alexandr Kostochka and Ruth Luo.
When: September 22nd at 2:30pm
Speaker: Ruth Luo (University of South Carolina)
Abstract: Let A and B be 0,1-matrices. We say A contains B as a configuration if there exists a submatrix of A that is a row and column permutation of B. In the special case where A and B are incidence matrices of graphs G and H respectively, A contains B as a configuration if and only if B is a subgraph of A. We discuss some extremal problems where A and B are incidence matrices of (hyper)graphs.
When: September 15th 2023 at 2:30pm
Speaker: Sebastian Cioaba (University of Delaware)
Abstract: Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material sciences, engineering and biological sciences. In 1982, Lovasz and Yemini proved that every 6-connected graph is rigid. Consequently, if Fiedler’s algebraic connectivity is greater than 5, then G is rigid. In recent work with Sean Dewar and Xiaofeng Gu, we showed that for a graph G with minimum degree d>5, if its algebraic connectivity is greater than 2+1/(d-1), then G is rigid and if its algebraic connectivity is greater than 2+2/(d-1), then G is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least 8 is globally rigid. Time permitting, I will report on another recent work with Sean Dewar, Georg Grasegger and Xiaofeng Gu extending these results to valencies smaller than 8.
When: September 8th 2023 at 2:30pm
Speaker: Bruce Sagan (Michigan State University)
Abstract: Let t be a positive integer and let G be a combinatorial graph with vertices
V and edges E. A proper coloring of G from a set with t colors is a function c :
V → {1, 2, . . . , t} such that if uv ∈ E then c(u) ̸= c(v), that is, the endpoints
of an edge must be colored differently. These are the colorings considered in
the famous Four Color Theorem. The chromatic polynomial of G, P(G;t),
is the number of proper colorings of G from a set with t colors. It turns out
that this is a polynomial in t with many amazing properties. For example,
there are connections with acyclic orientations, hyperplane arrangements and
symmetric functions. This talk will survey some of these results.
When: September 1st 2023 at 2:30pm
Speaker: William Linz (University of South Carolina)
Abstract: For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.
Ruth Luo, University of South Carolina
- Sep 23
- 2:30pm
Abstract: A graph is hamiltonian-connected if for every pair of vertices u and v there exists a hamiltonian path from u to v. It is easy to see that hamiltonian-connectness implies hamiltonicity in graphs. In this talk, we consider r-uniform hypergraphs and give sufficient conditions for the existence of hamiltonian Berge paths between any pair of vertices. It is also shown that this property in hypergraphs does not necessarily imply the existence of a hamiltonian Berge cycle.This is joint work with Alexandr Kostochka and Grace McCourt
Himanshu Gupta, University of Delaware
- Sep 23
- 2:30pm
Abstract: Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs. This is joint work with Sebastian M. Cioaba (University of Delaware), Ferdinand Ihringer (Ghent University), and Hirotake Kurihara (Yamaguchi University).
Joshua Cooper, University of South Carolina
- Sep 16
- 2:30pm
Abstract: A problem that arose in computational phylogenetics led to study of so-called "successful pressing sequences" on graphs, permutations of the vertices with a certain elimination-type property. It turns out that the success of a given pressing sequence can be stated in a number of interesting ways, one of which is a linear-algebraic condition on the graph’s adjacency matrix over GF(2) that is formally almost identical to semi-definiteness over \(\mathbb{R}\). We explore which classical properties of semi-definiteness carry over to GF(2) and other finite fields, and which ones fail. Joint work with Erin Hanna and Hays Whitlatch.
William Linz, University of South Carolina
- Sep 9
- 2:30pm
Abstract: A family of sets F is d-wise, t-intersecting if any d sets from F contain at least t elements in common. In this talk, I will state and prove analogues of the classical Erdős-Ko-Rado and Hilton-Milner theorems for d-wise, t-intersecting families, improving upon several earlier results by a number of authors, including O'Neill-Verstraete and Tokushige. I will also discuss various extensions of these results. Time permitting, I will indicate how d-wise, t-intersecting families can be used to construct \(K_{s,t}\)-intersecting families of size larger than the trivial construction, answering a question of Ellis. This is joint work with Jozsef Balogh.
Yan Zhaung, Davidson College
- Sep 2
- 2:30pm
Abstract: The Goulden–Jackson cluster method, adapted to permutations by Elizalde and Noy, reduces the problem of counting permutations by occurrences of a prescribed consecutive pattern to that of counting clusters, which are special permutations with a lot of structure. Recently, the speaker proved a lifting of the cluster method to the Malvenuto–Reutenauer algebra, which specializes to Elizalde and Noy's cluster method for permutations as well as new formulas which refine by additional permutation statistics, namely the inverse descent number ides, the inverse peak number ipk, and the inverse left peak number ilpk. Thus, if σ is a consecutive pattern and we can count σ-clusters by ides, ipk, or ilpk, then we can count all permutations by occurrences of σ jointly with the corresponding statistic.This talk will survey results on counting clusters by the statistics ides, ipk, and ilpk. Special attention will be given to the pattern 2134...m; in joint work with Sergi Elizalde and Justin Troyka, we show that 2134...(r+1)-clusters are equinumerous with r-Stirling permutations introduced by Gessel and Stanley, and we establish some joint equidistributions between these two families of permutations.
Leslie Hogben, Iowa State University and American Institute of Mathematics
- Aug 26
- 2:30pm
Abstract: Zero forcing is an iterative process that repeatedly applies a rule to fill vertices of a graph. The zero forcing number is the minimum number of initially filled vertices that are needed to fill all vertices through the process, and is denoted by Z(G). The maximum multiplicity of an eigenvalue (or maximum nullity) among matrices having off-diagonal nonzero pattern described by the edges of the graph G is denoted by M(G). It is known that M(G) <= Z(G), and this relationship is one of the origins of zero forcing (and the source of its name). Several variants of zero forcing number and maximum nullity, such as positive semidefinite zero forcing number and maximum nullity, have also been studied. For each variant of zero forcing, other parameters of interest include the propagation time (number of rounds needed to fill all vertices) and throttling number (which minimizes a combination of resources used to accomplish a task and rounds needed to accomplish it). This talk will survey results on extreme values of various zero forcing numbers, propagation times, throttling numbers, and maximum nullities.
Bill Kay, Pacific Northwest National Laboratory
- Apr 29
- 2:30pm
Abstract: In this talk, I will discuss how discrete geometry can play a role in data classification. Namely, I will introduce a data augmentation technique which provably reduces misclassification error without increasing training time for linear classifiers, and discuss the efficacy of this technique empirically on other kinds of classifiers. The talk will include a gentle introduction to relevant data classification discrete geometry methods involved, so no specific prior knowledge is required.
David Galvin, University of Notre Dame
- April 15
- 2:30pm
Abstract: Morse theory seeks to understand the shape of a manifold by studying smooth functions on it. Though the objects involved are inherently continuous, the study of Morse functions can lead to interesting and non-trivial combinatorial questions.
Heather Blake, Davidson College
- April 8
- 2:30pm
Abstract: Given a problem and a set of feasible solutions to that problem, the associated reconfiguration problem involves determining whether one feasible solution can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.
Any reconfiguration problem can be modelled with a reconfiguration graph, where the vertices represent the feasible solutions and two vertices are adjacent if and only if the corresponding feasible solutions can be transformed to each other via one allowable move.
Our interest is in reconfiguring dominating sets of graphs. The domination reconfiguration graph of a graph \(G\), denoted \({\mathcal D}(G)\), has a vertex corresponding to each dominating set of \(G\) and two vertices of \({\mathcal D}(G)\) are adjacent if and only if the corresponding dominating sets differ by the deletion or addition of a single vertex.
We are interested in properties of domination reconfiguration graphs. For example, it is easy to see that they are always connected and bipartite. While none has a Hamilton cycle, we explore families of graphs whose reconfiguration graphs have Hamilton paths.
Gregory Clark, University of Oxford
- April 1
- 2:30pm
Abstract: Measuring and interpreting the centrality of vertices in a graph is critical to numerous problems. Recently, the principal eigenvector of a hypergraph has received increasing attention from academics and practitioners alike. In particular, hypergraph network models exhibit desirable properties such as admitting heterogeneous data types. Despite the increasing attention, there is still hesitance for adopting these models. One reason for this is a fundamental question: are the insights gained from a hypergraph ‘distinct enough’ from the graph case to warrant a new methodology? We present evidence in the affirmative by considering the spectral ranking of a hypergraph and its shadow; that is, the ranking of vertices according to the principal eigenvector of the associated hypermatrix and the traditional co-occurrence matrix. To this end, we present the first known example of a hypergraph whose most central node varies under the shadow operation. We explore this topic by presenting several examples and results which highlight the mechanisms underpinning this phenomenon.
Hays Whitlatch, Gonzaga University
- March 25
- 2:30pm
Abstract: Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this presentation we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time. This is joint work with Kat Shultis (Gonzaga University) and three undergraduate students: Lana Kniahnitskaya, Michele Ortiz, and Olivia Ramirez.
Jozsef Balogh, University of Illinois Urbana-Champaign
- March 15
- 2:30pm
Abstract: A classical combinatorial number theory problem is to determine the maximum size of a Sidon set of \(\{ 1, 2, \ldots, n\}\), where a subset of integers is {\it Sidon} if all its pairwise sums are different. In this entry point into the subject, combining two elementary proofs, we decrease the gap between the upper and lower bounds by \(0.2\%\) for infinitely many values of \(n\). We show that the maximum size of a Sidon set of \(\{ 1, 2, \ldots, n\}\) is at most \(\sqrt{n}+ 0.998n^{1/4}\) for \(n\) sufficiently large. Joint work with Zoltán Füredi and Souktik Roy.
Ryan Martin, Iowa State University
- February 25
- 2:30pm
Abstract: For a planar graph \(H\), let \({\bf N}_{\mathcal P}(n,H)\) denote the maximum number of copies of \(H\) in an \(n\)-vertex planar graph. The case where \(H\) is the path on 3 vertices, \(H=P_3\), was established by Alon and Caro. The case of \(H=P_4\) was determined, also exactly, by Győri, Paulos, Salia, Tompkins, and Zamora. In this talk, we will give the asymptotic values for \(H\) equal to \(P_5\) and \(P_7\) as well as the cycles \(C_6\), \(C_8\), \(C_{10}\) and \(C_{12}\) and discuss the general approach which can be used to compute the asymptotic value for many other graphs \(H\).
This is joint work with Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia, Chuanqi Xiao, and Oscar Zamora and also joint work with Chris Cox.
Hua Wang, Georgia Southern University
- February 18
- 2:30pm
Abstract: A composition of a given positive integer n is an ordered sequence of positive integers with sum n. In n-color compositions a part k has one of k possible colors. Using spotted tiling to represent such colored compositions we consider those with restrictions on colors. With general results on the enumeration of color restricted n-color compositions in terms of allowed or prohibited colors, we introduce many particular combinatorial observations related to various integer sequences and identities. This is joint work with Brian Hopkins.
Michael Levet, University of Colorado Boulder
- February 11
- 2:30pm
Abstract:
The Weisfeiler–Leman (WL) algorithm is a key combinatorial subroutine in Graph Isomorphism, that (for fixed \(k \geq 2\)) computes an isomorphism invariant coloring of the k-tuples of vertices. Brachter & Schweitzer (LICS 2020) recently adapted WL to the setting of groups. Using a classical Ehrenfeucht–Fraïssé pebble game, we will show that Weisfeiler–Leman serves as a polynomial-time isomorphism test for several families of groups previously shown to be in \(\textsf{P}\) by multiple methods. These families of groups include:
- Coprime extensions \(H \ltimes N\), where \(H\) is \(O(1)\)-generated and the normal Hall subgroup \(N\) is Abelian (Qiao, Sarma, & Tang, STACS 2011).
- Groups without Abelian normal subgroups (Babai, Codenotti, & Qiao, ICALP 2012).
In both of these cases, the previous strategy involved identifying key group-theoretic structure that could then be leveraged algorithmically, resulting in different algorithms for each family. A common theme among these is that the group-theoretic structure is mostly about the action of one group on another. Our main contribution is to show that a single, combinatorial algorithm (Weisfeiler–Leman) can identify those same group-theoretic structures in polynomial time.
We also show that Weisfeiler–Leman requires only a constant number of rounds to identify groups from each of these families. Combining this result with the parallel WL implementation due to Grohe & Verbitsky (ICALP 2006), this improves the upper bound for isomorphism testing in each of these families from \(\textsf{P}\) to \(\textsf{TC}^0\).
This is joint work with Joshua A. Grochow.
Stephan Wagner, Uppsala University
- February 4
- 2:30pm
Abstract: A subtree of a graph is any (not necessarily induced) subgraph that is also a tree. In this talk, I will discuss different questions concerning the distribution of subtrees in deterministic and random graphs. For instance: what can we say about the distribution of the subtree sizes, or the average size? What is the probability that a random subtree is spanning (covers all vertices)?
Ervin Gyõri, Alfréd Rényi Institute of Mathematics
- January 28
- 2:30pm
Abstract: Let \(\text{ex}_P(n, H)\) denote the maximum number of edges in an \(n\)-vertex planar graph which does not contain \(H\) as a subgraph. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both \(\text{ex}_P(n, C_4)\) and \(\text{ex}_P(n, C_5)\). Later on, Y. Lan, et al. continued this topic and proved that \(\text{ex}_P(n, C_6) \le 18(n-2)/7\). In this talk, I will focus on a sharp upper bound \(\text{ex}_P(n, C_6) \le 5n/2 - 7\), for all \(n \ge 18\), which improves Lan’s result. Some related extremal planar graph problems will be discussed shortly too.
This is joint result with Debarun Ghosh, Ryan R. Martin, Addisu Paulos, and Chuanqi Xiao.
Youngho Yoo, Georgia Tech
- December 3
- 2:30pm
Abstract: We show that if \(G\) is a 2-connected simple subcubic graph on \(n\) vertices with \(n_2\) vertices of degree 2, then \(G\) has a TSP walk (spanning closed walk) of length at most \(\frac{5n+n_2}{4}-1\), confirming a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible; there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have lengths \(\frac{5n+n_2}{4}-1\) (respectively, \(\frac{5n}{4} - 2\)). Our proof implies a polynomial-time algorithm for finding such a TSP walk. In particular, we obtain a \(\frac{5}{4}\)-approximation algorithm for the graphic TSP on simple cubic graphs, improving on the previously best known approximation ratio of \(\frac{9}{7}\).
Joint work with Michael Wigal and Xingxing Yu.
He Guo, Technion - Israel Institute of Technology
- November 19
- 2:30pm
Abstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n).
Based on joint work with Kalen Patton and Lutz Warnke.
Xiaonan Liu, Georgia Tech
- November 12
- 2:30pm
Abstract: Hakimi, Schmeichel, and Thomassen conjectured that every \(4\)-connected planar triangulation \(G\) on \(n\) vertices has at least \(2(n-2)(n-4)\) Hamiltonian cycles, with equality if and only if \(G\) is a double wheel. In this paper, we show that every \(4\)-connected planar triangulation on \(n\) vertices has \(\Omega(n^2)\) Hamiltonian cycles. Moreover, we show that if \(G\) is a \(4\)-connected planar triangulation on \(n\) vertices and the distance between any two vertices of degree \(4\) in \(G\) is at least \(3\), then \(G\) has \(2^{\Omega(n^{1/4})}\) Hamiltonian cycles. Joint work with Zhiyu Wang and Xingxing Yu.
Grant Fickes, Department of Mathematics, University of South Carolina
- November 5
- 2:30pm
Abstract: Call a hypergraph \(k\)-uniform if every edge is a \(k\)-subset of the vertices. Moreover, a \(k\)-uniform linear hyperpath with \(n\) edges is a hypergraph \(G\) with edges \(e_1, ... , e_n\) so that \(e_i \cap e_j = \emptyset\) if \(|i-j| \neq 1\), and \(|e_i \cap e_{i+1}| = 1\) for all \(1 \leq i\leq n-1\). Since the adjacency matrix of a graph is real symmetric, sets of eigenvectors form vector spaces. The extension of adjacency matrices to adjacency tensors in the hypergraph setting implies eigenvectors are no longer closed under arbitrary linear combinations. Instead, eigenvectors form varieties, and there is interest in finding decompositions of eigenvarieties into irreducible components. In this talk we find such a decomposition of the nullvariety for 3-uniform hyperpaths of arbitrary length. Moreover, we explore the repercussions of this decomposition on a conjecture of Hu and Ye.
Clifford Smyth, Department of Mathematics and Statistics, University of North Carolina, Greensboro
- October 29
- 2:30pm
Abstract: A bond of a graph G is a spanning subgraph H such that each component of H is an induced subgraph of G. The bonds of a graph G, when ordered by inclusion, form the so-called bond lattice, L(G) of G, an interesting sub-lattice of the well-studied set partition lattice. Bond lattices enjoy many interesting algebraic properties and there are interesting combinatorial formulations of the Moebius function and characteristic polynomial of these lattices.
We order the vertices of G and say two components in a bond are crossing if there are edges ik in one and jl in the other such that i < j < k < l. We say a bond is non-crossing if no two of its components cross. We study the non-crossing bond poset, NC(G), the set of non-crossing bonds of G ordered by inclusion, an interesting sub-poset of the well-studied non-crossing set partition lattice. We study to what extent the combinatorial theorems on L(G) have analogues in NC(G). This is joint work with Matt Farmer and Joshua Hallam.
Anton Bernshteyn, Department of Mathematics, Georgia Institute of Technology
- October 22
- 2:30pm
Abstract: According to a celebrated theorem of Johansson, every triangle-free graph \(G\) of maximum degree \(\Delta\) has chromatic number \(O(\Delta/\log\Delta)\). Molloy recently improved this upper bound to \((1+o(1))\Delta/\log\Delta\). In this talk, we will strengthen Molloy’s result by establishing an optimal lower bound on the number of proper \(q\)-colorings of \(G\) when \(q\) is at least \((1+o(1))\Delta/\log\Delta\). One of the main ingredients in our argument is a novel proof technique introduced by Rosenfeld. This is joint work with Tyler Brazelton, Ruijia Cao, and Akum Kang.
Zhiyu Wang, Mathematics, Georgia Institute of Technology
- October 15
- 2:30pm
Abstract: A graph class is called polynomially \(\chi\)-bounded if there is a function \(f\) such that \(\chi(G) \leq f(\omega(G))\) for every graph \(G\) in this class, where \(\chi(G)\) and \(\omega(G)\) denote the chromatic number and clique number of \(G\) respectively. A t-broom is a graph obtained from \(K_{1,t+1}\) by subdividing an edge once. A fork is a graph obtained from \(K_{1,4}\) by subdividing two edges. We show two conjectures: (1) we show that for graphs \(G\) without induced \(t\)-brooms, \(\chi(G) = o(\omega(G)^{t+1})\), answering a question of Schiermeyer and Randerath. For \(t=2\), we strengthen the bound on \(\chi(G)\) to \(7.5\omega(G)^2\), confirming a conjecture of Sivaraman. (2) We show that any \{triangle, fork\}-free graph \(G\) satisfies \(\chi(G)\leq \omega(G)+1\), confirming a conjecture of Randerath.
Xiaofan Yuan, Mathematics, Georgia Tech
- October 1
- 2:30pm
Abstract: The well-known Four Color Theorem states that graphs containing no K5-subdivision or K3,3-subdivision are 4-colorable. It was conjectured by Hajós that graphs containing no K5-subdivision are also 4-colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture is 4-connected but not 5-connected. We show that any such counterexample does not admit a 4-cut with a nontrivial planar side. This is joint work with Qiqin Xie, Shijie Xie and Xingxing Yu.
Felix Lazebnik, Department of Mathematical Sciences, University of Delaware
- September 24
- 2:30pm
Abstract: In this talk I will survey some results and open questions related to graphs of high density and without cycles of length 4, or 6, or 8. Some of them are obtained in a uniform way by lifting large induced subgraphs of Levi graphs (point-incidence graphs) of projective planes.
Part of the talk will be based on recent joint work with Vladislav Taranchuk.
Justin Troyka, Mathematics, Davidson College
- September 17
- 2:30 pm
Abstract: A split graph is a graph whose vertices can be partitioned into a clique (complete graph) and a stable set (independent set). How many split graphs on n vertices are there? Approximately how many are there, as n goes to infinity? Collins and Trenk (2018) have worked on these questions; after briefly summarizing their results, I will show how I have generalized them in the setting of species theory, a powerful framework for counting combinatorial objects acted on by isomorphisms. This generalization leads to a result relating split graphs and bicolored graphs, allowing me to prove the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are "balanced".
Joshua Cooper, Department of Mathematics, University of South Carolina
- September 10
- 2:30pm
Abstract: Consider permutations \(\sigma : [n] \rightarrow [n]\) written in one-line notation as a vector \(\vec{\sigma} = (\sigma(1),\ldots,\sigma(n))\). The permutohedron \(\mathcal{P}_n\) (in one standard presentation) is the convex hull of all such \(\vec{\sigma}\), with center \(\vec{p} = ((n+1)/2,\ldots,(n+1)/2)\). Then \(\mathcal{P}_n\) has a geometric equator: permutations \(\tau\) so that \((\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}}_n-\vec{p}) = 0\), where \(\text{id}_n\) is the identity permutation. But \(\mathcal{P}_n\) also has a combinatorial equator: permutations \(\tau\) in the middle level of the weak Bruhat order, i.e., for which \(\text{inv}(\tau) = \frac{1}{2} \binom{n}{2}\). We ask: how close are these two equators to each other? This question arose in connection with a problem in machine learning concerned with estimating so-called Shapley values by sampling families of permutations efficiently.
The most interesting special case of our main result is that, for permutations \(\tau\) close to the geometric equator, i.e., for which \((\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}}_n-\vec{p}) = o(1)\), the number of inversions satisfies
$$
\left | \frac{\text{inv}(\tau)}{\binom{n}{2}} - \frac{1}{2} \right | \leq \frac{1}{4}
+ o(1)
$$
and, furthermore, the quantity \(1/4\) above cannot be improved beyond \(1/2 - 2^{-5/3} \approx 0.185\). The proof is not difficult but uses an amusing application of bubble sorting. We discuss this and a more general and precise version of the result for any ratio \(\text{inv}(\tau)/\binom{n}{2}\).
Joint work with: Rory Mitchell of Nvidia, and Eibe Frank and Geoffrey Holmes of University of Waikato, NZ
Andrew Meier, Department of Mathematics, University of South Carolina
- September 3
- 2:30pm
Abstract: An edge-colored graph \(H\) is called \textit{rainbow} if every edge of \(H\) receives a different color. Given any host multigraph \(G\), the anti-Ramsey number of \(t\) edge-disjoint rainbow spanning trees in \(G\), denoted by \(r(G,t)\), is defined as the maximum number of colors in an edge-coloring of \(G\) containing no \(t\) edge-disjoint rainbow spanning trees. For any vertex partition \(P\), let \(E(P,G)\) be the set of non-crossing edges in \(G\) with respect to \(P\). In this talk, we determine \(r(G,t)\) for all host multigraphs \(G\): \(r(G,t)=|E(G)|\) if there exists a partition \(P_0\) with \(|E(G)|-|E(P_0,G)|<t(|P_0|-1)\); and \(r(G,t)=\max_{P\colon |P|\geq 3} \{|E(P,G)|+t(|P|-2)\}\) otherwise. As a corollary, we determine \(r(K_{p,q},t)\) for all values of \(p,q, t\), improving a result of Jia, Lu and Zhang.