Combinatorics Seminar
Questions or comments?

Posted October 3, 2003

3:10 pm - 4:00 pm Lockett 381
Guoli Ding, Mathematics Department, LSU

Some new problems on graph embeddings

Combinatorics Seminar
Questions or comments?

Posted October 21, 2005

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

Combinatorics Seminar
Questions or comments?

Posted October 28, 2005

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

Combinatorics Seminar
Questions or comments?

Posted August 31, 2006

1:40 pm - 2:30 pm Lockett 381
Dirk Llewellyn Vertigan, Mathematics Department, LSU

Integer Flows and Cycle Covers: Introductory Lecture

Combinatorics Seminar
Questions or comments?

Posted April 15, 2007

1:40 pm - 2:30 pm 276 Lockett Hall
Chris Rodger, Auburn University

Hamilton decompositions in complete multipartite graphs

Combinatorics Seminar
Questions or comments?

Posted October 26, 2007

11:40 am - 12:30 pm 113 Lockett Hall
Deborah Chun, LSU
Graduate student

Deletion-contraction to form a polymatroid

All welcome

Combinatorics Seminar
Questions or comments?

Posted November 7, 2007

11:40 am - 12:30 pm 113 Lockett Hall
Moshe Cohen, Department of Mathematics, Bar-Ilan University, Israel

Ribbon Graphs and Quasi-trees

Combinatorics Seminar
Questions or comments?

Posted November 12, 2007

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

Combinatorics Seminar
Questions or comments?

Posted November 28, 2007

11:40 am - 12:30 pm 113 Lockett Hall
Evan Morgan, LSU Mathematics Department
Graduate student

Tree-width and contraction

All welcome.

Combinatorics Seminar
Questions or comments?

Posted August 27, 2008

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.

Combinatorics Seminar
Questions or comments?

Posted September 5, 2008

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.

Combinatorics Seminar
Questions or comments?

Posted September 19, 2008

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.

Combinatorics Seminar
Questions or comments?

Posted November 25, 2008

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})$.

Combinatorics Seminar
Questions or comments?

Posted November 25, 2008

5:10 pm - 6:00 pm Wednesday, November 12, 2008 285 Lockett Hall
Mark Bilinski, LSU, Mathematics

On the Reconstruction of Planar Graphs

Combinatorics Seminar
Questions or comments?

Posted November 25, 2008

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

Combinatorics Seminar
Questions or comments?

Posted December 2, 2008

Last modified December 4, 2008

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.

Combinatorics Seminar
Questions or comments?

Posted April 30, 2009

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

Combinatorics Seminar
Questions or comments?

Posted October 13, 2009

4:40 pm - 5:30 pm Lockett Hall 285
Xiangqian Zhou

On minimally k-connected matroids

Combinatorics Seminar
Questions or comments?

Posted November 13, 2009

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.

Combinatorics Seminar
Questions or comments?

Posted January 28, 2010

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.

Combinatorics Seminar
Questions or comments?

Posted February 19, 2010

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.

Combinatorics Seminar
Questions or comments?

Posted March 3, 2010

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.

Combinatorics Seminar
Questions or comments?

Posted March 15, 2010

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.

Combinatorics Seminar
Questions or comments?

Posted January 27, 2011

4:40 pm - 5:30 pm 285 Lockett Hall
Winfried Hochstaettler, Fern Universitat in Hagen

Flows in Matroids I

Combinatorics Seminar
Questions or comments?

Posted January 31, 2011

4:40 pm - 5:30 pm 285 Lockett Hall
Winfried Hochstaettler, Fern Universitat in Hagen

Flows in Matroids II

Combinatorics Seminar
Questions or comments?

Posted September 6, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted September 15, 2011

Last modified September 20, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted September 16, 2011

Last modified October 5, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted September 16, 2011

Last modified September 20, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted October 28, 2011

Last modified October 31, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted November 11, 2011

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.

Combinatorics Seminar
Questions or comments?

Posted January 30, 2012

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.

Combinatorics Seminar
Questions or comments?

Posted February 13, 2012

Last modified February 15, 2012

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.

Combinatorics Seminar
Questions or comments?

Posted February 27, 2012

Last modified February 29, 2012

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).

Combinatorics Seminar
Questions or comments?

Posted March 13, 2012

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.

Combinatorics Seminar
Questions or comments?

Posted October 1, 2012

Last modified October 3, 2012

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.

Combinatorics Seminar
Questions or comments?

Posted October 19, 2012

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

Combinatorics Seminar
Questions or comments?

Posted February 13, 2013

Last modified February 18, 2013

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).

Combinatorics Seminar
Questions or comments?

Posted February 26, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted March 5, 2013

Last modified March 10, 2013

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 inthe 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.

Combinatorics Seminar
Questions or comments?

Posted March 20, 2013

Last modified April 8, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted March 21, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted April 15, 2013

Last modified April 29, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted September 19, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted September 19, 2013

Last modified October 4, 2013

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.

Combinatorics Seminar
Questions or comments?

Posted September 6, 2014

4:30 pm - 5:30 pm Lockett 237Inequivalent representations of matroids

Combinatorics Seminar
Questions or comments?

Posted October 20, 2014

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.

Combinatorics Seminar
Questions or comments?

Posted October 24, 2014

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.

Combinatorics Seminar
Questions or comments?

Posted October 31, 2014

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.

Combinatorics Seminar
Questions or comments?

Posted November 17, 2014

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.

Combinatorics Seminar
Questions or comments?

Posted January 28, 2015

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.

Combinatorics Seminar
Questions or comments?

Posted March 13, 2015

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."

Combinatorics Seminar
Questions or comments?

Posted March 20, 2015

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.

Combinatorics Seminar
Questions or comments?

Posted October 10, 2015

Last modified October 11, 2015

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.

Combinatorics Seminar
Questions or comments?

Posted October 11, 2015

Last modified October 14, 2015

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.

Combinatorics Seminar
Questions or comments?

Posted November 16, 2015

Last modified November 17, 2015

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.

Combinatorics Seminar
Questions or comments?

Posted January 26, 2016

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.

Combinatorics Seminar
Questions or comments?

Posted March 13, 2016

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.

Combinatorics Seminar
Questions or comments?

Posted March 5, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted March 27, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted April 3, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted November 1, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted November 1, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted November 15, 2017

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.

Combinatorics Seminar
Questions or comments?

Posted March 5, 2018

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.

Combinatorics Seminar
Questions or comments?

Posted March 7, 2018

3:30 pm Lockett 277
James Oxley, Mathematics Department, LSU

The mathematical contributions of W.T. Tutte

Abstract: 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.

Combinatorics Seminar
Questions or comments?

Posted April 17, 2018

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.

Combinatorics Seminar
Questions or comments?

Posted November 5, 2018

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.

Combinatorics Seminar
Questions or comments?

Posted November 26, 2018

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.