Calendar

Posted October 3, 2003

Combinatorics Seminar Questions or comments?

3:10 pm – 4:00 pm Lockett 381

Guoli Ding, Mathematics Department, LSU
Some new problems on graph embeddings

Posted October 21, 2005

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 381 Lockett Hall

Carolyn Chun, Victoria University in Wellington, New Zealand Former LSU graduate student
Unavoidable Parallel Minors of Large, 4-Connected Graphs

Posted October 28, 2005

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 381 Lockett Hall

Brian Beavers, Mathematics Department, LSU Graduate student
Finding Cycles of All Sizes in Large Graphs and Matroids

Posted August 31, 2006

Combinatorics Seminar Questions or comments?

1:40 pm – 2:30 pm Lockett 381

Dirk Llewellyn Vertigan, Mathematics Department, LSU
Integer Flows and Cycle Covers: Introductory Lecture

Posted April 15, 2007

Combinatorics Seminar Questions or comments?

1:40 pm – 2:30 pm 276 Lockett Hall

Chris Rodger, Auburn University
Hamilton decompositions in complete multipartite graphs

Posted October 26, 2007

Combinatorics Seminar Questions or comments?

11:40 am – 12:30 pm 113 Lockett Hall

Deborah Chun, LSU Graduate student
Deletion-contraction to form a polymatroid

All welcome

Posted November 7, 2007

Combinatorics Seminar Questions or comments?

11:40 am – 12:30 pm 113 Lockett Hall

Moshe Cohen, Department of Mathematics, Bar-Ilan University, Israel
Ribbon Graphs and Quasi-trees

Posted November 12, 2007

Combinatorics Seminar Questions or comments?

11:40 am – 12:30 pm 113 Lockett Hall

Stan Dziobiak, Department of Mathematics, LSU Graduate Student
Coloring Graphs within a Constant Error in Polynomial Time

Posted November 28, 2007

Combinatorics Seminar Questions or comments?

11:40 am – 12:30 pm 113 Lockett Hall

Evan Morgan, LSU Mathematics Department Graduate student
Tree-width and contraction

All welcome.

Posted August 27, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm 381 Lockett Hall

James Shook, University of Mississippi Graduate Student
Some properties of k-trees

James will introduce a new parameter, branch number, that is useful for studying Hamiltonian properties of k-trees. The main result in his talk generalizes a recent result of Broersma et al.

Posted September 5, 2008

Combinatorics Seminar Questions or comments?

3:00 pm – 4:00 pm 285 Lockett Hall

Mareike Massow, Technische Universitat Berlin
Diametral Pairs of Linear Extensions

Abstract: Let a finite partially ordered set (or poset) P be given. We are interested in the family of its linear extensions (LEs). The distance between two LEs L_1 and L_2 of P is the number of incomparable pairs appearing in different orders in L_1 and L_2. A pair of LEs maximizing this distance among all pairs of LEs of P is called a diametral pair. This talk will be about properties of diametral pairs. It is based on joint work with Graham Brightwell.

Posted September 19, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm 285 Lockett Hall

Evan Morgan, LSU Mathematics Department Graduate student
1-switching in cubic graphs

Abstract: Most of the time we want what we don\'t have. Fortunately in the case of cubic graphs our desire need not go unrequited. I will present a small local operation we can perform repeatedly on a connected cubic graph with n vertices which will transform it into any other connected cubic graph on $n$ vertices. And if we want to start 3-connected and end 3-connected, we can even keep it 3-connected the whole way through. Some extensions to embedded graphs may be discussed.

Posted November 25, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm 285 Lockett Hall

Mark Bilinski, LSU, Mathematics
Bounding the circumference of 3-connected claw-free graphs

Abstract: The circumference of a graph is the length of its longest cycle. A result of Jackson and Wormald implies that the circumference of a 3-connected claw-free graph is at least $\\frac 12 n^{\\log_{150}2}$. In this paper we improve this lower bound to $\\Omega(n^{\\log_3 2})$, and our proof implies a polynomial time algorithm for finding a cycle of such length. Bondy and Simonovits showed that the best lower bound one can hope for is $\\Omega(n^{\\log_98})$.

Posted November 25, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm Wednesday, November 12, 2008 285 Lockett Hall

Mark Bilinski, LSU, Mathematics
On the Reconstruction of Planar Graphs

Posted November 25, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm 285 Lockett Hall

Carolyn Chun, Victoria University in Wellington, New Zealand Former LSU graduate student
A chain theorem for internally 4-connected binary matroids

Posted December 2, 2008
Last modified December 4, 2008

Combinatorics Seminar Questions or comments?

5:10 pm – 6:00 pm Lockett 285

Xingxing Yu, Georgia Institute of Technology
Judicious partitions of hypergraphs

Abstract: Judicious partition problems on graphs and hyper graphs ask for partitions that optimize several quantities simultaneously. In this talk Professor Yu will discuss several judicious partition problems for hyper graphs, and present several results on hyper graphs whose edges have size at most 3. He will also outline the martingale approach for proving these results.

Posted April 30, 2009

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 285 Lockett Hall

Ken Shoda, George Washington University
Semi-Magic Square Matroids: A Super-exponential family of nonisomorphic matroids having the same Tutte polynomial

Posted October 13, 2009

Combinatorics Seminar Questions or comments?

4:40 pm – 5:30 pm Lockett Hall 285

Xiangqian Zhou
On minimally k-connected matroids

Posted November 13, 2009

Combinatorics Seminar Questions or comments?

4:40 pm – 5:30 pm 285 Lockett Hall

Natalie Hine, LSU Mathematics Graduate Student
Infinite Antichains of Matroids

Abstract: In this talk, I will assume no prior knowledge of matroid theory, so I will begin by defining a matroid and giving some basic examples. Then, I will explain the differences between graphs and matroids with respect to infinite antichains under the minor ordering. Lastly, I will discuss when a minor-closed class of matroids with a single excluded minor does not contain an infinite antichain.

Posted January 28, 2010

Combinatorics Seminar Questions or comments?

4:40 pm – 5:30 pm 235 Lockett Hall

Carolyn Chun, Victoria University in Wellington, New Zealand Former LSU graduate student
Matroid Fragility

Dinner will follow the talk, and will be held at Rama\'s Restaurant, commencing at 6pm.

Posted February 19, 2010

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 285 Lockett Hall

Stan Dziobiak, Department of Mathematics, LSU Graduate Student
An excluded-minor characterization of apex-outerplanar graphs

It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K_4 and K_{2,3}. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We will present the complete list of excluded minors for this class and outline the major steps of the proof.

Posted March 3, 2010

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 285 Lockett Hall

Lisa Warshauer, LSU Mathematics Graduate student
Graphs that are Almost Series-Parallel

Abstract: Consider the class of graphs G with the property that one can add an edge e and contract it out to obtain a series-parallel graph. This class of graphs is closed under taking minors. We give an excluded-minor characterization for the class.

Posted March 15, 2010

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm 285 Lockett Hall

Tanya Lueder, LSU Mathematics Graduate Student
A Characterization of Near Outer-Planar Graphs

A graph containing an edge whose removal results in an outer-planar graph is a near outer-planar graph. We present partial results towards the larger goal of describing the class of all such graphs in terms of a finite list of excluded graphs. Specifically, we give a description of those members of this list that are not 2-connected and do not contain a subdivision of a three-spoke wheel.

Posted January 27, 2011

Combinatorics Seminar Questions or comments?

4:40 pm – 5:30 pm 285 Lockett Hall

Winfried Hochstättler, FernUniversität in Hagen
Flows in Matroids I

Posted January 31, 2011

Combinatorics Seminar Questions or comments?

4:40 pm – 5:30 pm 285 Lockett Hall

Winfried Hochstättler, FernUniversität in Hagen
Flows in Matroids II

Posted September 6, 2011

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett Hall 241

Perry Iverson, Mathematics Department, LSU
Internally 4-connected projective graphs

Abstract: Archdeacon showed that projective graphs are characterized by 35 excluded minors. We show that the class of internally 4-connected projective graphs can be characterized by 23 excluded minors. In doing so, we discuss general methods for improving connectivity.

Posted September 15, 2011
Last modified September 20, 2011

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 239

Tyler Moss, Department of Mathematics, LSU Graduate Student
A minor-based characterization of matroid 3-connectivity

There are several well-known characterizations of matroid 2-connectivity. In this talk, I give a characterization of 3-connectivity.

Posted September 16, 2011
Last modified October 5, 2011

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 239

Dan Cranston, Virginia Commonwealth University
The Game of Revolutionaries and Spies on a Graph

We study a pursuit game between two teams on a graph; it can be viewed as modeling a problem of network security. The first team consists of r revolutionaries; the second consists of s spies. The revolutionaries seek a one-time meeting of m revolutionaries free of oversight by spies. Initially, the revolutionaries take positions at vertices, and then the spies do the same. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. Everyone knows where everyone else is at all times.

The revolutionaries win if after a round there is an unguarded meeting, where a meeting consists of (at least) m revolutionaries on one vertex, and it is unguarded if no spy is there. The spies win if they can prevent this forever. Let RS(G,m, r, s) denote this game played on the graph G by s spies and r revolutionaries with meeting size m.

The revolutionaries can form \floor(r/m) disjoint meetings (if G has at least this many vertices), so the spies need s at least \floor(r/m) to avoid losing immediately. For fixed G, r, m, let sigma(G,m,r) be the least s such that RS(G,m, r, s) is won by the spies. Say that G is spy-good if sigma(G,m,r) = \floor(r/m) for all m and r such that (r/m) < |V(G)|. We obtain a large class of spy-good graphs. A webbed tree is a graph G having a rooted spanning tree T such that every edge of G not in T joins vertices having the same parent in T.

Theorem: Every webbed tree is spy-good. Furthermore, all interval graphs and all graphs having a dominating vertex are webbed trees.

We also consider the game on bipartite graphs, hypercubes, unicyclic graphs, large k-partite graphs, and graphs with small domination number. This is joint work with Jane V. Butterfield, Gregory J. Puleo, Clifford D. Smyth, Douglas B. West, and Reza Zamani.



Dan Cranston is an invited speaker of the Student Colloquium Committee, which is funded by the VIGRE grant.

Posted September 16, 2011
Last modified September 20, 2011

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Locket 243

John Rhodes, University of California at Berkeley
Representing Matroids and Hereditary Collections by Boolean Matrices

We give the definition of representing a hereditary collection of sets on a finite set by a Boolean matrix and then prove all matroids have Boolean representations. We then talk about what other hereditary collections have Boolean representations. Though this research is new, the methods are elementary and should be understood by all. Joint work with Zur Izhakian.

Posted October 28, 2011
Last modified October 31, 2011

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm Lockett 243

Karl Mahlburg, Department of Mathematics, LSU
Enumeration of Non-crossing pairings on bit strings

A non-crossing pairing on a bit string is a matching of 1s and 0s in the string with the property that the pairing diagram has no crossings. This enumeration problem arises when calculating moments in the theory of random matrices and free probability, and the goal is to obtain useful formulas and/or asymptotic estimates. The main results include explicit formulas in the "symmetric" case where each run of 1s and 0s has the same length, as well as upper and lower bounds that are uniform across all words of fixed length and fixed number of runs. The results are proved through bijective mappings that relate the set of non-crossing pairings into certain generalized "Catalan" structures that include labelled trees and lattice paths.

Posted November 11, 2011

Combinatorics Seminar Questions or comments?

3:40 pm – 4:30 pm Locket 243

Clifford Smyth, University of North Carolina at Greensboro
Correlation inequalities and the BKR inequality

Correlation inequalities are theorems giving conditions on when certain classes of events (or random variables) are positively (or negatively) correlated. Perhaps one of the most well-known is the FKG inequality which asserts the positive correlation of increasing random variables on finite distributive lattices as long as the probability measure obeys the positive lattice condition. The BKR inequality is another well-known correlation-type result with important applications in percolation. The BKR inequality is phrased on product spaces but recently we have found a generalization to finite distributive lattices.

Posted January 30, 2012

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett 239

Dennis Hall, Department of Mathematics, LSU Graduate Student
Unavoidable minors for connected 2-polymatroids.

Abstract: It is well known that, for any integer $n$ greater than one,
there is a number $r$ such that every $2$-connected simple graph with
at least $r$ edges has a minor isomorphic to an $n$-edge cycle or
$K_{2,n}$. This result was extended to matroids by Lov\\\'asz,
Schrijver, and Seymour who proved that every sufficiently large
connected matroid has an $n$-element circuit or an $n$-element
cocircuit as a minor. In this talk, we generalize these theorems by
providing an analogous result for connected $2$-polymatroids.

Posted February 13, 2012
Last modified February 15, 2012

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett 239

Daniel Guillot, Department of Mathematics, LSU Graduate Student
Coloring Graphs with Independent Crossings

There are many well known results regarding bounds for the chromatic number of a graph embedded in a particular surface. A related problem is considering graphs drawn on a surface with some crossings. Kral and Stacho showed that for planar graphs with independent crossings, the chromatic number is at most 5. We will consider graphs drawn on other surfaces and show that, with the possible exception of certain complete graphs, Heawood's number is the correct upper bound.

Posted February 27, 2012
Last modified February 29, 2012

Combinatorics Seminar Questions or comments?

2:40 pm – 3:30 pm Lockett 239

Jesse Taylor, Department of Mathematics, LSU Graduate Student
On a Class of Nearly Binary Matroids.

One of the most widely known excluded-minor characterizations of matroids is Tutte's characterization of the class of binary matroids. In this presentation, we look at a class of matroids which is nearly binary. Specifically, we give an excluded-minor characterization for the class of matroids M in which M\\e or M/e is binary for all e in E(M).

Posted March 13, 2012

Combinatorics Seminar Questions or comments?

2:40 pm – 3:30 pm Lockett 239

Charles Semple, University of Canterbury, New Zealand
Realizing phylogenies with local information

Results that say local information is enough to guarantee global information provide the theoretical underpinnings of many reconstruction algorithms in evolutionary biology. Such results include Buneman\'s Splits-Equivalence Theorem and the Tree-Metric Theorem. The first result says that, for a collection C of binary characters, pairwise compatibility is enough to guarantee compatibility for C, that is, there is a phylogenetic (evolutionary) tree that realizes C. The second result says that, for a distance matrix D, if every 4 by 4 distance submatrix of D is realizable by an edge-weighted phylogenetic tree, then D itself is realizable by such a tree. In this talk, we investigate these and other results of this type. Furthermore, we explore the closely related task of determining how much information is enough to reconstruct the correct phylogenetic tree.

Posted October 1, 2012
Last modified October 3, 2012

Combinatorics Seminar Questions or comments?

3:30 pm – 4:20 pm Lockett 237

Moshe Cohen, Department of Mathematics, Bar-Ilan University, Israel
The graph of perfect matchings coming from knots: a formula for its diameter

The graph of perfect matchings has as its vertices the perfect matchings of a specific bipartite graph and as edges a flip move taking alternating edges of a face to the missing edges. We realize Kauffman's obscure vocabulary in his book on Formal Knot Theory as a result about the graph of perfect matchings coming from knots. In this case, the plane embedding of the bipartite graph gives a direction to the flip move edges which helps to answer one of the first questions in this combinatorial theory: what is the diameter of this graph?

We prove recursive structural properties of the bipartite graph and mention applications to grid graphs and to discrete Morse functions.

This is joint work with Mina Teicher.

Posted October 19, 2012
Last modified March 3, 2021

Combinatorics Seminar Questions or comments?

3:30 pm – 4:20 pm Lockett 235

Clifford Smyth, University of North Carolina at Greensboro
Means and Row-Column Correlation

We prove generalized arithmetic-geometric mean inequalities for quasi-means arising from symmetric polynomials. The inequalities are satisfied by all positive, homogeneous symmetric polynomials, as well as a certain family of nonhomogeneous polynomials; this family allows us to prove the following combinatorial result. Suppose that a random subgraph is chosen from a complete bipartite graph G with an equal number of vertices in each part of the bipartition (A;B), where each edge is independently chosen with a probability that depends only on its intersection with A. Then for any m, the probability that the degree of each vertex in A is bounded by m is less than the probability that this is true of each vertex in B.

This talk is based on joint work with Karl Mahlburg

Posted February 13, 2013
Last modified March 11, 2021

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 237

Bruce Richter, University of Waterloo
On Zarankiewicz' conjecture: the crossing number of $K_{m,n}$

The problem of determining the crossing number of $K_{m,n}$ dates back at least to the Second World War. The conjectured value of $$\left\lfloor \mathstrut\frac{\mathstrut m}{\mathstrut 2}\right\rfloor \left\lfloor \frac{m-1}2\right\rfloor \left\lfloor \frac{\mathstrut n}{\mathstrut 2}\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor$$ is achievable by a drawing. Two proofs that the conjecture is right were published in the early 1950's, but recognized in the 1960's to have fatal gaps. Kleitman showed in 1970 that the conjecture holds when $\min(m,n)\le 6$. More recent computer work with a related convex program has verified the conjecture for the pairs $(m,n)$ with $m=7,8$ and $n=7,8,9,10$ and provided improved lower bounds for the crossing number of $K_{m,n}$.

This talk takes the convex program approach one step further and shows that, for each $m$, either the conjecture is correct for $m$ or there is an explicit function $f(m)$ so that a counterexample exists with $n \le f(m)$.

Posted February 26, 2013

Combinatorics Seminar Questions or comments?

2:30 pm – 3:20 pm Lockett 285

Simon Pfeil, Louisiana State University
Unbreakable Matroids

A matroid M is unbreakable if M/F is connected for all flats F of M. It is not difficult to show that M is unbreakable if and only if M* has no two skew circuits. This talk will discuss some properties of unbreakable matroids and, in particular, will describe all regular unbreakable matroids.

Posted March 5, 2013
Last modified March 3, 2021

Combinatorics Seminar Questions or comments?

2:30 pm – 3:20 pm Lockett 235

Luke Postle, Emory University
Linear Isoperimetric Bounds for Graph Coloring

We will discuss how linear bounds in graph coloring lead to new and interesting results. To that end, we say a family F of graphs embedded in surfaces is hyperbolic if for every G in F and for every closed curve Y that intersects G only in vertices and bounds an open disk D, we have that |V(G) (intersect) D| <= O(|V(G) (intersect) Y|). This says that the number of vertices inside such an open disk is linear in the number of vertices on the boundary of that disk (counted with multiplicities). Similarly we say that a family F is strongly hyperbolic if the same holds for every annulus D. Being strongly hyperbolic has a number of interesting consequences. Foremost is the fact that the number of vertices of a graph in a strongly hyperbolic family is linear in the Euler genus of the surface. This gives rise to a linear-time algorithm for testing whether a graph on a fixed surface contains a member of F.

The concept of hyperbolicity unifies and simplifies a number of known results about coloring graphs on surfaces while resolving some open conjectures. Robin Thomas and I recently proved that the family of 6-list-critical graphs is strongly hyperbolic. In particular, the theory of strongly hyperbolic families then implies that the number of 6-list-critical graphs on a fixed surface is finite, resolving a conjecture of Thomassen from 1997. It also follows that locally planar graphs with distant precolored vertices are 5-choosable. For the plane, this was conjectured by Albertson in 1999 and recently resolved by Dvorak, Lidicky, Mohar and Postle. Furthermore, we can prove that locally planar graphs drawn in a surface with crossings far apart are 5-choosable which generalizes a result of Dvorak, Lidicky and Mohar for the plane. We also resolve a conjecture of Thomassen that a 5-list-colorable graph has exponentially many 5-list-colorings which he proved for planar graphs.

I have also recently proved that the family of 4-list-critical graphs of girth at least five is strongly hyperbolic. This implies a few interesting results, and provides a simplified proof of Havel's conjecture that a planar graph with triangles far enough apart is 3-colorable.

Based on joint work with Robin Thomas.

Posted March 20, 2013
Last modified April 8, 2013

Combinatorics Seminar Questions or comments?

2:30 pm – 3:20 pm Lockett 235

Kimberly D'souza, Louisiana State University
Excluding the Pyramid

A very important problem in graph minors research is to characterize Petersen-free and $K_6$-free graphs, both of which are graphs on 15 edges. These two problems have remained unsolved using current methods. Study of smaller graphs produces new methods for approaching this type of problem. This talk looks at the Pyramid graph, a graph on 12 edges. This graph has a special connectivity, namely the graph is (4,4)-connected. We exploit this property of the graph to develop a means of characterizing all Pyramid-free graphs.

Posted March 21, 2013

Combinatorics Seminar Questions or comments?

2:30 pm – 3:20 pm Lockett 235

Trevor McGuire, Louisiana State University
The Combinatorics of Ideals with Binomial and Monomial Generators

For nearly 200 years, invariant theory has had some place in mathematics; sometimes it has been at the forefront, and other times it was nearly forgotten. Since Kung and Rota said, "Like the Arabian phoenix rising out of its ashes, the theory of invariants, pronounced dead at the turn of the century, is once again at the forefront of mathematics" in 1984, new tools have been applied to the field and it is strong once again. In particular, much research has been done in applying tools from commutative algebra and combinatorics to the theory of monomial and binomial ideals. In fact, in their 2005 book, Combinatorial Commutative Algebra, Miller and Sturmfels put the new branch of math on firm footing, and extensively outlined the combinatorial theory behind free resolutions of monomial ideals and binomial ideals.

When one reads the separate theories, though, it is clear that they are distantly related, but the current literature does not outline the connection between the two. In this talk, we will give exactly the relation between the two, and in particular, we will discuss free resolutions of ideals that have monomial and binomial generators, and show that the new theory reduces to the two known theories. We will begin with an overview of resolutions and primarily discuss concrete examples on our way to the statement of the overarching theorem.

Posted April 15, 2013
Last modified April 29, 2013

Combinatorics Seminar Questions or comments?

2:30 pm – 3:20 pm Lockett 235

Kwang Ju Choi, LSU
A characterization of almost all minimal not nearly planar graphs

In this work, we define nearly planar graphs G to be planar graphs or have an edge e such that G\\e is planar. The class of nearly planar graphs is not minor-closed, but is closed under topological minors. Since we can make a trivial infinite series of planar graphs using parallel subdivision, we define a relation between two graphs which is an extension of the topological minor relation. We define M to be the minimal excluded class of nearly planar graphs under our relation. We prove that all members of M, except finitely many, contain a Mobius ladder and are made by three blocks.

Posted September 19, 2013

Combinatorics Seminar Questions or comments?

4:30 pm – 5:20 pm Lockett 235

Dillon Mayhew, Victoria University of Wellington, NZ
Characterizing representable matroids

Matroids abstract the notions of linear/geometric/algebraic dependence. More specifically, a matroid consists of a finite collection of points, and a distinguished family of dependent subsets. If we take a finite collection of vectors from a vector space, and distinguish the linearly dependent subsets, then the result is a matroid, and we say that such a matroid is representable. The original motivating problem in matroid theory involves deciding which matroids are representable and which are not. A large fraction of the research in the area has been driven by this problem.

This talk will be an introduction to matroid theory, and a survey of recent developments in the characterization of representable matroids. The focus will be on excluded-minor characterizations and formal languages. No knowledge of matroids will be assumed.

Posted September 19, 2013
Last modified October 4, 2013

Combinatorics Seminar Questions or comments?

4:30 pm – 5:20 pm Lockett 243

Carolyn Chun, Brunel University, London Former LSU graduate student
Delta-matroids, partial duality, and ribbon graphs

In this talk, I define delta-matroids and discuss their relationship with partial duality and ribbon graphs.

Posted September 6, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Dillon Mayhew, Victoria University of Wellington, NZ
Inequivalent representations of matroids

A representation of a matroid can be thought of as a one-to-one independence-preserving function from the groundset of the matroid into the points of a projective geometry. Naturally enough, there may be many such functions. Sometimes these functions are equivalent, in the sense that we can apply an automorphism of the projective geometry in such a way that they become identical, but it is also possible for the representations to be genuinely different. The existence of inequivalent representations makes matroid theory significantly more complicated, and quite a lot of effort has been dedicated to understanding, and gaining control over inequivalent representations. This talk will be a survey of some of those efforts.

Posted September 6, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Inequivalent representations of matroids

Posted October 20, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Emily Marshall, LSU
Hamiltonicity and Structure of Classes of Minor-free Graphs

In this talk, we examine the structure of K_{2,5} and K_{2,4} minor-free graphs. Tutte proved that every 4-connected planar graph is Hamiltonian. Not all 3-connected planar graphs are Hamiltonian, however: the Herschel graph is one example. We show that restricting to 3-connected, planar, K_{2,5}-minor-free graphs is enough to ensure Hamiltonicity. We give examples to show that the K_{2,5}-minor-free condition cannot be weakened to K_{2,6}-minor-free. Next we provide a complete characterization of all K_{2,4}-minor-free graphs. To prove both of these results we first provide a characterization of rooted-K_{2,2}-minor-free graphs. We also prove several useful results concerning Hamilton paths in rooted K_{2,2}-minor-free graphs.

Posted October 24, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Elyse Yeager, University of Illinois
Disjoint Cycles and a Question of Dirac

In this talk, we explore a refinement of the Corr\\\'adi-Hajnal Theorem. The Corr\\\'adi-Hajnal Theorem states that any graph on at least $3k$ vertices with minimum degree at least $2k$ contains a set of $k$ vertex-disjoint cycles. Our refinement answers a 1963 question posed by G. Dirac about ($2k-1$)-connected graphs that do not possess $k$ disjoint cycles. For a portion of our result, we use techniques from equitable coloring.

Posted October 31, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Peter Nelson, University of Waterloo
Exponentially Dense Matroids

The growth rate function for a minor-closed class of matroids is the function $h(n)$ whose value at an integer n is the maximum number of elements in a simple matroid in the class of rank at most n; this can be seen as a measure of the density of the matroids in the class. A theorem of Geelen, Kabell, Kung and Whittle implies that $h(n)$, where finite, grows either linearly, quadratically, or exponentially with base equal to some prime power $q$, in $n$. I will discuss growth rate functions for classes of the exponential sort, determining the growth rate function almost exactly for various interesting classes and giving a theorem that essentially characterises all such functions.

Posted November 17, 2014

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 237

Stefan van Zwam, LSU
Connectivity in Graphs and Matroids

A recurring theme in graph theory and its generalizations is connectivity. Time and again it is found that the presence (or absence!) of connectivity reveals useful structural information about the problem at hand. In this talk I will touch on a variety of examples from graph theory and matroid theory.

Posted January 28, 2015

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 276

Jorn van der Pol, TUE
On the number of Matroids

In this talk I will discuss joint work with Nikhil Bansal and Rudi Pendavingh, in which we consider the number of matroids on a ground set of size n. The talk will roughly consist of two parts. In the first part, I will present a technique for bounding the number of stable sets in a graph. The technique uses the spectral properties op the graph to obtain a concise description of any stable set in the graph. This result does not use any matroid theory, and works in a broader setting than matroid enumeration. In the second part, we will see how this spectral technique can be combined with some elementary properties of matroids in order to obtain an upper bound on the number of matroids. This upper bound substantially improves previous upper bounds, and comes quite close to the best known lower bound.

Posted March 13, 2015

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Friday, March 18, 2016 Lockett 285

Carolyn Chun, Brunel University, London Former LSU graduate student
Delta-matroids and ribbon graphs

Tutte famously observed that, ``If a theorem about graphs can be expressed in terms of edges and circuits alone it probably exemplifies a more general theorem about matroids.\" It is well known that graphs and matroids have a mutually enriching relationship. In this talk, we discuss the mutually enriching relationship between ribbon graphs and delta-matroids and give some results based on this relationship, in order to support our claim that, ``If a theorem about embedded graphs can be expressed in terms of quasi trees alone it probably exemplifies a more general theorem about delta-matroids.\"

Posted March 20, 2015

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 284

Alexander Garver, University of Minnesota
Maximal Green Sequences and Type A Quivers

A quiver Q is simply a directed graph. Quiver mutation is a combinatorial operation one performs on a quiver Q by selecting one of its vertices k and changing some of the edges of Q that are close to k. Certain sequences of quiver mutations called maximal green sequences are currently the subject of intense study by combinatorialists, representation theorists, and string theorists. I will explain some of the connections between maximal green sequences and combinatorics and I will discuss how to explicitly construct maximal green sequences for a class of quivers called type A quivers. This is joint work with Gregg Musiker.

Posted October 10, 2015
Last modified October 11, 2015

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm 277 Lockett

Chanun Lewchalermvongs, Louisiana State University
Graphs Without W4 and K5-e as Induced Minors

We concern with graphs that contain neither W4 (a wheel graph with 5 vertices) nor K5-e (the complete graph K5 minus one edge) as an induced minor. This class of graphs will be denoted by $\mathscr{W}$. We show that a graph in $\mathscr{W}$ can be constructed by the 0-, 1-, 2-sums of cliques with the specific condition on 2-sum. We also prove that $\mathscr{W}$ is not well-quasi-ordered by the induced minor relation. To prove this statement, we construct an infinite antichain, $\mathscr{D}^{\Gamma}$, in $\mathscr{W}$. Moreover, we prove as the main result that for any closed subclass $\mathscr{Z}$ of $\mathscr{W}$, $\mathscr{Z}$ contains an infinite antichain if and only if $\mathscr{Z} \cap \mathscr{D}^{\Gamma}$ is infinite.

Posted October 11, 2015
Last modified October 14, 2015

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm 277 Lockett

Benjamin Clark, Louisiana State University
Towards an excluded-minor characterization of the Hydra-5 matroids

One of the longstanding goals of matroid theory is to find excluded-minor characterizations of classes of representable matroids. The immediate problem that looms large is that of finding the excluded minors for the class of GF(5)-representable matroids. While this problem is beyond the range of current techniques, there is a road map for an attack that reduces the problem to a finite sequence of excluded-minor problems. This talk will give an overview of excluded-minor characterizations of classes of representable matroids, and outline the progress made towards an excluded-minor characterization of the class of Hydra-5 matroids.

Posted November 16, 2015
Last modified November 17, 2015

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 277

Emily Marshall, LSU
Excluding theta graphs

A theta graph, denoted theta_{a,b,c}, consists of a pair of vertices together with three disjoint paths between the vertices of lengths a, b, and c. In this talk, we characterize graphs which exclude certain theta graphs as a minor. We begin with small theta graphs, in particular those with at most 7 edges. This work is part of a larger project which characterizes H-minor-free graphs for all 2-connected graphs H on at most 7 edges and is joint with Mark Ellingham, Tom McCourt, and Tony Nixon. Next we look at excluding large theta graphs. We allow at least one of the paths to be arbitrarily long. The most complicated case is excluding theta_{t,t,t} where t is any large integer. The work on large theta graphs is joint with Guoli Ding.

Posted January 26, 2016

Combinatorics Seminar Questions or comments?

4:30 pm Lockett 285

Noah Winslow, Louisiana State University
Forbidden Minors for d-Realizability

Abstract: Call a generic placement of the vertices of a graph in an N-dimensional Euclidean space an N-realization. We say G is d-realizable if for any N-realization of a graph G, d is the smallest value for which there exists a d-realization of G with the same edge lengths. Formally, Belk and Connelly determined the set of all forbidden minors for d-realizability for d at most 3. Expanding on this work, we determine a large family of forbidden minors for each dimension greater than 3. At the heart of this graph family is a new concept, spherical realizability, which generically places the vertices of a graph on a d-sphere rather than in Euclidean space.

Posted March 13, 2016

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 285

Kevin Grace, LSU
Templates for Minor-Closed Classes of Binary Matroids

The concept of a template was recently introduced by Jim Geelen, Bert Gerards, and Geoff Whittle as a tool to describe some of their results in matroid structure theory. Matroids that conform to a frame template are obtained by altering a graphic matroid in a certain way. We introduce a partial order on binary frame templates and a list of minimal templates in this partial order. An application of this result is that all sufficiently highly connected 1-flowing matroids are either graphic or cographic. Other applications can be made to growth rates of minor-closed classes of binary matroids.

Posted March 5, 2017

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 240

Richard Hammack, Virginia Commonwealth University in Richmond
Neighborhood reconstruction and cancellation of graphs

This talk connects two seemingly unrelated problems in graph theory. Any graph G has an associated neighborhood multiset N (G) = {N(x) | x in V (G)} whose elements are precisely the open vertex-neighborhoods of G. In general there exist non isomorphic graphs G and H for which N (G) = N (H). We say G is neighborhood reconstructible if it is uniquely determined by its neighborhood multiset, that is, if N (G) = N (H) implies G ~= H. The cancellation problem for the direct product of graphs seeks the conditions under which G x K ~= H x K implies G ~= H. Lovasz proved that this is indeed the case if K is not bipartite. A second instance of the cancellation problem asks for conditions on G that assure G x K ~= H x K implies G ~= H for any bipartite graph K. A graph G for which this is true is called a cancellation graph. We will see that the neighborhood-reconstructible graphs are precisely the cancellation graphs. Some new results on cancellation graphs are given, with corresponding implications for neighborhood reconstruction.

Posted March 27, 2017

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 240

Matt Barnes, Department of Mathematics, LSU Graduate Student
Unavoidable immersions of large 3- and 4-edge connected graphs

Oporowski, Oxley, and Thomas showed that there is a function f such that every 3-connected graph of sufficient order, f(n), contains a minor isomorphic to a wheel, W_n, or K_3,n. We prove an analogous result for immersion, giving the unavoidable immersions of 3-edge-connected graphs, and a conjecture for the unavoidable immersions of 4-edge-connected graphs.

Posted April 3, 2017

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 240

Kevin Grace, LSU
All That Glitters Is Not Golden-Mean

Three closely related classes of GF(4)-representable matroids are the golden-mean matroids, the matroids representable over all fields of size at least 4, and the matroids representable over GF(4) as well as fields of all characteristics. We characterize the highly connected matroids in each of these classes by using frame templates, which were recently introduced by Geelen, Gerards, and Whittle as tools for describing the the highly connected members of minor-closed classes of representable matroids. As a direct consequence of this characterization, we give the growth rates of these classes of matroids, including the golden-mean matroids. This proves that a conjecture made by Archer in 2005 holds for golden-mean matroids of sufficiently high rank.

Posted November 1, 2017

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 276

Zachary Gershkoff, Mathematics Department, LSU
Characterization and enumeration of 3-regular permutation graphs

By taking a permutation in line notation, drawing a vertex for every letter in the permutation, and adding edges between vertices if and only if the corresponding letters are inverted, we obtain a type of graph called a permutation graph. We give a construction to show that there are infinitely many k-regular permutation graphs for k greater than two. For 3-regular permutation graphs, we characterize their structure, and we give a formula for counting them.

Posted November 1, 2017

Combinatorics Seminar Questions or comments?

4:30 pm Lockett 114

Peter Nelson, University of Waterloo
Turan problems for matroids

Given a fixed simple binary matroid $N$, we study, for large $n$, the maximum size of a simple rank-$n$ binary matroid $M$ that does not contain $N$ has a restriction. We argue that such problems closely resemble analogous extremal problems for $H$-free graphs, using a matroidal analogue of chromatic number and deep tools from arithmetic combinatorics to give surprisingly exact answers to many such questions.

Posted November 15, 2017

Combinatorics Seminar Questions or comments?

4:30 pm – 5:30 pm Lockett 276

Josh Fallon, LSU
Criticality of Counterexamples to Edge-hamiltonicity on the Klein Bottle

Tutte and Thomas and Yu proved that 4-connected planar and projective-planar graphs, respectively, are hamiltonian. Grunbaum and Nash-Williams conjecture that 4-connected toroidal and Klein bottle graphs are hamiltonian. Thomassen constructed counterexamples to edge-hamiltonicity of four-connected toroidal and Klein bottle graphs. Ellingham and Marshall contribute to the characterization of four-connected toroidal graphs in which some edge is not on a hamilton cycle, showing a sort of criticality of Thomassen\'s counterexamples and their generalizations. In this talk, I will discuss the progress made toward determining hamiltonicity of 4-connected graphs on the torus and Klein bottle and show in Thomassen\'s Klein bottle counterexamples a criticality similar to that in toroidal graphs.

Posted March 5, 2018

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 277

Deborah Chun, West Virginia University Institute of Technology
Three Recent Results

The first result concerns matroid connectivity and basis exchange graphs for matroids. The second result gives the bicircular matroids representable over GF(4) and GF(5). The third result is the unavoidable minors for bicircular 4-connected matroids. Basis exchange graphs and bicircular matroids are introduced. Knowledge of matroids is assumed.

Posted March 7, 2018
Last modified March 3, 2021

Combinatorics Seminar Questions or comments?

3:30 pm Lockett 277

James Oxley, Mathematics Department, LSU
The mathematical contributions of W.T. Tutte

Bill Tutte was born in 1917 in Newmarket, England, a town famous for the breeding of thoroughbred racehorses. To mark the centenary of his birth, there were many mathematical celebrations around the world last year. This talk, versions of which were presented at some of those celebrations, will discuss some of Bill's many profound mathematical contributions.

Posted April 17, 2018

Combinatorics Seminar Questions or comments?

3:30 pm Lockett 277

James Madden, Mathematics Department, LSU
A Generating Function for the Distribution of Runs in Binary Words

Let N(n,r,k) denote the number of binary words of length n that begin with 0 and contain exactly k runs (i.e., maximal subwords of identical consecutive symbols) of length r. We show that the generating function for the sequence N(n,r,0), n=0,1,..., is (1−x)(1−2x+x^r−x^{r+1})−1 and that the generating function for {N(n,r,k)} is x^{kr} time the k+1 power of this. We extend to counts of words containing exactly k runs of 1s by using symmetries on the set of binary words.

Posted November 5, 2018
Last modified March 2, 2021

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 241

Joeseph E. Bonin, George Washington University
The 𝒢-Invariant of a Matroid

The 𝒢-invariant of a matroid was introduced by Derksen (2009), who showed that it properly generalizes the Tutte polynomial. Akin to the Recipe Theorem, which says that the Tutte polynomial is universal among invariants that satisfy deletion-contraction rules, Derksen and Fink (2010) showed that the 𝒢-invariant is universal among valuations, which are invariants that satisfy an inclusion/exclusion-like property on matroid base polytopes. We give a new view of 𝒢(M) as a generating function for the flags of flats of M. We use this perspective to explore the effect of some matroid constructions on the 𝒢-invariant. We identify some of the information that the 𝒢-invariant picks up that the Tutte polynomial does not, such as the number of circuits and cocircuits of a given size, and whether (apart from free extensions and free coextensions) the matroid is a free product of two other matroids. From 𝒢(M), we can deduce whether M is connected; however, we show that for each positive integer n, there are matroids M and N with 𝒢(M) = 𝒢(N) for which their connectivities satisfy λ(M) - λ(N) ≥ n. Much of this is joint work with Joseph Kung.

Posted November 26, 2018

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm TBA

Charles Semple, University of Canterbury, New Zealand
When is a phylogenetic network reconstructible from its path distances?

Phylogenetic networks are a type of leaf-labelled, acyclic, directed graph used by evolutionary biologists to represent the ancestral history of species whose past includes reticulate (non-treelike) events. To what extent is an edge-weighted phylogenetic network determined by the path-length distances between its leaves? It is well known that such distances are sufficient to (uniquely) reconstruct phylogenetic trees. This result dates back to Zaretskii (1965), and underlies many widely-used tree reconstruction methods including the popular method of Neighbor-Joining. Does this sufficiency extend to phylogenetic networks? In this talk, we explore this question and discuss some recent results for the prominent class of tree-child networks.

Posted September 17, 2019
Last modified May 1, 2021

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett Hall 237

Farid Bouya, Louisiana State University
Seymour's Second Neighborhood Conjecture from a Different Perspective

Seymour's Second Neighborhood Conjecture states that every orientation of every simple graph has at least one vertex $v$ such that the number of vertices of out-distance 2 from $v$ is at least as large as the number of vertices of out-distance 1 from it. We present an alternative statement of the conjecture in the language of linear algebra.

Posted October 4, 2019
Last modified March 3, 2021

Combinatorics Seminar Questions or comments?

3:30 pm Lockett Hall 237

Zachary Gershkoff, Mathematics Department, LSU
Connectivity in Matroids and Polymatroids

Another way of saying that a matroid is connected is to say that for every pair of elements, there is a U_{1,2}-minor that uses them. We investigate what kind of structure a matroid M has when every two elements of M are in an N-minor for certain N. For 2-polymatroids, we prove a result that's similar to Brylawski and Seymour's result that if M is a connected matroid with a connected minor N, and e is in E(M)−E(N), then M\e or M/e is connected having N as a minor.

Posted October 11, 2019
Last modified March 3, 2021

Combinatorics Seminar Questions or comments?

3:30 pm Lockett Hall 237

Tara Fife, Louisiana State University
Laminar Matroids and their Generalizations

I'll begin by introducing matroids, nested matroids, and laminar matroids. One characterization of laminar matroids is that for all circuits $C_1\cap C_2\not=\emptyset$, either $C_1$ is in the closure of $C_2$ or $C_2$ is in the closure of $C_1$. We use this characterization to define two infinite families of generalized laminar matroids and give structural results of these classes. This is joint work with James Oxley.

Posted February 24, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Sarah Allred, Louisiana State University
Unavoidable induced subgraphs of large 2-connected graphs

Posted February 24, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Rose McCarty, Princeton University
Coloring visibility graphs

Posted February 24, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Zach Walsh, Louisiana State University
An Application of Extremal Matroid Theory

Posted February 24, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Amin Bahmanian, Illinois State University
Laminar Families and Connected Fair Detachments

Posted February 24, 2021
Last modified February 25, 2021

Combinatorics Seminar Questions or comments?

4:00 pm https://lsu.zoom.us/j/98833974073?pwd=WnhDbDY5d0ljbjBldEVWT1JacE1zQT09

George Drummond, University of Canterbury
Circuit-difference matroids

One characterization of binary matroids is that the symmetric difference of every pair of intersecting circuits is a disjoint union of circuits. We will consider circuit-difference matroids, that is, those matroids in which the symmetric difference of every pair of intersecting circuits is a single circuit. Our main result shows that a connected regular matroid is circuit-difference if and only if it contains no pair of skew circuits. We also characterize the infinitely many excluded series minors for the class.

This was a joint work with Kevin Grace, Tara Fife and James Oxley.

Posted March 10, 2021

Combinatorics Seminar Questions or comments?

4:00 pm https://lsu.zoom.us/j/98833974073?pwd=WnhDbDY5d0ljbjBldEVWT1JacE1zQT09

Ben Moore, University of Waterloo
A density bound for triangle free 4-critical graphs

Carsten Thomassen showed that every girth 5 graph embeddable in the torus or projective plane is 3-colourable. A complementary result of Robin Thomas and Barrett Walls shows that every girth 5 graph embedded in the Klein bottle is 3-colourable. I'll show neither the embeddability condition nor the girth 5 condition is needed in the above theorems by showing that every triangle-free 4-critical graph has average degree slightly larger than 10/3. This is joint work with Evelyne Smith Roberge.

Posted April 21, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Zachary Gershkoff, Mathematics Department, LSU
Elastic elements in 3-connected matroids

Posted April 21, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Josephine Reynes, Texas State University
Applications of Hypergraphic Matrix-minors via Contributors

Posted April 21, 2021

Combinatorics Seminar Questions or comments?

4:00 pm https://lsu.zoom.us/j/98833974073?pwd=WnhDbDY5d0ljbjBldEVWT1JacE1zQT09

Charles Semple, University of Canterbury, New Zealand
Recovering non-treelike evolution from small trees

Phylogenetic (evolutionary) trees and, more generally, phylogenetic networks are used in computational biology to represent the ancestral history of a collection of present-day taxa. The latter allows for the representation of non-treelike (reticulate) evolution such as hybridisation and recombination. A well-known result in mathematical phylogenetics says that every phylogenetic tree is recoverable from (determined by) its set of induced subtrees on three leaves. This result typically underlies those algorithms for reconstructing and analysing phylogenetic trees that take, as input, a collection of smaller phylogenetic trees on overlapping leaf sets and output a parent tree that `best'' represents the input. These algorithms are collectively known as supertree methods. They are practical and widely used in tree reconstruction. As an initial step towards developing analogous algorithms for reconstructing phylogenetic networks, to what extent is a phylogenetic network recoverable from its set of induced subtrees? In this talk, we investigate this question, and discuss a surprising and unexpected result for the class of normal (phylogenetic) networks.

Posted May 26, 2021

Combinatorics Seminar Questions or comments?

4:00 pm

Cameron Crenshaw, Louisiana State University
On the Cogirth of Binary Matroids

Posted November 8, 2021

Combinatorics Seminar Questions or comments?

4:00 pm Zoom Link: https://lsu.zoom.us/j/98833974073?pwd=WnhDbDY5d0ljbjBldEVWT1JacE1zQT09

Kevin Grace, Vanderbilt University
Dyadic Matroids with Spanning Cliques

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable over a fixed finite field. To use these results to study specific classes, it turns out to be important to study the matroids in the class containing spanning cliques. A spanning clique of a matroid M is a complete-graphic restriction of M with the same rank as M. In this talk, we will describe the structure of dyadic matroids with spanning cliques. The dyadic matroids are those matroids that can be represented by a real matrix each of whose nonzero subdeterminants is a power of 2, up to a sign. A subclass of the dyadic matroids is the signed-graphic matroids. In the class of signed-graphic matroids, the entries of the matrix are determined by a signed graph. Our result is that dyadic matroids with spanning cliques are signed-graphic matroids and a few exceptional cases. The main results in this talk will come from joint work with Ben Clark, James Oxley, and Stefan van Zwam.

Posted October 16, 2022

Combinatorics Seminar Questions or comments?

3:30 pm 233 Lockett Hall

Rose McCarty, Princeton University
Local structure for vertex-minors

Roughly, the vertex-minors of a graph $G$ are the graphs that can be obtained from $G$ by deleting vertices and by performing certain local moves within the neighborhood of a vertex. We are interested in classes of graphs which are closed under vertex-minors and isomorphism and which do not contain all graphs. Geelen conjectures that the graphs in any such class have a simple structural description. We discuss progress towards proving this conjecture and its relationship with binary matroids. This is part of an ongoing project with Jim Geelen and Paul Wollan.

Posted September 12, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239

Zhiyu Wang, Louisiana State University
$\chi$-boundedness and $\chi$-binding functions of graph classes

Abstract: A graph class is called $\chi$-bounded if there is a fixed function $f$ (called the $\chi$-binding function) such that for every graph G in that graph class, $\chi(G)\leq f(\omega(G))$, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$ respectively. The well-known Gy\'arf\'as-Sumner Conjecture states that for every tree $T$, the class of $T$-free graphs is $\chi$-bounded. The existence of a polynomial $\chi$-binding function for a graph class also implies the Erd\H{o}s-Hajnal Conjecture for that graph class. In this talk, we survey some recent results on $\chi$-boundedness and $\chi$-binding functions of certain graph classes.

Posted September 18, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239

Brittian Qualls, Louisiana State University
Unavoidable Immersions in 4-edge-connected Graphs

A graph H is called an immersion of a graph G if H can be obtained from a subgraph of G by repeated liftings, which means replacing two adjacent edges xy, xz by one edge yz. In this talk, we discuss results on unavoidable topological minors and their analogous results for immersions. In particular, we discuss our main result: that every sufficiently large 4-edge-connected graph contains a doubled cycle of length k, $C_{2,k}$, as an immersion. We will also discuss other results on immersions and possible avenues of further research.

Posted September 25, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Xiaonan Liu, Vanderbilt University
Counting Hamiltonian cycles in planar triangulations

Whitney showed that every planar triangulation without separating triangles is Hamiltonian. This result was extended to all $4$-connected planar graphs by Tutte. Hakimi, Schmeichel, and Thomassen showed the first lower bound $\log _2 n$ for the number of Hamiltonian cycles in every $n$-vertex $4$-connected planar triangulation and, in the same paper, they conjectured that this number is at least $2(n-2)(n-4)$, with equality if and only if $G$ is a double wheel. 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.

Posted October 6, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239 (or email zhiyuw at lsu.edu for Zoom link)

Samuel Weiner, Louisiana State University
Unavoidable Uniform Hypergraphs

A classical extension of Ramsey's Theorem states that every infinite graph must contain either an infinite clique or infinite coclique as an induced subgraph. There are three similar results detailing the unavoidable induced subgraphs for 1) graphs with infinitely many edges, 2) graphs with a vertex of infinite degree, and 3) locally finite, connected, infinite graphs. We now generalize all three of these results to hypergraphs for which every edge contains a uniform number of vertices. We also obtain the corresponding results for finite hypergraphs.

Posted October 16, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239 (or email zhiyuw at lsu.edu for Zoom link)

Linyuan Lu, University of South Carolina
Anti-Ramsey number of disjoint rainbow bases: from graphs to matroids

Motivated by our earlier work on the anti-Ramsey number of disjoint rainbow spanning trees on graphs, we generalize it to matroids. Consider a matroid $M=(E,\mathcal{I})$ with its elements of the ground set $E$ colored. A {\em rainbow basis} is a maximum independent set in which each element receives a different color. The {\em rank} of a subset $S$ of $E$, denoted by $r_M(S)$, is the maximum size of an independent set in $S$. A {\em flat} $F$ is a maximal set in $M$ with a fixed rank. The {\em anti-Ramsey} number of $t$ pairwise disjoint rainbow bases in $M$, denoted by $ar(M,t)$, is defined as the maximum number of colors $m$ such that there exists an $m$ coloring of the ground set $E$ of $M$ which contains no $t$ pairwise disjoint rainbow bases. We determine $ar(M,t)$ for all matroids.

Posted October 23, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239 (or email zhiyuw at lsu.edu for Zoom link)

James "Dylan" Douthitt, Louisiana State University
A matroid analogue of chordal graphs

A graph is chordal if every cycle of length four or more has a chord. In 1961, Dirac proved that a graph is chordal if and only if it can be built from complete graphs by repeated clique-unions. In this talk, I will describe a generalization of Dirac's result to binary matroids. This talk is based on joint work with James Oxley.

Posted October 31, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Emily Heath, Iowa State University
Conflict-free hypergraph matchings and generalized Ramsey numbers

Given graphs $G$ and $H$ and a positive integer $q$, an $(H,q)$-coloring of $G$ is an edge-coloring in which each copy of $H$ receives at least $q$ colors. Erdős and Shelah raised the question of determining the minimum number of colors, $f(G,H,q)$, which are required for an $(H,q)$-coloring of $G$. Determining $f(K_n,K_p,2)$ for all $n$ and $p$ is equivalent to determining the classical multicolor Ramsey numbers. Recently, Mubayi and Joos introduced the use of a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the values of $f(K_n,n,C_4,3)$ and $f(K_n,K_4,5)$. In this talk, we will show how to generalize their approach to give bounds on the generalized Ramsey numbers for several families of graphs. This is joint work with Deepak Bal, Patrick Bennett, and Shira Zerbib.

Posted November 7, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 239 (or email zhiyuw at lsu.edu for Zoom link)

James Anderson , Georgia Institute of Technology
Borel line graphs

We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\E_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers. (We will give an overview of the necessary descriptive set theory background so that the talk is accessible to a general combinatorics audience).

Posted November 13, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Jagdeep Singh, Binghamton University, State University of New York
Apex Graphs and Cographs

A class of graphs is called hereditary if it is closed under taking induced subgraphs. Its apex class is defined as the class of graphs G that contain a vertex v such that G-v is in the hereditary class. In recent work, Vaidy Sivaraman, Tom Zaslavsky, and I showed that if a hereditary class has finitely many forbidden induced subgraphs, then so does its apex class. I will talk about this result and its matroid analogue.

Posted November 28, 2023

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Ruth Luo, University of South Carolina
Long cycles in 2-connected hypergraphs

Dirac proved that every $n$-vertex, $2$-connected graph with minimum degree $\delta$ contains a cycle of length at least $\min\{n, 2\delta\}$. 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.

Posted January 19, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233

Chun-Hung Liu, Texas A&M University
Assouad-Nagata dimension of minor-closed metrics

Assouad-Nagata dimension addresses both large-scale and small-scale behaviors of metric spaces and is a refinement of Gromov’s asymptotic dimension. A metric space is a minor-closed metric if it is defined by the distance function on the vertices of an edge-weighted graph that satisfies a fixed graph property preserved under vertex-deletion, edge-deletion, and edge-contraction. In this talk, we determine the Assouad-Nagata dimension of every minor-closed metric. It is a common generalization of known results about the asymptotic dimension of H-minor free unweighted graphs, about the Assouad-Nagata dimension of complete Riemannian surfaces of finite Euler genus, and about their corollaries on weak diameter coloring of minor-closed families of graphs and asymptotic dimension of minor-excluded groups.

Posted January 28, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233

Yiwei Ge, Louisiana State University
Oriented diameter of near planar triangulations

The oriented diameter of an undirected graph $G$ is the smallest diameter over all the strongly connected orientations of $G$. A near planar triangulation is a planar graph such that every face except possibly the outer face is a triangle. In this talk, we will show that the oriented diameter of all $n$-vertex near planar triangulations(except seven small exceptions) is bounded by $\lceil \frac{n}{2}\rceil$, and the bound is tight. Joint work with Xiaonan Liu and Zhiyu Wang.

Posted January 28, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Sam Spiro, Rutgers University
The Random Tur\'an Problem

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)$ was determined in breakthrough work done independently by Conlon-Gowers and by Schacht. In this talk we discuss some recent results for bipartite $F$ (where much less is known), as well as for the analogous problem for $r$-partite $r$-graphs.

Posted February 11, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Youngho Yoo, Texas A&M University
Minimum degree conditions for apex-outerplanar minors

Motivated by Hadwiger's conjecture, we study graphs H for which every graph with minimum degree at least |V(H)|-1 contains H as a minor. We prove that a large class of apex-outerplanar graphs satisfies this property. Our result gives the first examples of such graphs whose vertex cover numbers are significantly larger than a half of its vertices, and recovers all known such graphs that have arbitrarily large maximum degree. If time permits, we discuss how our proof can be adapted to directed graphs to show that every directed graph with minimum out-degree at least t contains a certain orientation of the wheel and of every apex-tree on t+1 vertices as a subdivision and a butterfly minor respectively. Joint work with Chun-Hung Liu.

Posted February 17, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Yixuan Huang, Vanderbilt University
Even and odd cycles through specified vertices

Cycles through specified vertices generalize Hamilton cycles. Given a vertex subset of a graph , we define the local connectivity on $\kappa_G(X)$ by $\min_{x,y \in X} \kappa_G(x,y)$, where $\kappa_G(x,y)$ is the minimum number of vertices or edges separating $x$ and $y$, and by Menger’s theorem, equal to the maximum number of internally disjoint $xy$-paths. We prove that if a vertex subset $X$ satisfies $\kappa_G(X) \ge k \ge3$ and $|X| > k$, then there is an even cycle through any $k$ vertices of $X$. In addition, if the block containing $X$ is non-bipartite, there is an odd cycle through any $k$ vertices of $X$. Our results extend the results based on ordinary connectivity due to Bondy and Lovász. As a corollary, we prove the existence of cycles through a particular subset in the prism graph.

Posted February 25, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233

Scott Baldridge, Louisiana State University
Using quantum states to understand the four-color theorem

The four-color theorem states that a bridgeless plane graph is four-colorable, that is, its faces can be colored with four colors so that no two adjacent faces share the same color. This was a notoriously difficult theorem that took over a century to prove. In this talk, we generate vector spaces from certain diagrams of a graph with a map between them and show that the dimension of the kernel of this map is equal to the number of ways to four-color the graph. We then generalize this calculation to a homology theory and in doing so make an interesting discovery: the four-color theorem is really about all of the smooth closed surfaces a graph embeds into and the relationships between those surfaces. The homology theory is based upon a topological quantum field theory. The diagrams generated from the graph represent the possible quantum states of the graph and the homology is, in some sense, the vacuum expectation value of this system. It gets wonderfully complicated from this point on, but we will suppress this aspect from the talk and instead show a fun application of how to link the Euler characteristic of the homology to the famous Penrose polynomial of a plane graph. This talk will be hands-on and the ideas will be explained through the calculation of easy examples! My goal is to attract students and mathematicians to this area by making the ideas as intuitive as possible. Topologists and representation theorists are encouraged to attend also—these homologies sit at the intersection of topology, representation theory, and graph theory. This is joint work with Ben McCarty.

Posted March 3, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233 (simulcasted via Zoom)

Hailun Zheng, University of Houston-Downtown
Polytope and spheres: the enumeration and reconstruction problems

Consider a simplicial d-polytope P or a simplicial (d-1)-sphere P with n vertices. What are the possible numbers of faces in each dimension? What partial information about P is enough to reconstruct P up to certain equivalences? In this talk, I will introduce the theory of stress spaces developed by Lee. I will report on recent progress on conjectures of Kalai asserting that under certain conditions one can reconstruct P from the space of affine stresses of P ---- a higher-dimensional analog of the set of affine dependencies of vertices of P. This in turn leads to new results in the face enumeration of polytopes and spheres; in particular, a strengthening of (the numerical part of) the g-theorem. Joint work with Satoshi Murai and Isabella Novik.

Posted March 20, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Enrique Gomez-Leos , Iowa State University
On a problem of Erdős and Gyárfás

Given positive integers n,p,q, where p≤n, 1≤q≤(p choose 2), a (p,q)-coloring of the complete graph Kn is an edge coloring of Kn in which every clique on p vertices has at least q colors appearing in its edges. Let f(n,p,q) be the minimum number of colors needed for a (p,q)-coloring on Kn. Erdős and Gyárfás originally posed the question in 1997 and determined a general upper bound. In addition to determining the linear and quadratic threshold, they also showed that 5/6(n-1) ≤ f(n,4,5) ≤ n. Recently, Mubayi and Joos introduced a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the value of f(n,4,5) to be 5/6n + o(n). In this talk, we will introduce recent improvements to f(n,5,8). Indeed, we show that f(n,5,8) ≥ 6/7(n-1) and discuss how to use the conflict-free hypergraph matching method to show that f(n,5,8) ≤ n + o(n). This is joint work with Emily Heath, Coy Schwieder, Alex Parker, and Shira Zerbib.

Posted March 28, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett 233 (Simulcasted via Zoom)

Laszlo Szekely, University of South Carolina
Tanglegrams with the largest crossing number

A tanglegram consists of two binary trees with the same number of leaves, a left binary tree and a right binary tree, and a perfect matching between the leaves of the two trees. The size of a tanglegram is the number of matching edges. Tanglegrams are drawn in a special way. Leaves of the left tree must be on the line $x=0$, leaves of the right tree must be on the line $x=1$, the left binary tree is a plane tree in the halfplane $x\leq 0$, the right binary tree is a plane tree in the halfplane $x\geq 1$, and the perfect matching must be drawn in straight line segments. Such a drawing is called a layout of the tanglegram. The crossing number of a layout is the number of unordered pairs of matching edges that cross, while The crossing number of a tanglegram is the least number of crossings in layouts of this tanglegram. It is easy to see that the crossing number of a size $n$ tanglegram is at most $\binom{n}{2}$. Anderson, Bai, Barrera-Cruz, Czabarka, Da Lozzo, Hobson, Lin, Mohr, Smith, Sz\'ekely, and Whitlatch [Electronic J. Comb. {25}(4) (2018) \#P4.24] observed that the crossing number of any tanglegram is strictly less than $\frac{1}{2}\binom{n}{2}$, but some $n$, some tanglegrams have crossing number at least $\frac{1}{2}\binom{n}{2}-\frac{n^{3/2}-n}{2}$. In the current work we show on the one hand that the crossing number of any tanglegram is at most $\frac{1}{2}\binom{n}{2} -\Omega(n)$, and on the other hand that for some $n$, some tanglegrams have crossing number at least $\frac{1}{2}\binom{n}{2}-O(n\log n)$.

Posted March 28, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233 (Simulcasted via Zoom)

Eva Czabarka, University of South Carolina
Maximum diameter of $k$-colorable graphs

Between 1965 and 1989 several people showed that the diameter of an $n$-vertex connected graph $G$ with minimum degree $\delta$ is at most $\frac{3n}{\delta+1}-1$. In 1989 Erd\H{o}s, Pach, Pollack and Tuza posed the following conjecture: For fixed integers $r,\delta\geq 2$, for any connected graph $G$ with minimum degree $\delta$ and order $n$ we have (1) If $G$ is $K_{2r}$-free and $\delta$ is a multiple of $(r-1)(3r+2)$ then, as $n\rightarrow \infty$, $$ \operatorname{diam}(G) \leq \frac{2(r-1)(3r+2)}{(2r^2-1)}\cdot \frac{n}{\delta} + O(1)=\left(3-\frac{2}{2r-1}-\frac{1}{(2r-1)(2r^2-1)}\right)\frac{n}{\delta}+O(1). $$ (2) If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n\rightarrow \infty$, $$\operatorname{diam}(G) \leq \frac{3r-1}{r}\cdot \frac{n}{\delta} + O(1)=\left(3-\frac{2}{2r}\right)\frac{n}{\delta}+O(1). $$ Erd\H{o}s, Pach, Pollack and Tuza also created examples that show that the above conjecture, if true, is tight. Not much progress was made till 2009, when Czabarka, Dankelman and Sz\'ekely showed that for $r=2$ a weaker version of (2) holds: For every connected $4$-colorable graph $G$ of order $n$ and minimum degree $\delta\ge 1$, $ \operatorname{diam}(G) \leq \frac{5n}{2\delta}-1.$ This suggests a weakening of the conjecture by replacing the condition $K_{k+1}$-free with $k$-colorability. With Inne Singgih and L\'aszl\'o A. Sz\'ekely we provided conterexamples of part (1) of the conjecture in both versions (forbidden clique size or colorability) for every $r\ge 2$ for large enough $\delta$. These examples give that, if we are to bound the diameter of a $K_{k+1}$-free $n$-vertex graph with minimum degree $\delta$ by $C_k\cdot\frac{n}{\delta}$, then $C\ge 3-\frac{2}{k}$ regardless of the parity of $k$. With Stephen Smith and L\'aszl\'o A. Sz\'ekely we showed that this modified conjecture holds for both $3$- and $4$-colorable graphs (the latter result is an alternative and shorter proof to the 2009 result).

Posted April 8, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Jonathan Tidor, Stanford University
Ramsey and Turán numbers of sparse hypergraphs

The degeneracy of a graph is a measure of sparseness that plays an important role in extremal graph theory. To give one example, a 1966 conjecture of Erdős states that $d$-degenerate bipartite graphs have Turán number $O(n^{2-1/d})$. Though this is still far from solved, the bound $O(n^{2-1/4d})$ was proved by Alon, Krivelevich, and Sudakov in 2003. As another example, the Burr--Erdős conjecture states that graphs of bounded degeneracy have Ramsey number linear in their number of vertices. (This is in contrast to general graphs whose Ramsey number can be as large as exponential in the number of vertices.) This conjecture was resolved by Lee in 2017. I will talk about the hypergraph analogues of these two questions. Though the typical notion of hypergraph degeneracy does not give any information about either the Ramsey or Turán numbers of hypergraphs, I will define a new notion called skeletal degeneracy that is better-suited for these problems. We prove the hypergraph analogue of the Burr--Erdős conjecture: hypergraphs of bounded skeletal degeneracy have Ramsey number linear in their number of vertices. Furthermore, we give good bounds on the Turán number of partite hypergraphs in terms of their skeletal degeneracy. Both of these results use the technique of dependent random choice. Joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou.

Posted April 14, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett Hall 233

Xingxing Yu, Georgia Institute of Technology
Planar Turan Number of Cycles

The planar Turan number of a graph $H$, $ex_P(n,H)$, is the maximum number of edges in an $n$-vertex planar graph without $H$ as a subgraph. We discuss recent work on $ex_P(n,H)$, in particular when $H=C_k$ (cycle of length $k$), including our work on $ex_P(n,C_7)$. We prove an upper bound on $ex_P(n, C_k)$ for $k, n\ge 4$, establishing a conjecture of Cranston, Lidicky, Liu, and Shantanam. The discharging method and previous work on circumference of planar graphs are used.

Posted April 19, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Lockett 233

Ryan Martin, Iowa State University
Counting cycles in planar graphs

Basic Tur\'an theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Tur\'an 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 discuss 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.

Posted April 19, 2024

Combinatorics Seminar Questions or comments?

2:00 pm – 3:00 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Peter Nelson, University of Waterloo
Infinite matroids on lattices

There are at least well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will discuss some nice ideas that arise when combining these two generalizations. This is joint work with Andrew Fulcher.

Posted August 28, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 233 (Simulcasted via Zoom)

Yiwei Ge, Louisiana State University
Reconstructing induced-$C_4$-free graphs from digitally convex sets

A set $S$ of vertices is {\it digitally convex} if for every vertex $v$, $N[v]\subseteq N[S]$ implies $v\in S$. In 2014, Lafrance, Oellermann, and Pressey showed that trees are reconstructable from their digitally convex sets. We improved upon that result by showing that all induced-$C_4$-free graphs are reconstructable from their digitally convex sets, and we provide an algorithm for the reconstruction. This is based on a project with a group from the Graduate Research Workshop in Combinatorics (GRWC).

Posted September 10, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom Link

Anton Dochtermann, Texas State University
Cycle systems, parking functions, and h-vectors of matroids

The h-vector of a matroid M is an important invariant related to the independence complex of M, which can also be covered as an evaluation of its Tutte polynomial. A well-known conjecture of Stanley posits that the h-vector of a matroid is a "pure O-sequence", meaning that it can be recovered by counting faces of a pure multicomplex. Merino has established Stanley's conjecture for the case of cographic matroids via a connection to chip-firing on graphs and the concept of a G-parking function. Inspired by these constructions, we introduce the notion of a cycle system for a matroid M . This leads to a collection of integer sequences that we call (co)parking functions for M, which we show are in bijection with the set of bases of M. We study maximal coparking functions, and also how cycle systems behave under deletion and contraction. This leads to a proof of Stanley’s conjecture for the case of matroids that admit cycle systems. This is joint work with Scott Cory, Solis McClain, and David Perkinson.

Posted September 13, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Friday, September 13, 2024 Zoom Link

Bryce Frederickson, Emory
Turán and Ramsey problems in vector spaces over finite fields

Abstract: Turán-type problems ask for the densest-possible structure which avoids a fixed substructure H. Ramsey-type problems ask for the largest possible "complete" structure which can be decomposed into a fixed number of H-free parts. We discuss some of these problems in the context of vector spaces over finite fields. In the Turán setting, Furstenberg and Katznelson showed that any constant-density subset of the affine space $AG(n,q)$ must contain a $k$-dimensional affine subspace if n is large enough. On the Ramsey side of things, a classical result of Graham, Leeb, and Rothschild implies that any red-blue coloring of the projective space $PG(n-1,q)$ must contain a monochromatic k-dimensional projective subspace, for n large. We highlight the connection between these results and show how to obtain new bounds in the latter (projective Ramsey) problem from bounds in the former (affine Turán) problem. This is joint work with Liana Yepremyan.

Posted September 17, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom Link

Matthew Kroeker, Waterloo
Unavoidable flats in matroids representable over a finite field

For a positive integer k and finite field F, we prove that every simple F-representable matroid with sufficiently high rank has a rank-k flat which either is independent, or is a projective or affine geometry over a subfield of F. As a corollary, we obtain the following Ramsey theorem: given an F-representable matroid of sufficiently high rank and any 2-colouring of its points, there is a monochromatic rank-k flat. This is joint work with Jim Geelen and Peter Nelson.

Posted August 28, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Ce Chen, University of Illinois Urbana-Champaign
On the maximum $F$-free induced subgraphs in $K_t$-free graphs

For graphs $F$ and $H$, let $f_{F,H}(n)$ be the minimum possible size of a maximum $F$-free induced subgraph in an $n$-vertex $H$-free graph, which is a generalization of both the Ramsey function and the Erd\H{o}s--Rogers function. Assuming the existence of certain locally dense $H$-free graphs, we give a general upper bound on $f_{F,H}(n)$ by establishing a container lemma for the $F$-free subgraphs. In particular, we improve the upper bounds on $f_{F,H}(n)$ when H is $K_3$ and $K_4$. This is joint work with J\'{o}zsef Balogh and Haoran Luo.

Posted October 4, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 233 (simulcasted via Zoom)

Zilin Jiang, Arizona State University
Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult

The classification of graphs with smallest eigenvalues at least −2 culminated in a beautiful theorem of Cameron, Goethals, Seidel and Shult, who related such graphs to root systems from the representation theory of semisimple Lie algebras. In this talk, I will explore graphs with smallest eigenvalues between −2 and −λ*, where λ* is about 2.0198, and I will explain why the mysterious number λ* is a barrier for classification. Joint work with Alexander Polyanskii and Hricha Acharya.

Posted October 1, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Friday, October 4, 2024 Zoom Link

Andrew Fulcher, University College Dublin
The cyclic flats of L-polymatroids

In recent years, $q$-polymatroids have drawn interest because of their connection with rank-metric codes. For a special class of $q$-polymatroids called $q$-matroids, the fundamental notion of a cyclic flat has been developed as a way to identify the key structural features of a $q$-matroid. In this talk, we will see a generalization of the definition of a cyclic flat that can apply to $q$-polymatroids, as well as a further generalization, $L$-polymatroids. The cyclic flats of an $L$-polymatroid is essentially a reduction of the data of an $L$-polymatroid such that the $L$-polymatroid can be retrieved from its cyclic flats. As such, in matroid theory, cyclic flats have been used to characterize numerous invariants.

Posted November 5, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Lockett Hall 233 (simulcasted via Zoom)

Matthew Mizell, LSU
Structures That Arise From Nested Sequences of Flats in Projective and Affine Geometries

In a vector space $V$, take a sequence of subspaces $V_1,V_2,\dots,V_n$ such that $V_1 \subseteq V_2 \subseteq \ldots \subseteq V_n = V$. Color the non-zero elements of $V_1$ green, the elements of $V_2 \backslash V_1$ red, the elements of $V_3 \backslash V_2$ green and so on. We call the resulting set of green elements a target. The study of targets was initiated by Nelson and Nomoto in 2018 for vector spaces over the $2$-element field. In this talk, we will discuss targets over arbitrary finite fields. We will also consider the graph analogue of targets as well as targets over affine geometries. Our main results will characterize each type of target in terms of its forbidden substructures. This is joint work with James Oxley.

Posted November 21, 2024

Combinatorics Seminar Questions or comments?

2:30 pm – 3:30 pm Zoom Link

Dillon Mayhew, University of Leeds
Excluded minors for Z3-gainable biased graphs

A biased graph is a graph along with a collection of distinguished cycles, which are said to be balanced. The only rule is that a theta subgraph cannot contain exactly two balanced cycles.Minors of biased graphs work more or less as one would expect: we can delete or contract edges (and delete isolated vertices), and the balanced cycles of the minor are inherited from the larger biased graph.Sometimes the balanced cycles are determined by a gaining function which applies elements of a group to (oriented) edges. We calculate the product of edge labels around a cycle (taking the inverse of a label if that edge is oriented against our direction of travel), and declare a cycle to be balanced if this product is the group identity. If the balanced cycles can be produced in this way via some labeling with elements from the group H, then the biased graph is said to be H-gainable.H-gainable biased graphs form a minor-closed class within the universe of biased graphs, so we naturally ask for a characterisation via excluded minors. This characterisation was completed for the group Z2 by Zaslavsky. We have now completed the characterisation when the group is Z3.More generally, we can postulate a version of Rota's conjecture: when H is a finite group, there are only finitely many excluded-minor biased graphs for the class of H-gainable biased graphs. One might think that this is exactly the same problem as Rota's conjecture for the class of frame matroids or lift matroids arising from H-gainable biased graphs. However, there is no reason to be believe that solving one of these problems will solve the other.This is joint work with Nick Brettell, Rutger Campbell, and Daryl Funk.

Posted January 21, 2025

Combinatorics Seminar Questions or comments?

1:30 pm – 2:30 pm Lockett Hall 233

Avin Sunuwar, LSU
Chain theorems on 3-connected graphs

Chain theorems provide a pathway in constructing and analyzing families of graphs. In this seminar, we explore improvements in chain theorems for 3-connected graphs and their subclasses. We discuss an improved version of Tutte’s Wheel Theorem, which enhances algorithmic efficiency by limiting the construction process to extensions of the wheel W4 with restricted operations. Then, we discuss a chain theorem for smoothly 3-connected graphs. Additionally, we present a chain theorem for rooted graphs. These results not only refine classical theorems but also pave the way for further advancements in graph theory and its applications.

Posted February 10, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett 233 (Simulcasted via Zoom)

Christine Cho, Louisiana State University
Weak maps and the Tutte polynomial

Let M and N be distinct matroids such that N is the image of M under a rank-preserving weak map. Generalizing results of Dean Lucas, we prove that, for x and y positive, T(M;x,y) \geq T(N;x,y) if and only if x+y \geq xy. We give several consequences of this result related to relative freedom of elements of a matroid.

Posted February 17, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Yixuan Huang, Vanderbilt University
Hierarchy of trees, walks, and Hamiltonicity of products

A spanning t-tree is a spanning tree of maximum degree at most t. A spanning t-walk is a spanning closed walk visiting every vertex at most t times. Spanning t-trees and spanning t-walks are generalizations of Hamiltonian paths and Hamiltonian cycles. Jackson and Wormald (1990) showed that the existence of spanning t-walks implies the existence of spanning t-trees, which again implies the existence of spanning (t+1)-walks. In this talk, we go through results on the existence of these two objects and introduce some results on Hamiltonicity of products of graphs that can be added to this hierarchy.

Posted February 24, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Zoom (email zhiyuw at lsu.edu for Zoom link)

Tung Nguyen, Princeton University
Induced subdivisions and polylogarithmic chromatic number

We discuss a proof that for every graph H, every n-vertex graph with no induced subdivision of H and with bounded clique number has chromatic number at most polylog(n). This extends a result of Fox and Pach that similar polylogarithmic bounds hold for all string graphs, and is close to optimal as there are triangle-free n-vertex string graphs with chromatic number at least loglog n. Joint work with Alex Scott and Paul Seymour.

Posted February 24, 2025

Combinatorics Seminar Questions or comments?

10:30 am Lockett Hall 233

James "Dylan" Douthitt, Louisiana State University
Induced-minor-closed classes of matroids (dissertation defense)

Abstract: A graph is chordal if every cycle of length at least four has a chord. In 1961, Dirac characterized chordal graphs as those graphs that can be built from complete graphs by repeated clique-sums. Generalizing this, we consider the class of simple $GF(q)$-representable matroids that can be built from projective geometries over $GF(q)$ by repeated generalized parallel connections across projective geometries. We show that this class of matroids is closed under induced minors and characterize the class by its forbidden induced minors, noting that the case when $q=2$ is distinctive. Additionally, we show that the class of $GF(2)$-chordal matroids coincides with the class of binary matroids that have none of $M(K_4)$, $M^*(K_{3,3})$, or $M(C_n)$ for $n\geq 4$ as a flat. We also show that $GF(q)$-chordal matroids can be characterized by an analogous result to Rose's 1970 characterization of chordal graphs as those that have a perfect elimination ordering of vertices. We then describe the classes of binary matroids with pairs from the set $\{M(C_4),M(K_4\backslash e),M(K_4),F_7\}$ as excluded induced minors. Additionally, we prove structural lemmas toward characterizing the class of binary matroids that do not contain $M(K_4)$ as an induced minor.

Posted March 10, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Lockett Hall 233 (Simulcast via Zoom)

Tan Nhat Tran, Binghamton University
Inductive and Divisional Posets: A Study of Poset Factorability

We introduce and study the notion of inductive posets and their superclass, divisionalposets, inspired by the concepts of inductive and divisional freeness for central hyperplane arrangements. A poset is called factorable if its characteristic polynomial has all positive integer roots. Motivated by this, we define inductive and divisional abelian (Lie group) arrangements, with their posets of layers serving as primary examples. Our first main result shows that every divisional poset is factorable. The second result establishes that the class of inductive posets includes strictly supersolvable posets, a class recently introduced by Bibby and Delucchi (2024), which extends the classical result by Jambu and Terao (1984) that every supersolvable hyperplane arrangement is inductively free. Finally, we present an application to toric arrangements, proving that the toric arrangement defined by any ideal of a root system of type A, B, or C, with respect to the root lattice, is inductive. This work is joint with R. Pagaria (Bologna), M. Pismataro (Bologna), and L. Vecchi (KTH).

Posted March 17, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Zoom (Please email zhiyuw at lsu.edu for Zoom link)

Zach Walsh, Auburn University
Delta-Wye exchange for matroids over pastures

Delta-Wye exchange is a fundamental graph operation that preserves many natural embeddability properties of graphs. This operation generalizes to matroids, and preserves many natural representability properties of matroids. We will present a result showing that Delta-Wye exchange preserves matroid representability over any pasture, which is an algebraic object that generalizes partial fields and hyperfields. This is joint work with Matt Baker, Oliver Lorscheid, and Tianyi Zhang.

Posted March 21, 2025

Combinatorics Seminar Questions or comments?

11:30 am – 12:30 pm Zoom Link

Jorn van der Pol, University of Twente
Turán densities for matroid basis hypergraph

What is the maximum number of bases of an n-element, rank-r matroid without a given uniform matroid U as a minor? This question arises in the problem of determining the Turán density of daisy-hypergraphs. Ellis, Ivan, and Leader recently showed that this density is positive, thus disproving a conjecture by Bollobás, Leader, and Malvenuto. Their construction is a matroid basis hypergraph, and we show that their construction is best-possible within the class of matroid basis hypergraphs. This is joint work with Zach Walsh and Michael C. Wigal.

Posted January 21, 2025

Combinatorics Seminar Questions or comments?

3:30 pm – 4:30 pm Zoom Link

Joseph Bonin, George Washington University
Results on positroids from the perspective of structural matroid theory

A matroid of rank $r$ on $n$ elements is a positroid if it has a representation by an $r$ by $n$ matrix over $\mathbb{R}$ with the property that the determinant of each $r$ by $r$ submatrix is nonnegative. Positroids are commonly studied through the lens of algebraic combinatorics, where a fixed linear order on the ground set is regarded as part of the positroid. We focus on the matroid structure per se, without a priori fixing a linear order on the ground set. A number of earlier characterizations of positroids involve connected flats and non-crossing partitions; we provide a new characterization of a similar flavor and discuss some of its applications. One application is finding conditions under which two positroids can be glued together along a common restriction, in the freest way possible, to yield another positroid: for instance, if $M$ and $N$ are positroids and the intersection of their ground sets is an independent set and a set of clones in both $M$ and $N$, then the free amalgam of $M$ and $N$ is a positroid (that encompasses parallel connections and much more). Also, the class of positroids is minor-closed, and we identify many multi-parameter infinite families of excluded minors for this class, while more excluded minors remain to be discovered.