# 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* = 4*k* + 2 and *Dn,x *= {*xi−xn+1−i* : *i* = 1, 2,...,2*k*+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

*v*1,

*v*2 if and only if height (

*v*1 +

*v*2) = 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*) > 3*n*/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.