Poster Session and Reception

Tuesday, November 11, 2014 - 4:05pm - 6:00pm
Lind 400
  • Combinatorics of Diagrams of Permutations
    Joel Lewis (University of Minnesota, Twin Cities)
    The combinatorics of the totally nonnegative part of the Grassmannian involves a variety of objects associated to a Grassmannian permutation. Many of these objects can be defined for permutations that are not necessarily Grassmannian by an appropriate choice of associated diagram. We study several such objects and their q-analogues, including acyclic orientations of inversion graphs, rook placements avoiding a diagram, various restricted fillings of diagrams, intervals in the strong Bruhat order, and invertible matrices over a finite field with restricted support.
  • The Fewest Edges in a Nearly Bipartite 4-Critical Graph
    Benjamin Reiniger (University of Illinois at Urbana-Champaign)
    With A.V. Kostochka, we answer a conjecture of Chen, Erdős, Gyárfás, and Schelp.
    Rödl and Tuza proved that a 4-critical graph requires the deletion of at least three edges to become bipartite;
    call such a graph a B+3 graph. Chen et al. asked how few edges such a graph may have.
    We prove that every such graph on n vertices has at least 2n-3 edges.
    Our proof uses a potential function and the connection between graph orientations and list coloring.
  • A Linear Diophantine System Solver
    Felix Breuer (Johannes Kepler Universität Linz)Zafeirakis Zafeirakopoulos (Johannes Kepler Universität Linz)
    Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce.
  • R-stable Hypersimplices
    Liam Solus (University of Kentucky)
    The hypersimplices are a well-studied collection of polytopes in combinatorics, optimization, and algebraic geometry. For each hypersimplex we define a new family of subpolytopes called the r-stable hypersimplices. These polytopes form a nested chain of subpolytopes within the hypersimplex, and a standard regular unimodular triangulation of the hypersimplex restricts to a triangulation of each r-stable hypersimplex in the nested chain. From the perspective of Ehrhart Theory, a number of the combinatorial properties of the h*-polynomial of the hypersimplex are shared with the r-stable hypersimplices within. For instance, the degree of the h*-polynomial of the hypersimplex, and its asymmetry, are shared by the r-stable hypersimplices with only a few exceptions. Also, in many instances, the h*-polynomials are unimodal. In the special case of the odd second hypersimplices, we can provide a shelling of the triangulation relating the r-stable hypersimplices that consecutively builds each polytope in the nested chain. Using this shelling we can compute the h*-polynomials of these polytopes, including the hypersimplex itself, via a sum of independence polynomials of graphs. For one such r-stable hypersimplex, this computation yields a connection to CR mappings of Lens spaces via Ehrhart-MacDonald reciprocity.
  • Several Divisibility Questions from Group Theory and Combinatorics
    Russ Woodroofe (Mississippi State University)
    This is joint work with John Shareshian.

    Certain questions on divisibility of binomial coefficients (and a slightly broader collection of numbers) naturally arose in our work on non-contractibility of the coset lattice of a finite group. This poster will put these questions in context with some other questions regarding generation of an alternating group, and will describe our recent progress on these problems.
  • Maximal Green Sequences for Type A Quivers
    Alexander Garver
    Maximal green sequences are certain mutation sequences of a framed quiver \widehat{Q}. Some applications of maximal green sequences include Reading's Cambrian lattices in combinatorics, computations of spectra of BPS states in physics, and quantum dilogarithm identities in representation theory. Maximal green sequences have been studied for many acyclic quivers by Br\{u}stle, Dupont, and Pérotin, by Keller, and by Qiu. We present a method for constructing an explicit maximal green sequence of any type A quiver (i.e. a quiver that is mutation equivalent to an orientation of a type A Dynkin diagram). This is joint work with Gregg Musiker.
  • The m-Cover Posets and the Strip-Decomposition of m-Dyck Paths
    Henri Muehle (Université de Paris VII (Denis Diderot))
    We present a realization of the m-Tamari lattice of parameter n in terms of m-tuples of Dyck paths of length 2n, equipped with componentwise rotation order. For that, we define the m-cover poset of an arbitrary bounded poset, and show that the smallest lattice completion of the m-cover poset of the Tamari lattice of parameter n is isomorphic to the m-Tamari lattice of parameter n. A crucial tool for the proof of this isomorphism is a decomposition of m-Dyck paths into m-tuples of classical Dyck paths, which we call the strip-decomposition. Finally, we show that the m-cover poset of the Cambrian lattice of the dihedral group is a trim lattice with cardinality equal to the generalized Fuss-Catalan number of the dihedral group.
  • Proof of Blum's Conjecture on Hexagonal Dungeons
    Tri Lai (University of Minnesota, Twin Cities)
    Matt Blum considered a special region called hexagonal dungeon and conjectured that the tilings of a hexagonal dungeon are always enumerated by powers of 13 and 14. We prove the conjecture by investigating two new regions whose numbers of tilings are also given by powers of 13 and 14.

    This work is joint with Mihai Ciucu.
  • Cellular Trees and Forests: An Overview
    Jeremy Martin (University of Kansas)
    This poster is an overview of the theory of spanning trees and forests in cell complexes, as developed by Art Duval, Caroline Klivans and myself over the last several years. The theory includes generalizations of the Matrix-Tree Theorem, the critical group of a graph, and cut and flow lattices from graph theory to general CW-complexes. I also summarize work on cellular colorings, tensions and flows (joint with Matthias Beck, Felix Breuer and Logan Godkin) and on tree enumeration in self-dual complexes (join with Molly Maxwell, Vic Reiner and Scott O. Wilson) and mention some open problems.
  • Disjoint Cycles and a Question of Dirac
    Elyse Yeager (University of Illinois at Urbana-Champaign)
    We discuss sufficient conditions for the existence of $k$ disjoint cycles in a graph. Corr\'adi and Hajnal proved that if a graph has at least $3k$ vertices and minimum degree at least $2k$, then it contains $k$ disjoint cycles. This has been refined in a number of ways, including by considering minimum degree sum instead of minimum degree. We show how a refinement of ours can be used to answer a 1963 question of G. Dirac. Namely, which $(2k-1)$-connected multigraphs do not contain $k$ disjoint cycles?

    Authors: Kenry Kierstead, Alexandr Kostochka, Theodore Molla, Elyse Yeager
  • Rainbow Colorings of some Geometrically Defined Uniform Hypergraphs in the Plane
    Brent Holmes (University of Kansas)
    Fix a subset F of the real plane. Define a uniform hypergraph whose vertices are the points of the plane, and whose hyperedges are F and all of its images under orientation-preserving isometries. The chromatic number is the smallest number of colors required to color the plane such that no two vertices that lie in a common hyperedge have the same color. I have classified families of these graphs and established upper bounds on the chromatic numbers of these families by using geometric tilings that extend the well-known Hadwiger tiling.
  • Rowmotion and Generalized Toggle Groups
    Jessica Striker (North Dakota State University)
    We extend the notion of the toggle group, as defined by P. Cameron and D. Fon-der-Flaass and further explored by the author with N. Williams, from the set of order ideals of a poset to any set L of subsets of a countable set E. We prove a general structure theorem for these toggle groups, similar to the theorem of Cameron and Fon-der-Flaass in the case of order ideals, and specialize it to several interesting settings, including chains, antichains, and interval closed sets of a poset, independent sets on a graph, matroids, and antimatroids (or convex geometries).

    If L contains the closed sets of some closure operation, we can define rowmotion on L as an action involving this closure operation. We prove that generalized rowmotion is only expressible as a product of toggles in the order ideal case.

  • Rademacher--Carlitz Polynomials
    Florian Kohl (University of Kentucky)
    We introduce and study the Rademacher--Carlitz polynomial. These polynomials generalize and unify various Dedekind-like sums and polynomials; most naturally, one may view the Rademacher--Carlitz polynomials as a polynomial analogue (in the sense of Carlitz) of the Dedekind--Rademacher sum which appears in various number-theoretic, combinatorial, geometric, and computational contexts.

    Our results come in three flavors: we prove a reciprocity theorem for Rademacher--Carlitz polynomials, we show how they are the only nontrivial
    ingredients of integer-point transforms of any rational polyhedron P, and we derive the reciprocity theorem for Dedekind--Rademacher sums as a
    corollary which follows naturally from our setup.
  • Random 312-Avoiding Permutations
    Lerna Pehlivan (Dalhousie University)
    Monte Carlo experiments, in a recent paper of Atapour and Madras, reveal some features of random 312-avoiding permutations when these random permutations are graphed as functions from 1,...,N to 1,...,N. In light of these experiments we determine some probabilities explicitly under the uniform distribution on the set of 312-avoiding
    permutations of 1,...,N. We derive exact formulas for the probability that the graph of a random 312-avoiding
    permutation has one specified point below the diagonal as well as two specified points below the diagonal considering
    both increasing and decreasing cases. In all of these cases we find the asymptotic approximations to these probabilities
    for large N and with the restriction that the determined points apart from each other and far from the boundaries. We
    also generalized the two specified decreasing points to k specified decreasing points and we observe that that for large
    N the points below the diagonal look like trajectories of a random walk.
  • Winding Numbers and Toric h-Vectors of Convex Polytopes
    Sarah Nelson (University of Kentucky)
    For simplicial polytopes, Lee defined the winding number in a Gale Diagram corresponding to a given polytope. Then he showed that the k-th winding number matches the k-th component of the g-vector of the corresponding polytope. We are working on extending Lee's definition of the winding number to nonsimplicial polytopes. Our goal is to find an appropriate generalization of the k-th winding number in the Gale transform so that it relates to the toric g-vector.
  • Multigraphical Arrangements and Parking Functions
    Mikhail Mazin (Kansas State University)
    We prove injectivity of the generalized Pak-Stanley labeling of regions of multigraphical arrangements by multigraphical parking functions. In particular, we obtain a short and straightforward proof of the bijectivity of the original Pak-Stanley labeling of the regions of k-Shi arrangements by k-parking functions. Our result is a generalization of a result of Sam Hopkins and David Perkinson for bigraphical arrangements.
  • The Tropical Picard Group
    Alexander Lazar (University of Miami)
    It is possible to view finite graphs as combinatorial analogues of one-dimensional algebraic varieties. For example, one can define the notion of a divisor on a graph, which is related to a version of the chip-firing game on finite graphs. This analogy can be extended to higher-dimensional simplicial complexes. A tropical complex is a simplicial complex equipped with certain algebraic data related to its dual. One can define a combinatorial invariant called the tropical Picard group of a tropical complex, which is an analogue of the Picard group from algebraic geometry. We prove some basic results about the tropical Picard group for a particular class of simplicial complexes. This poster presents part of this proof, and gives a brief introduction to tropical complexes
  • The Local Action Lemma
    Anton Bernshteyn (University of Illinois at Urbana-Champaign)
    The Lov\'{a}sz Local Lemma is a very powerful tool in probabilistic combinatorics, that is often used to prove existence of combinatorial objects satisfying certain constraints. Moser and Tardos have shown that the LLL gives more than just pure existence results: there is an effective randomized algorithm that can be used to find a desired object. In order to analyze this algorithm Moser and Tardos developed the so-called entropy compression method. It turned out that one could obtain better combinatorial results by a direct application of the entropy compression method rather than simply appealing to the LLL. We provide a general statement that implies both these new results and the LLL itself.
  • Andrews and Bressoud Style Identities for Partitions and Overpartitions
    Kagan Kursungoz (Sabanci University)
    We propose a method to construct a variety of partition identities at once.
    The main applications are all-moduli generalization of some of Andrews' results in
    [Andrews, Parity in partition identities. Ramanujan Journal 23:45-90 (2010)]
    and Bressoud's even moduli generalization of Rogers-Ramanujan-Gordon identities,
    and their counterparts for overpartitions due to Lovejoy et al. and Chen et al.
    We obtain unusual companion identities to known theorems
    as well as to the new ones in the process.
    The novelty is that the method constructs solutions to functional equations
    which are satisfied by the generating functions.
    In contrast, the conventional approach is to show that a variant of well-known series
    satisfies the system of functional equations,
    thus reconciling two separate lines of computations.
  • The Topology of the Eternal Activity Complex of a Matroid
    Jose Alejandro Samper Casas (University of Washington)
    The external activity complex Act_simplicial complex recently defined by Ardila and Boocher. They showed
    that this complex is Cohen-Macaulay and asked questions about its
    topology. We prove that Act_every linear extension of LasVergnas's external/internal order
    <_ on="" the="" bases="" of="" m="" provides="" a="" shelling="" act="" we="">also show that every linear extension of LasVergnas's internal order
    <_ on="" m="" is="" a="" shelling="" of="" the="" independence="" complex="" m.="">As a corollary, Act}_As a corollary we prove that, after removing its cone points, the
    external activity complex is contractible if M contains U_{3,1} as a
    minor, and a sphere otherwise.

    This is based on joint work with Federico Ardila and Federico Castillo.
  • Weighted Enumerator for Spannning Trees in Simplicial Complexes
    Ghodratollah Aalipour (Kharazmi University)
    The Cayley's formula for the enumeration of spanning trees of complete graph is one of the oldest and most well-known results in enumerative combinatorics. This formula is a special case of Kirchhoff's matrix tree theorem which enumerates the number of spanning trees in a graph by computing eigenvalues of the associated Laplacian matrix. All these results have been extended to the weighted version by assigning some weights to the vertices or edges of graphs. Here we first introduce the concept of spanning trees in simplicial complexes. Then, we obtain the weighted enumerator for spanning trees of complete colorful complexes. This is joint work with Art Duval.
  • Catalan Shuffles
    Emma Cohen (Georgia Institute of Technology)Damir Yeliussizov (Kazakh-British Technical University)
    Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence, and derive estimates on the mixing time of the corresponding Markov chains. While our main result is in deriving an $O(n^2 \log n)$ bound on the mixing time in $L_2$ (and hence total variation) distance for the random transposition chain on Dyck paths, we raise several open problems, including the optimality of the above bound. Joint work with Prasad Tetali and Damir Yeliussizov.