LSU College of Science
LSU
Mathematics

Calendar


Time interval:   Events:

Thursday, October 16, 2003

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

Thursday, October 27, 2005

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

Thursday, November 3, 2005

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

Thursday, August 31, 2006

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

Wednesday, April 18, 2007

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

Friday, November 2, 2007

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

Friday, November 9, 2007

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

Friday, November 16, 2007

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

Friday, November 30, 2007

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.

Friday, August 29, 2008

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.

Friday, September 5, 2008

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.

Friday, September 19, 2008

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.

Friday, September 26, 2008

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

Friday, November 14, 2008

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

Friday, November 21, 2008

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

Friday, December 5, 2008

Combinatorics Seminar  Questions or comments?

Posted December 2, 2008
Last modified December 4, 2008

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.

Friday, May 1, 2009

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

Friday, October 16, 2009

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

Friday, November 13, 2009

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.

Friday, January 29, 2010

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.

Friday, February 19, 2010

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.

Friday, March 5, 2010

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.

Friday, March 19, 2010

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.

Thursday, January 27, 2011

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

Thursday, February 3, 2011

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

Friday, September 9, 2011

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.

Thursday, September 22, 2011

Combinatorics Seminar  Questions or comments?

Posted September 15, 2011
Last modified September 20, 2011

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.

Thursday, October 6, 2011

Combinatorics Seminar  Questions or comments?

Posted September 16, 2011
Last modified October 5, 2011

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.

Friday, October 28, 2011

Combinatorics Seminar  Questions or comments?

Posted September 16, 2011
Last modified September 20, 2011

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.

Friday, November 4, 2011

Combinatorics Seminar  Questions or comments?

Posted October 28, 2011
Last modified October 31, 2011

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.

Friday, November 18, 2011

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.

Friday, February 3, 2012

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.

Friday, February 17, 2012

Combinatorics Seminar  Questions or comments?

Posted February 13, 2012
Last modified February 15, 2012

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.

Friday, March 2, 2012

Combinatorics Seminar  Questions or comments?

Posted February 27, 2012
Last modified February 29, 2012

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

Friday, March 23, 2012

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.

Friday, October 5, 2012

Combinatorics Seminar  Questions or comments?

Posted October 1, 2012
Last modified October 3, 2012

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.

Monday, October 22, 2012

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 satisfi ed 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

Monday, February 18, 2013

Combinatorics Seminar  Questions or comments?

Posted February 13, 2013
Last modified February 18, 2013

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

Wednesday, February 27, 2013

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.

Wednesday, March 13, 2013

Combinatorics Seminar  Questions or comments?

Posted March 5, 2013
Last modified March 10, 2013

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

Wednesday, April 10, 2013

Combinatorics Seminar  Questions or comments?

Posted March 20, 2013
Last modified April 8, 2013

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.

Wednesday, April 24, 2013

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.

Wednesday, May 1, 2013

Combinatorics Seminar  Questions or comments?

Posted April 15, 2013
Last modified April 29, 2013

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.

Wednesday, September 25, 2013

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.

Wednesday, October 9, 2013

Combinatorics Seminar  Questions or comments?

Posted September 19, 2013
Last modified October 4, 2013

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.

Wednesday, September 10, 2014

Combinatorics Seminar  Questions or comments?

Posted September 6, 2014

4:30 pm - 5:30 pm Lockett 237

Inequivalent representations of matroids

Wednesday, October 22, 2014

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.


Wednesday, October 29, 2014

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.

Wednesday, November 5, 2014

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.

Wednesday, November 19, 2014

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.

Wednesday, February 11, 2015

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.

Wednesday, March 18, 2015

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

Monday, March 23, 2015

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.

Wednesday, October 21, 2015

Combinatorics Seminar  Questions or comments?

Posted October 10, 2015
Last modified October 11, 2015

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.

Wednesday, October 28, 2015

Combinatorics Seminar  Questions or comments?

Posted October 11, 2015
Last modified October 14, 2015

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.

Wednesday, November 18, 2015

Combinatorics Seminar  Questions or comments?

Posted November 16, 2015
Last modified November 17, 2015

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.

Wednesday, February 10, 2016

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.

Wednesday, March 30, 2016

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.

Wednesday, March 8, 2017

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.

Wednesday, March 29, 2017

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.

Wednesday, April 5, 2017

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.

Friday, October 6, 2017

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.

Wednesday, November 8, 2017

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.

Friday, November 17, 2017

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.

Wednesday, March 7, 2018

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.

Wednesday, March 14, 2018

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.

Wednesday, April 25, 2018

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.