# Seminars

**$\chi$-binding functions for two graph classes--4/21/23--Dr. Zhiyu Wang, Hale Visiting
Assistant Professor, in the School of Mathematics, Georgia Institute of Technology**

**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 \emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once.
A \emph{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\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. This is joint work with Xiaonan
Liu, Joshua Schroeder, and Xingxing Yu.**

**Spanning Trees in Expanders--4/14/23--Jie Han, Beijing Institute of Technology**

**We consider the spanning tree embedding problem in dense graphs without bipartite
holes and sparse graphs. In 2005, Alon, Krivelevich and Sudakov asked for determining
the best possible spectral gap forcing an (n,d,\lambda)-graph to be T(n, \Delta)-universal.
In this talk, we introduce our recent work on this conjecture.**

**Cataloging Enumeration Formulae for Bouquet and Dipole Embeddings Under Symmetries--3/24/23--Mark
Ellingham, Vanderbuilt University**

**We give a general counting framework and enumeration formulae for cellular embeddings
of bouquets and dipoles under different symmetry groups. Embeddings of bouquets correspond
to chord diagrams, which have many applications, and embeddings of dipoles correspond
to permutations or permutation matrices, which are fundamental objects in mathematics.
Our results use Burnside's Lemma in a standard way, but by considering a number of
groups with a common subgroup we are able to solve a number of problems simultaneously
using `coset averages'. We also give a simple general framework for counting symmetric
objects and asymmetric pairs of objects under an involuntary symmetry; reflexible
objects and chiral pairs are a special case of this. We count bouquets with edge
colorings, which allows us to deal with nonorientable embeddings as well as orientable
ones. We also count directed embeddings of directed bouquets. Some of the results
we present are known, but of the 58 sequences (for uncolored objects) that we present,
43 have not, as far as we know, been described previously.**

### The Number of k-tons in the Coupon Collector Problem--3/4/23--J.C. Saunders, Middle Tennessee State University

**Consider the coupon collector problem where each box of a brand of cereal ****contains a coupon and there are n different types of coupons. Suppose that the ****probability of a box containing a coupon of a specific type is 1/n and that we ****keep buying boxes until we collect at least m coupons of each type. In 1960, ****Donald Newman and Lawrence Shepp determined the expected number of total ****coupons to be collected as n log n+(m−1)n log log n+nCm+o(1) as n → ∞ and ****m remains fixed, where Cm is a constant depending on m. Very soon afterwards, ****Paul Erd˝os and Alfr´ed R´enyi found the exact asymptotic distribution of the total
****number of coupons collected and since then many others have worked on other ****aspects of the coupon collector problem and its generalisations. In this talk, we
****give an overview of such results, as well as describe the speaker’s own work on ****this problem. More specifically, for k ≥ m, we call a certain coupon a k-ton if ****we see it k times by the time we have seen m copies of all of the coupons. We ****determine the asymptotic distribution of the number of k-tons after we have ****collected m copies of each coupon for any k in a restricted range, given any ****fixed m. We also determine the asymptotic joint probability distribution over ****such values of k and the total number of coupons collected.**

### Global dynamics of population network models--2/10/23--Yixiang Wu, Middle Tennessee State University

**It will discuss about some of our recent results on population network models. For
single species models, we consider the monotonicity of the spectral bound of a class
of matrices, which measure the growth rate of the population when the size is small;
we study the distribution of resources that maximize the total population in stream
environment. For two species competition models, I will present a result that classifies
the global dynamics of the model under some assumptions on the network structure.
**

### Recent problems in partitions and other combinatorial functions--12/2/22--Larry Rolen, Vanderbilt University

**This talk will discuss recent work, joint with a number of collaborators, on analytic
and combinatorial properties of the partition and related functions. This includes
work on recent conjectures of Stanton, which aim to give a deeper understanding into
the "rank" and "crank" functions which "explain" the famous partition congruences
of Ramanujan. It will describe progress in producing such functions for other combinatorial
functions using the theory of modular and Jacobi forms and recent connections with
Lie-theoretic objects due to Gritsenko-Skoruppa-Zagier. It will also discuss how analytic
questions about partitions can be used to study Stanton's conjectures, as well as
recent conjectures on partition inequalities due to Chern-Fu-Tang and Heim-Neuhauser,
which are related to the Nekrasov-Okounkov formula.**

**Approximating TSP walks in subcubic graphs--11/11/22--**Xingxing Yu, Georgia Tech

**There has been extensive research on approximating TSP walks in subcubic graphs.
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 of length at most 5n/4 + n_2/4 - 1, establishing
a conjecture of Dvorak, Kral' and Mohar. This upper bound is the best possible.
Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby
giving a (5/4)-approximation algorithm for the graphic TSP on simple cubic graphs
and improving on the previously best-known approximation ratio of 9/7. This is joint
work with Youngho Yoo and Michael Wigal.**

### Alternating Products of Binomial Coefficients --10/1/22--William Cox, MTSU

**In this talk we recall a few of the interesting properties apparent from looking at
binomial coefficients as entries in Pascal's Triangle. We consider the alternating
product of a row of entries of Pascal's Triangle and correlate the resulting value
to the alternating product of binomial coefficients. It will be shown that the alternating
product of a row of binomial coefficients corresponds to a ratio of double factorials.
From these investigations, a class of Pascal-type triangles dubbed arithmetic triangles
are defined. Last, we consider more general arithmetic triangles and see how the alternating
product formula extends naturally to a large class of arithmetic triangles.**

### Modulo 3-orientation and Sign-circuit covering-- 10/7/22--Dong Ye, MTSU

**A modulo 3-orientation of a graph is an orientation D such that, for every vertex
v, the number of edges oriented toward v is congruent to the number of edges oriented
away from v modulo 3. Tutte found that a graph G with a modulo 3-orientation has a
circuit cover which covers each edge at most twice, and hence a shortest circuit cover
at most 4|E(G)|/3. In this talk, we talk about connections between modulo 3-orientation
and circuit covers of signed graphs, extending Tuttes result from graph to signed
graphs. This is based on joint work with Jiaao Li and Yezhou Wu.**

#### Minimally Embedding Grid Graphs on Orientable Surfaces--9/30/22--Fabian Salinas, Vanderbilt University

**A K-dimensional grid graph is the graph cartesian product of K paths. When the product
of K paths includes 3 paths with an odd number of edges, the minimal orientable genus
of the corresponding grid graph has been known since 1970 by the work of White. In
the unsolved case, the problem becomes non-trivial, as the combinatorial lower bounds
provided by White no longer become fruitful. Expanding on Whites work, we classified
the minimum orientable genus of 2 infinite families of 3-dimensional grid graphs in
the unsolved case. Using visually intuitive methods for constructing orientable surfaces
and topological minors, we conjecture an orientable genus formula for any 3-dimensional
grid graph that is exact for the families we classified.**

### Sieve Methods in Random Graph Theory--9/23/22--J.C. Saunders, MTSU

**In this talk, we introduce the Turan sieve, which was first developed by Pal Turan
to give a simpler proof of the Hardy and Ramanujan result on the normal order of the
number of prime factors of a positive integer. The Turan sieve and its ****complement the simple sieve were developed further by Ram Murty and Yu-Ru Liu to problems
in combinatorics. We ****apply the Turan sieve and the simple sieve here to examine the diameter of a random
graph. In particular, we obtain ****upper and lower bounds on the probability of a random graph on n vertices having diameter
d for some d >= 2 with edge probability p, where the edges are chosen independently.
An interesting feature revealed in these results is that the Turan sieve and the simple
sieve "almost completely" complement each other. This result recovers an asymptotic
result on the diameter of a random graph by Bela Bollobas, as well provide concrete
upper and lower bounds for n and p (the number of vertices and the edge probability
in the random graph in question respectively) in certain ranges.**

#### Orientable Embeddings with Eulerian faces--9/16/22--Mark Ellingham, Vanderbilt University

###### **Embeddings with faces bounded by Euler circuits arise in several situations, such
as building DNA models of graphs that can be scanned easily, and finding maximum genus
orientable directed embeddings of digraphs. We discuss results on the existence of
such embeddings. First, graphs where all vertices have degree congruent to 2 mod
4 have an orientable embedding with two Euler circuit faces. Second, n-vertex eulerian
graphs where all vertices have at least (4n+2)/5 distinct neighbours also have such
an embedding. We discuss some of the ideas used in the proofs of these results and
some extensions and related results. ****This is joint work with Jo Ellis-Monaghan.**

###### MTSU **Department of Mathematical Sciences**

MTSU BOX 34

Murfreesboro, Tennessee 37132

Phone: (615) 898-2669

Fax: (615) 898-5422

**32**^{nd} Cumberland Conference on Combinatorics, Graph Theory & Computing

^{nd}Cumberland Conference on Combinatorics, Graph Theory & Computing

### May 13-14, 2023

Learn more about about the 32nd Cumberland Conference in the article written by Nance Degennaro from MTSU NEWS.