# Department of Mathematics

## Discrete Math and Combinatorics Seminar

We invite speakers to present original research in combinatorics and graph theory as well as their applications.

Organized by: Stephen Smith ( sjs8@email.sc.edu )

Note: Due to the COVID-19 pandemic, we are currently leaving the format of the seminar up to each individual speaker. To make the seminar as accessible as possible, we will be attempting to simulcast each in-person presentation live so that anyone who can't or would prefer not to attend in person can still participate.

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 Stephen Smith.

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.