When: April 19^th 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 12^th 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 5^th 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 29^th 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 22^nd 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 15^th 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 1^st 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 23^rd 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 16^th 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 9^th 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 2^nd 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 26^th 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 19^th 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 12^th 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 8^th 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 1^st 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 17^th 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 10^th 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 3^rd 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.

This work has been published on arXiv

When: October 27^th 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 6^th 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 29^th 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 v₁,e₂,v₂, ... , e_c, v₁ such that {v_i,v_i+1} ⊆ e_i 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 22^nd 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 15^th 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 8^th 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 1^st 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.