Last updated Fri 11/21/08
The KU Combinatorics Seminar meets on Wednesdays, 3:00--4:00 PM in Snow 408. Please contact Jeremy Martin if you are interested in speaking.
Abstract: Let P be the poset of all posets on [n], ordered by inclusion of their sets of relations. Bjorner and Welker proved that P is a ranked poset whose order complex has the homotopy type of an (n-2)-sphere. We'll present their argument, and along the way will talk about useful tools in topological combinatorics such as supersolvability and the nerve theorem.
Abstract: Matroid base polytope decompositions arise in the work of certain algebraic geometers. In 2006, Billera, Jia, and Reiner invented a new invariant F(M) for matroids in the form of a quasisymmetric function. One motivating application of this invariant is to the study of matroid base polytope decompositions. The mapping of matroids to the algebra of quasisymmetric functions (QSym) behaves as a valuation on matroid base polytopes, and leads to a necessary algebraic condition on their decompositions. Billera, Jia, and Reiner pose a number of questions regarding this relationship. We address some of these questions, obtaining a full characterization for the rank two case.
Along the way, we obtain a novel Z-basis for QSym that has especially nice properties. For instance this basis has nonnegative integer structure constants and reflects, in addition to the usual grading of QSym by degree, a second grading of QSym that on (the images of) loopless matroids coincides with their matroidal rank.
No familiarity with quasisymmetric functions or matroids are assumed for this talk.
Abstract: The Tutte polynomial of a matroid is a bivariate polynomial that captures all of its invariants that behave nicely with respect to deletion and contraction. In this talk I will review algebraic interpretations of certain single-variable specializations of the Tutte polynomial. I will then show how to simultaneously generalize two of them to capture the whole two-variable beast. As simple corollaries, we'll see a few old results from the literature as well as one or two new ones.
Abstract: Given a set F of graphs, a graph G is F-free if G does not contain any member of F as an induced subgraph. We say that F is a degree-sequence-forcing set if, for each graph G in the class C of F-free graphs, every realization of the degree sequence of G is also in C. This definition is motivated by the well-studied class of split graphs. We prove that for any k there are finitely many minimal degree-sequence-forcing sets with cardinality k. We also give a complete characterization of the degree-sequence-forcing sets F when F has cardinality at most two, and partial results when F has cardinality three.
Abstract: One famous result in knot theory, the Kauffman-Murasugi Theorem, is that the span of the Jones polynomial of a prime knot is less than or equal to the crossing index of the knot, with equality if and only if the knot is alternating. In other words, nonalternating knots have a span less than or equal to the crossing index minus one. We strengthen that result here, utilizing the nonalternating skeleton of Bae and Morton. This combinatorial method computes the extreme coefficients of a version of the Jones polynomial through a constructed graph. Looking at properties of certain knots, we'll see that these extreme coefficients are zero, hence strengthening the Kauffman-Murasugi result.
No prior knowledge of knot theory is necessary; the essential definitions and examples will be provided.
Abstract: I will discuss recent works by Matt Baker and Serguei Norine. The classical Riemann-Roch theorem is a very powerful result involving the geometry and topology of a one-dimensional connected complex manifold. Baker and Norine proved an identical result for graphs. Applications include the existence of winning strategy for certain games.
Last updated Fri 11/21/08