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 237Inequivalent 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.