Poster Presentations

Great Plains Combinatorics Conference 2016

Poster Presentations

Lohans de Oliveira Miranda, Federal University of Piaui, Brazil

Little Proposition of the Great Plains

We prove the following proposition: Let x = (x1,x2,...,xi,...,xn) a permutation of order n = 4k + 2 and Dn,x = {xi−xn+1−i : i = 1, 2,...,2k+1}.  Then Dn,x has an odd number of odd numbered elements.  This is joint work with Liuhan Oliveira de Miranda (UFPI, Brazil) and Lossian Barbosa Bacelar Miranda (IFPI, Brazil).

Bennet Goeckner, University of Kansas

Partitioning Cohen-Macaulay Complexes

It was recently shown (by A. Duval, C. Klivans, J. Martin, and the presenter) that there exist Cohen-Macaulay simplicial complexes that are not partitionable.  This answered a longstanding conjecture of Stanley’s in the negative, but several similar conjectures still stand.  This poster will present the construction of a non-partitionable Cohen-Macaulay complex and some recent developments in related problems.

Thomas Grubb, Michigan State University

Restricted Growth Function Patterns and Statistics

We say that a sequence of positive integers w = w1…wn is a restricted growth function (RGF) if w1 = 1 and, for i ≥ 2, wi ≤ max{w1,…,wi−1} + 1. These objects are of interest because of a natural bijection between RGFs of length n and set partitions of {1, 2,…, n}.  Given two RGFs w and v, we say w contains v as a pattern if there is a subsequence of w which is order isomorphic to v.  Otherwise we say that w avoids v.  In this work we examine the generating functions ∑w∈Rn(v)qst(w), where Rn(v) is the set of RGFs of length n that avoid v and st(w) is one of four fundamental statistics defined on RGFs by Wachs and White.  In examining such generating functions we find connections between RGFs and objects such as integer partitions, lattice paths, noncrossing partitions, and more. This is joint work with Lindsey R. Campbell, Samantha Dahlberg, Robert Dorward, Jonathan Gerhard, Carlin Purcell, and Bruce E. Sagan.

Brent Holmes, University of Kansas

On Diameter of Hochster-Huneke Graphs of Stanley-Reisner Rings with Serre S2 Property

Given an ideal in a polynomial ring S, one can form a graph G(R) from the minimal prime ideals of R

=

S/l, where the vertices of G(R) are the minimal prime ideals of R and an edge connects two vertices v1, v2 if and only if height (v1 + v2) = 1.  G(R) is known as the Hochster-Huneke or dual graph of R.  The S2 property of R implies the connectedness of this graph.  We will discuss lower bounds and upper bounds for the maximum diameter of the dual graph in the case that R is S2 and I is a square free monomial ideal.

Jordan Lambert Silva, State University of Campinas, Brazil

Theta-Vexillary Signed Permutations

The theta-vexillary signed permutations are elements of the Weyl group Wn that index certain classes of degeneracy loci of type C.  Anderson and Fulton first described these permutations using triples of s-tuples of integers subject to specific conditions.  The objective of this work is to present different characterizations of theta-vexillary signed permutations, describing them in terms of pattern avoidance and also by arrangement of corners in its extended diagram.  These permutations generalize the vexillary signed permutation, holding similar combinatorial properties.

John Machacek, Michigan State University

Boundary Measurement Minors for Graphs on Surfaces

Given a directed graph embedded on a surface, we consider the boundary measurement matrix which has entries given by the signed sum of weighted paths between vertices.  In the case where the surface is a disk Postnikov showed that the maximal minors of this matrix are subtraction-free rational expressions.  For a disk Talaska has provided a combinatorial formula for these minors in the perfectly oriented case. We give a similar combinatorial formula for more general surfaces like an annulus or a torus.

Luke Nelsen, University of Colorado Denver

Monochromatic Cycle Partitions of Graphs with Large Minimum Degree

Lehel conjectured that in every 2-coloring of the edges of Kn, there is a vertex disjoint red cycle and blue cycle which span V(Kn).  Łuczak, Rödl, and Szemerédi proved Lehel’s conjecture for large n, Allen gave a different proof for large n, and finally Bessy and Thomassé gave a proof for all n.  Balogh, Barát, Gerbner, Gyárfás, and Sárközy proposed a significant strengthening of Lehel’s conjecture where Kn is replaced by any graph G with δ(G) > 3n/4; if true, this minimum degree condition is essentially best possible. They proved that δ(G) > (3/4 + o(1))n is sufficient to find cycles which span all but at most o(n) vertices.  DeBiasio and Nelsen proved that their conjecture holds when δ(G) > (3/4 + o(1))n.  Their proof makes use of the regularity—blow-up method along with notions such as robust expansion and absorbing.

Sara Solhjem, North Dakota State University

Semistandard Young Tableaux Polytopes

We define a new family of polytopes as the convex hull of certain {0,1,−1} matrices in bijection with semistandard Young tableaux.  We investigate various properties of these polytopes, including their inequality descriptions, vertices, and facets.

Eric Stucky, University of Minnesota

A Combinatorial Proof of Kachurovskii’s IVT

This is joint work with Yaxi Gao and Francis Su.  We develop a combinatorial proof to a theorem stated by Kachurovskii showing the existence of zeros for continuous maps satisfying a particular boundary condition.  We provide an alternative proof using Sperner’s Lemma with the advantage that it admits an algorithm to approximate zeros.

Rupei Xu, University of Texas at Dallas

Parameterization: Bridging Combinatorial Optimization and Extremal Graph Theory

Although both combinatorial optimization and extremal graph theory are areas dealing with extrema of a function defined in most cases on a finite set, these two areas develop in two different directions due to historical and cultural factors.  While combinatorial optimization is developing efficient (exact or approximate) algorithms and heuristics for solving specified types of problems, the extremal graph theory is finding bounds for various graph invariants under some constraints and with constructing extremal graphs.  While combinatorial optimization is more popular in operations research, theoretical computer science and all kinds of engineering applications, extremal graph theory is mostly in the domain of mathematics.  Can the two different areas benefit to each other?  If so, how?  In this talk, I will discuss the interconnections between the two areas with the example of studying the Minimum Rectilinear Steiner Tree Problem.  In 1955, Few asked the question what is the minimum Steiner tree of n points in a unit square.  Twenty-five years later, Chung and Graham gave a tighter bound and conjectured that the minimum rectilinear Steiner tree of n(n ≥ 2) points in a unit square is bounded by √n + 1, which is still open after twenty-five years.  However, in combinatorial optimization area, this problem is well studied.  The decision version of this problem is NP-complete, it only has exponential time exact algorithm, however, there exists a polynomial time approximation scheme (PTAS) due to the work of Arora.  I will show how the parameterization bridges the two different approaches for this problem and give further analysis.