Recent Results on Hamilton-Connected Line Graphs--11/21/23--Dr. Xiaofeng Gu--West Georgia University

Thomassen conjectured that every 4-connected line graph is Hamiltonian.  The best result to date is due to Kaiser and Vrana, who proved that every 5-connected line graph of minimum degree at least 6 is Hamilton-connected. They also proved that every 3-connected essentially 9-connected line graph is Hamilton-connected, where a graph G is essentially k-connected if G has no vertex cut X of size less than k such that G-X has two nontrivial components. Some recent updates and related results will be presented in this talk.

Long Cycles in 2-Connected Hypergraphs--10/19/23--Dr. Ruth Luo--The University of South Carolina

Dirac proved that every n-vertex, 2-connected graph with minimum degree x contains a cycle of length at least min{n, 2x}. In this talk we present an analog for a long Berge cycles in uniform hypergraphs. In particular, the minimum degree condition required differs dramatically if the size of the edges is small or large. This is joint work with Alexandr Kostochka and Grace McCourt.

Divisibility Rules--9/22/23--Dr. Jan Zijlstra, Middle Tennessee State University

Division rules can significantly reduce computational efforts in coding theory and related fields.vvEstablishing a simple – if obscure –rule for division by 7, we generalize our proof to generate similar rules for primes up to 200 by (efficient) use of a pocket calculator.  This presentation is aimed at a general audience with an interest in Number Theory. In the process, we discuss proof techniques and extension of existing results.

$\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, Vanderbilt 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.