Abstracts

Graduate Student Combinatorics Conference 2017

Not all mathematical formulas transferred correctly.  We can provide a correct pdf upon request.

Invited Talks

Sara Billey, University of Washington

Reduced words and a formula of Macdonald

Macdonald gave a remarkable formula connecting a weighted sum of reduced words for a permutation with the number of terms in a Schubert polynomial. We will review some of the fascinating results on the set of reduced words in order to put our main results in context. Then we will discuss a new bijective proof of Macdonald's formula based on Little's bumping algorithm. We will also discuss some generalizations of this formula based on work of Fomin, Kirillov, Stanely and Wachs. This project extends earlier work by Benjamin Young on a Markov process for reduced words of the longest permutation. This is joint work with Ben Young and Alexander Holroyd. 

Jacques Verstraete, University of California, San Diego

The probabilistic method: combinatorics and beyond

The probabilistic method was pioneered by Paul Erdos more than 70 years ago. Since that time, the tools and techniques have seen tremendous development, and is now an important part of modern mathematics. In this talk, I will highlight some off the salient techniques and theorems from combinatorics as well as some other areas of mathematics on which the probabilistic method has had an impact.

Contributed Talks

Mohsen Aliabadi, University of Illinois at Chicago

On matching in groups and vector spaces

A matching in an Abelian group GG is a bijection ff from a subset AA to a subset BB in GG such that a+f(a)∉Aa+f(a)∉A, for all a∈Aa∈A. This notion was introduced by Fan and Losonczy who used matchings in ℤnZn as a tool for studying an old problem of Wakeford concerning elimination of monomials in a generic homogenous form under a linear change of variables. We show a sufficient condition for the existence of matchings in arbitrary groups and its linear analogue, which lead to some generalizations of the existing results in the theory of matchings in groups and central extensions of division rings. We introduce the notion of relative matchings between arrays of elements in groups and use this notion to study the behavior of matchable sets under group homomorphisms.

Ahmed Umer Ashraf, Western University

Combinatorial characters

We derive an expression for generating function of irreducible character of 𝔖nSn corresponding to hook partition λ=(n−k,1k)λ=(n−k,1k). As an application we give an elementary proof of Rosas formula for Kronecker coefficients of hook shapes. The derivation involves defining homology on poset of brick tilings of Young diagrams.

Michelle Bodnar, University of California, San Diego

Rational noncrossing partitions

The Catalan numbers 𝖢𝖺𝗍(n)Cat(n), famously counting noncrossing partitions, have many generalizations. For instance, Fuss-Catalan numbers 𝖢𝖺𝗍(m)(n)Cat(m)(n) count the number of noncrossing partitions of [mn][mn], each of whose blocks have size divisible by mm. In this talk we'll focus on a further generalization, the rational Catalan numbers 𝖢𝖺𝗍(a,b)Cat(a,b), counting a collection of noncrossing partitions of [b−1][b−1]coming from rational a,ba,b-Dyck paths. I will review their construction, their basic properties, and the current research in this area.

Shawn Burkett, University of Colorado Boulder

Constructing supercharacter theories from lattices of normal subgroups

The normal subgroups of a finite group GG can be realized as intersections of stabilizers of the irreducible GG-modules. A supercharacter theory of GG is an analogue to the representation theory of GG where the theory is built from nearly irreducible modules. Via stabilizers, each such theory gives a sublattice of the lattice of normal subgroups, along with similar theories on each subquotient of the lattice. Now given a sublattice of the lattice of normal subgroups of a finite group GG and supercharacter theories on the covering relations, it is natural to ask under what conditions a supercharacter theory of GG can be built that respects the imposed covering relations. Recently, Aliniaeifard gave a construction which allows one to build from a sublattice L a supercharacter theory with L as its associated sublattice. However, this construction does not allow for the choice of supercharacter theories on each subquotient. In this talk, we will discuss Aliniaeifard's construction as well as some methods being developed to refine it to account for more general covering relations.

Joseph Burnett, The University of Texas at Dallas

A Generalization of the concept of arithmetic convolution to sets of divisors

If we consider a generalized set of divisors as a function A:ℕ→P(ℕ)A:N→P(N) (where ℕN is the natural numbers and P(ℕ)P(N) is the set of all subsets of the naturals) which satisfy the following restrictions for all nn: A(n)⊆D(n)A(n)⊆D(n), where D(n)D(n) is the set of the divisors of nn and1∈A(n)1∈A(n) Then we may define the following operation on these functions: Let A1(n)={d∈D(n):A(d)⋂A(nd)={1}}A1(n)={d∈D(n):A(d)⋂A(nd)={1}}. Our paper analyzes the properties of this operation and other related operations, which serve to produce fractal-like patterns when examining the graphs of these functions. We isolate special infinite families of these functions that have the property of being able to be visualized all at once from a single graphic, and provide explicit numerical results for related generalized Mobius functions.

Joseph Burnett and Austin Marstaller, The University of Texas at Dallas

Happy graphs

In Graph Theory, a graph is a set of vertices that may or may not be connected by some lines, called edges, or sometimes arcs. The graphs in this work are always complete and have edges and vertices colored red or blue. A graph is called Happy if there exists a vertex coloring such that each edge touches a vertex of its own color. We wish to find the exact size a graph must be so as to guarantee it contains a happy graph on nn vertices.

Charles Burnette, Drexel University

Abelian squares and their progenies

A polynomial P∈ℂ[z1,…,zd]P∈C[z1,…,zd] is strongly 𝔻dDd-stable if PP has no zeroes in the closed unit polydisc 𝔻⎯⎯⎯⎯d.D¯d. For such a polynomial define its spectral density function to be P(z)=(P(z)P(1/z⎯⎯⎯)⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯)−1.SP(z)=(P(z)P(1/z¯)¯)−1. An abelian square is a finite string of the form ww0ww0 where w0w0 is a rearrangement of w.w. We examine a polynomial-valued operator whose spectral density function’s Fourier coefficients are all generating functions for combinatorial classes of constrained finite strings over an alphabet of dd characters. These classes generalize the notion of an abelian square, and their associated generating functions are the Fourier coefficients of one, and essentially only one, L2(𝕋d)L2(Td)-valued operator. The asymptotic behavior of the coefficients of these generating functions as well as a combinatorial meaning to Parseval’s equation are given as consequences.

Federico Castillo, University of California, Davis

Newton polytopes of multidegrees

Recently June Huh classified, up to a multiple, all possible classes in the Chow ring of a product of two projective spaces that can be represented by an irreducible variety. As a first step to generalize this result to any number of copies of projective spaces, we focus only on the support of these classes. It turns out that the support of any irreducible variety can be described naturally as the integer points in a polytope, more precisely a generalized permutohedron.

Swee Hong Chan, Cornell University

Toric graphic arrangements

Consider an arrangement of linear hyperplanes integral with respect to a given lattice. The lattice gives rise to a torus and the arrangement to a subdivision of the torus. We are interested in the combinatorics of this subdivision. We will describe questions and results for particular lattices associated to root systems and arrangements associated to graphs.

Joseph Doolittle, University of Kansas

Reconstructing nearly simple polytopes from their graphs

A theorem of Blind and Mani shows that a simple polytope can be reconstructed from its graph. Kalai gave a very elegant proof of the theorem using fOfO as a way to measure "goodness" of an acyclic orientation. fOfO is defined for OO an orientation of a graph G=(V,E)G=(V,E), fO:=∑v∈V2indeg(v)fO:=∑v∈V2indeg(v). In this talk we will expand on the use of fOfO and present a new result about nearly simple polytopes, as well as showing a bound on the non-simplicity of a polytope which can be reconstructed from its graph.

Michael Earnest, University of Southern California

Longest Common Patterns in Permutations

A natural partial order on the set of permutations of all possible lengths is pattern containment. The concept of permutation patterns gives rise to a rich collection of combinatorial problems. We will discuss the longest common pattern, or LCP, between two permutations; this statistic is analogous to the longest common subsequence of two words, an important topic in computer science, specifically in bioinformatics. We have shown that the LCP between two random permutations of length nn grows proportionally to n2/3n2/3 as n→∞n→∞. In this talk, we demonstrate the proof of this fact, along with several generalizations and open problems.

Brittney Ellzey, University of Miami

A symmetric function arising from graph colorings

The chromatic polynomial of a graph counts the number of proper colorings of a graph using n colors. Stanley defined the chromatic symmetric function of a graph, which generalizes the chromatic polynomial. Shareshian and Wachs introduced a quasisymmetric refinement of the chromatic symmetric function for labeled graphs, namely the chromatic quasisymmetric function of a graph. We consider a generalization of these chromatic quasisymmetric functions from labeled graphs to directed graphs. In this talk, we will look at these definitions and some simple examples, as well as some of my results, generalizing work of Stanley, Shareshian-Wachs, and Athanasiadis.

Michael Engen, University of Florida

On the dimension of composition posets

We characterize the downsets of compositions (ordered by the generalized subword order) which have finite dimension in the sense of Dushnik and Miller. We identify four minimal downsets of infinite dimension and establish that any downset which does not contain one of these four has finite dimension.

Sean English, Western Michigan University

Large monochromatic components in sparse random hypergraphs

It is known, due to Gyárfás and Füredi, that for any rr-coloring of the edges of KnKn, there is a monochromatic component of order (1/(r−1)+o(1))n(1/(r−1)+o(1))n. They also showed that this is best possible if r−1r−1 is a prime power. Recently, Dudek and Prałat showed that the binomial random graph (n,p)G(n,p) behaves very similarly with respect to the size of the largest monochromatic component. More precisely, it was shown that a.a.s.\ for any rr-coloring of the edges of (n,p)G(n,p) and arbitrarily small constant α>0α>0, there is a monochromatic component of order (1/(r−1)−α)n(1/(r−1)−α)n, provided that pn→∞pn→∞. As before, this result is clearly best possible. In this talk we present a generalization of this result to hypergraphs. Specifically we show that in the kk-uniform random hypergraph, (k)(n,p)H(k)(n,p) a.a.s. for any kk-coloring of the edges, there is a monochromatic component of order (1−α)n(1−α)n and for any k+1k+1 coloring, there is a monochromatic component of order (1−α)kk+1n(1−α)kk+1n.

Joshua Fallon, Louisiana State University

A family of 2-crossing-critical graphs on the projective plane

A graph G is said to be 2-crossing-critical if it has crossing number at least two and every proper subgraph of G has crossing number less than two. Bokal, Oporowski, Richter, and Salazar recently determined all the 3-connected 2-crossing-critical graphs containing a subdivision of the Möbius Ladder V10. These graphs are members of a family generated by joining certain tiles in sequence. We show a closely related family of tile joins that are 2-crossing-critical on the real projective plane. Analogous to the plane case, these graphs have projective crossing number at least two and each proper subgraph has projective crossing number less than two. We also discuss ongoing work toward extending this family to all non-orientable surfaces.

Tara Fife, Louisiana State University

An extension of the class of laminar matroids

A matroid is a finite set with a collection of independent sets that behave like linearly independent sets in a vector space. The rank, r(X)r(X), of a set XX is the size of a largest independent subset of XX, and the closure, cl(X)cl(X), of XX is {x:r(X∪{x}=r(X)}{x:r(X∪{x}=r(X)}. A circuit is a minimal dependent set. The widely studied class of nested matroids consists of those matroids where, for any two circuits C1C1 and C2C2, either cl(C1)⊆cl(C2)cl(C1)⊆cl(C2) or cl(C2)⊆cl(C1)cl(C2)⊆cl(C1). Thus nested matroids are 00-laminar where a matroid is kk-laminar if, for any two circuits C1C1 and C2C2 with r(cl(C1)∩cl(C2)≥kr(cl(C1)∩cl(C2)≥k, either cl(C1)⊆cl(C2)cl(C1)⊆cl(C2) or cl(C2)⊆cl(C1)cl(C2)⊆cl(C1). Earlier work has characterized 0-laminar matroids and 1-laminar matroids in numerous ways. This talk will discuss the behavior of the class of 2-laminar matroids.

Nathan Fox, Rutgers University

Nice solutions to nested recurrence relations

Linear recurrence relations, such as the Fibonacci recurrence F(n)=F(n−1)+F(n−2)F(n)=F(n−1)+F(n−2), are completely understood. On the other hand, few general facts are known about general recurrences, and there are many open questions. In particular, nested recurrence relations, such as the Hofstadter Q-recurrence Q(n)=Q(n−Q(n−1))+Q(n−Q(n−2))Q(n)=Q(n−Q(n−1))+Q(n−Q(n−2)), can display a wide diversity of behaviors depending on the initial conditions. In this talk, we will explore some of the possible types of solutions we can achieve to such recurrences. We will focus primarily on finding solutions that also satisfy linear recurrences, though we will see some more unusual solutions as well.

Mac Gallagher, George Mason University

The Hirsch conjecture and the diameters of polytopes

The diameters of polytopes are studied in mathematical optimization because of their relation to the simplex method for linear programming. In 1957, Hirsch posed a conjecture on the maximum diameter of polytopes. While the conjecture was ultimately false (Santos, 2010), many related questions still remain at large, and the diameter problem for polytopes still remains largely unsolved. We will describe the relationship between the Hirsch conjecture and linear programming and discuss some of the current techniques being used to solve the problem.

Zachary Gershkoff, Louisiana State University

A notion of minor-based matroid connectivity

For a matroid NN, a matroid MM is NN-connected if every two elements of MM are in an NN-minor together. Thus a matroid is connected if and only if it is U1,2U1,2-connected. A proof is presented that U1,2U1,2 is the only connceted matroid NN such that if MM is NN-connected, then M∖eM∖e or M/eM/e is NN-connected.

Alejandro Ginory, Rutgers University

The combinatorics of Weingarten calculus

Integration on compact matrix groups with respect to the Haar measure has many applications, e.g. in physics and statistics. The method of Weingarten calculus, introduced by Benoit Collins, gives combinatorial methods for computing the integrals of polynomials in matrix coefficients over the unitary, orthogonal, and symplectic groups. These methods involve symmetric functions such as the Jack polynomials. In this talk, I will discuss the combinatorics of Weingarten calculus and some explicit recursive methods for carrying out these computations.

Kevin Grace, Louisiana State University

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 a conjecture made by Archer in 2005.

Corbin Groothuis, University of Nebraska-Lincoln

D-matching polynomials

For any graph GG we may construct an associated polynomial called the matching polynomial, which is a variant on a generating function for matchings of GG. When GG is a cycle or path graph with nn vertices, the resulting polynomials are essentially the Chebyshev polynomials Tn(x)Tn(x) and Un(x)Un(x) respectively. It is known that the only divisibility relations among the UnUn have the form Umn−1Un−1=Um−1⋅TnUmn−1Un−1=Um−1⋅Tn; we interpret this equality combinatorially. In particular we show the right-hand side is an object with combinatorial meaning, called the d-matching polynomial by Hall, Pruder and Sawin(2015).

Brent Holmes, University of Kansas

On the diameter of Hochster-Huneke graphs of Stanley-Reisner rings with Serre (S2S2) property and Hirsch type bounds on abstractions of polytopes

Let RR be a Noetherian commutative ring of positive dimension. The Hochster-Huneke graph of RR (sometimes called the dual graph of SpecRSpecR and denoted by (R)G(R)) is defined as follows: the vertices are the minimal prime ideals of RR, and the edges are the pairs of prime ideals (P1,P2)(P1,P2) with height(P1+P2)=1height(P1+P2)=1. If RR satisfies Serre's property (S2)(S2), then (R)G(R) is connected. In this note, we provide lower and upper bounds for the maximum diameter of Hochster-Huneke graphs of Stanley-Reisner rings satisfying (S2)(S2). These bounds depend on the number of variables and the dimension. Hochster-Huneke graphs of (S2)(S2) Stanley-Reisner rings are a natural abstraction of the 11-skeletons of polyhedra. We discuss how our bounds imply new Hirsch-type bounds on 11-skeletons of polyhedra.

Michael Joseph, University of Connecticut

Noncrossing partitions, toggles, and homomesies

We introduce n(n−1)/2n(n−1)/2 "toggling" involutions on the set NC(n)NC(n) of noncrossing partitions of [n]:={1,2,…,n}[n]:={1,2,…,n}. These involutions generate a group under composition, called the toggle group. For many operations TT within the toggle group, several statistics ff on NC(n)NC(n) are homomesic, meaning ff has the same average across every orbit. These statistics include the number of blocks of the partition. We will also discuss a consequence of the homomesy results to the sizes of orbits. This is joint work with David Einstein, Miriam Farber, Emily Gunawan, Matthew Macauley, James Propp, and Simon Rubinstein-Salzedo.

Ezgi Kantarci, University of Southern California

Type B analogues of ribbon tableaux

We introduce a shifted analogue of the ribbon tableaux defined by James and Kerber. For any positive integer kk, we give a bijection between the kk-ribbon fillings of a shifted shape and regular fillings of a ⌊k/2⌋⌊k/2⌋-tuple of shapes called its kk-quotient. We also define the corresponding generating functions, and prove that they are symmetric, Schur positive and Schur Q positive.

Hee Sun Kim, University of Kansas

Weighting of new context models

Contexts of stationary ergodic sources are considered not necessarily consecutive sequences of symbols of the past. The introduced context set model of a source provides a code that can achieve less parameter redundancy than the code the context tree and generalized context tree models provide. The problem of coding sources with unknown context set is addressed for multialphabet sources. Information on the maximum memory length of the source is not required; it may be even infinite. The Context Set Weighting method is introduced to efficiently calculate a mixture of the Krichevsky-Trofimov distributions over possible context sets. For a message of length n, the number of possible context sets is larger than exponential in n, but the Context Set Weighting is shown to be computable in time polynomial in n. The obtained coding distribution is proved to provide a universal code.

Westin King, Texas A&M University

A correspondence between parking functions on directed mappings and directed trees

Bruner and Panholzer extend the notion of a parking function to both rooted labeled trees in which edges are oriented towards the root and digraphs of mappings, f:[n]→[n],f:[n]→[n], with edges oriented a→f(a)a→f(a). If FnFn is the number of parking functions on rooted labeled trees with nn vertices and MnMn is the number of parking functions on mappings, then the authors demonstrate that nFn=MnnFn=Mn. In this talk, I will extend the notion of parking function to trees in which the edges are oriented away from the root and digraphs of mappings with edges f(a)→af(a)→a and show the same relationship holds.

Bo Lin, University of California, Berkeley

Tropical Fermat-Weber points

We investigate the computation of Fermat-Weber points under the tropical metric, motivated by its application to the space of equidistant phylogenetic trees with NN leaves realized as the tropical linear space of all ultrametrics. While the Fréchet mean with the CAT(0)CAT(0)-metric of Billera-Holmes-Vogtman has been studied by many authors, the Fermat-Weber point under tropical metric in tree spaces is not well understood. In this paper we investigate the Fermat-Weber points under the  tropical metric and we show that  the set of tropical Fermat-Weber points is a classical convex polytope. We identify conditions under which this set is a singleton. This is a joint work with Ruriko Yoshida.

Jephian C.-H. Lin, Iowa State University

Note on von Neumann and Rényi entropies of a graph

Let GG be a graph and LL its combinatorial Laplacian matrix. The scaled Laplacian matrix 1tr(L)L1tr(L)L is a positive semidefinite matrix with trace one, so it can be written as ∑ni=1λiEi∑i=1nλiEi, where λiλi's are the eigenvalues and EiEi's are rank-one matrices. Since λi≥0λi≥0 and ∑ni=1λi=1∑i=1nλi=1, such a matrix can be viewed as a mixture of several rank-one matrices and is called a density matrix in quantum information. The von Neumann entropy and the Rényi entropy measure the mixedness of a density matrix; in this talk, we will discuss how these entropies relate to different graphs.

Andrew Lohr, Rutgers University

Numerics for lattice paths

One of the many ways we can look at Catalan numbers is by the number of paths of steps west and north in ℕ2N2 that stay below the line y=x going from (0,0) to (n,n). There are some open questions when we change the slope of the line we have to stay below. An even less studied variation of this is if we consider paths in ℕ3N3 in a region bounded by planes.

Amanda Lohss, Drexel University

Tableaux and the ASEP

The ASEP is a particle model (which will be defined in this talk) that has been used extensively since 1970 in physics, biology, and biochemistry. Interestingly enough, in the past decade, various types of tableaux have been introduced to provide a simple combinatorical formula for the steady state distribution of the ASEP. Some of these tableaux will be introduced in this talk and the formula they provide will be discussed. Lastly, some results on these tableaux, which are significant in terms of the ASEP, will be presented.

Jack Love, George Mason University

Polygon spaces

Imagine 4 drinking straws arranged as a square on a flat table. Now imagine a string is running through them, and this string is fixed to the table with a tack at one of the vertices of the square. Now you can start moving the straws around to get lots of (uncountably many) parallelograms, including a few degenerate ones. Every parallelogram has two diagonals, so we can map the space of parallelograms to ℝ2R2 by sending a parallelogram to its diagonal lenghts. What does the image of this map look like? We know the answer to this question, and it has lots of nice features that we'll talk about. But what if we replace "4" with "nn" and "flat table" with "ℝdRd"? We present recent results and open questions.

Megan Ly, University of Colorado Boulder

Centralizer algebras of unipotent upper triangular matrices

Classical Schur-Weyl duality relates the irreducible characters of the symmetric group SnSn to the irreducible characters of the general linear group GLn(ℂ)GLn(C) via their commuting actions on tensor space. We investigate the analog of this result for the group of unipotent upper triangular matrices UTn(𝔽q)UTn(Fq). In this case the character theory of UTn(𝔽q)UTn(Fq) is unattainable, so we must employ supercharacter theory, creating a striking variation.

John Machacek, Michigan State University

The chromatic symmetric function: Hypergraphs and beyond

Stanley's chromatic symmetric function is a graph invariant which has been (and still is) the subject of much research. We will (attempt to) make case for the study of a chromatic symmetric function in hypergraphs and other generalizations of graphs. The existence (or non-existence) of two non-isomorphic trees with equal chromatic symmetric functions is an open problem. Martin, Morin, and Wagner have shown that the chromatic symmetric function of a tree determines its degree sequence. We will show that the degree sequence of a uniform hypertree is determined by its chromatic symmetric function, but there do exist non-isomorphic pairs of 3-uniform hypertrees with the same chromatic symmetric function. A definition of generalized graph coloring will be given and will encompass graph and hypergraph coloring as well as oriented coloring and acyclic coloring.

Viswambhara Makam, University of Michigan

Polynomial degree bounds for matrix semi-invariants

We study the left-right action of SL(n) x SL(n) on several copies of n×nn×n matrices. We prove that the null cone is defined by invariants of degree n(n−1)n(n−1) and that consequently invariants of degree ≤n6≤n6 generate the ring of invariants. We give generalizations to rings of invariants associated to quivers. Our results have applications in computational complexity, notably a polynomial time algorithm for non-commutative rational identity testing.

Carolyn Mayer, University of Nebraska - Lincoln

A two-phase graph decoder for LT codes with partial erasures

Luby Transform (LT) codes are a class of rateless erasure codes in which encoding symbols are generated and transmitted until all users receive enough symbols to reconstruct the original message. Encoding is performed by dynamically constructing a bipartite graph according to a specified degree distribution. Recently, partial erasure channels have been introduced to model applications in which some information may remain after an erasure event. In this talk, we will discuss a two-phase graph decoder for LT codes with partial erasures.

James McKeown, University of Miami

Alternating sign matrices and the Waldspurger decomposition

In the mid 2000's Lie theorists such as Waldspurger and Meinrenken used topological methods to prove some surprising new theorems in Coxeter theory. Specifically, they exhibited new tilings of space by simplices in bijection with Weyl group elements for each of the classical types. In type A, where the Weyl group is the symmetric group, I will give a concrete combinatorial description of these simplices by defining the "Waldspurger Transformation" of a permutation matrix. When one applies this transformation to the larger class of alternating sign matrices, the image has a nice description relating to the MacNeille Completion of the Bruhat order. I will show that Waldspurger matrices for types B and C, are equivalent to "folded Waldspurger" matrices of type A, and we consider ways of defining "type B" alternating sign matrices.

Kyle Meyer, University of California, San Diego

Descent representations of a generalization of the coinvariant algebra

The coinvariant algebra RnRn is a well-studied 𝔖nSn-module that gives a graded version of the regular representation of 𝔖nSn. Using a straightening algorithm on monomials and the Grasia-Stanton basis, Adin, Brenti, and Roichman give a description of the Frobenius image of RnRn, graded by partitions, in terms of descents of standard Young tableaux. Motivated by the Delta Conjecture of Macdonald polynomials, Haglund, Rhoades, and Shimozono give an extension of the coinvariant algebra Rn,kRn,k and an extension of the Garsia-Stanton basis. We extend the results of Adin, Brenti, and Roichman to Rn,kRn,k.

Marie Meyer, University of Kentucky

Laplacian simplices

In this talk we will introduce a polyhedral construction arising from the well studied Laplacian matrix of a graph, namely, taking the convex hull of the columns of the matrix to form a simplex. We will discuss known properties of these simplices according to graph type.

Ada Morse, University of Vermont

DNA origami and knots in graphs

Motivated by the problem of determining unknotted routes for the scaffolding strand in DNA origami self-assembly, we examine existence and knottedness of A-trails in (necessarily Eulerian) graphs embedded on surfaces in space. We construct infinite families of embedded graphs containing unknotted A-trails (for any genus surface) as well as infinite families of embedded graphs containing no unknotted A-trails (for surfaces other than the sphere.) While not every embedded Eulerian graph contains an unknotted A-trail, we conjecture that every abstract Eulerian graph has some embedding containing an unknotted A-trail. We prove this in the 4-regular case by giving an algorithm for finding such embeddings. In closing, we discuss some results regarding which knots can be constructed from A-trails of rectangular grids.

Lauren Nelsen, University of Denver

Many edge-disjoint rainbow spanning trees in general graphs

A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for nn and CC large enough, if GG is an edge-colored copy of KnKn in which each color class has size at most n/2n/2, then GG has at least ⌊n/(Clogn)⌋⌊n/(Clog⁡n)⌋ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if GG is any edge-colored graph with nn vertices in which each color appears on at most δ⋅λ1/2δ⋅λ1/2 edges, where δ≥Clognδ≥Clog⁡n for nn and CC sufficiently large and λ1λ1 is the second-smallest eigenvalue of the normalized Laplacian matrix of GG, then GG contains at least ⌊δ⋅λ1Clogn⌋⌊δ⋅λ1Clog⁡n⌋ edge-disjoint rainbow spanning trees.

Luke Nelsen, University of Colorado Denver

Erdős-Szekeres online

In 1935, Erdős and Szekeres proved that (m−1)(k−1)+1(m−1)(k−1)+1 is the minimum number of points in the plane (ordered by their xx-coordinates) which definitely contain an increasing (also ordered by yy-coordinates) subset of mm points or a decreasing subset of kk points. We consider their result from an online game perspective: Let points be determined one by one by player A first determining the xx-coordinate and then player B determining the yy-coordinate. What is the minimum number of points such that player A can force an increasing subset of mm points or a decreasing subset of kk points? In this talk, we discuss the distinction between the original setting from this new one and present some small results. Thanks to the 2016 GRWC workshop, work on this question is underway jointly with Kirk Boyer, Lauren M. Nelsen, Florian Pfender, Lizard Reiland and Ryan Solava.

David Nguyen, University of California, Santa Barbara

Closed form formulas for a class of generalized Dyck paths

Walks on the integers with steps −1−1 and +1+1 correspond to the classical Dyck paths, which are well known to be enumerated by Catalan numbers. A natural generalization is to consider walks on the integers with steps −h,…,−1,+1,…,+h−h,…,−1,+1,…,+h. In this talk, we will show how to find explicit formulas enumerating walks of length n for the case h=2h=2, using a method of wide applicability, the so-called "kernel method", in terms of nested sums of binomial coefficients. Interesting links to increasing trees will also be discussed.

Danh Nguyen Luu, University of California, Los Angeles

Presburger arithmetic and integer points in polyhedra

Presburger arithmetic is the first order theory on integers that allows only additions and inequalities. It is the natural language to express many problems in integer programming and optimization. Central in this topic the search for effective algorithms to decide the truth of Presburger sentences. We present various new hardness and polynomial-time results in this topic. These results are intimately related to the study of integer points in polyhedra and their projections via linear maps.

Pouria Salehi Nowbandegani, Vanderbilt

Forbidden properly edge-colored subgraphs that force large highly connected monochromatic subgraphs

We consider the connected graphs GG that satisfy the following property: If n≫m≫kn≫m≫k are integers, then any coloring of the edges of KnKn, using mm colors, containing no properly colored copy of GG, contains a monochromatic kk-connected subgraph of order at least n−f(G,k,m)n−f(G,k,m) where ff does not depend on nn. If we let G denote the set of graphs satisfying this statement, we exhibit some infinite families of graphs in G as well as conjecture that the cycles in G are precisely those whose lengths are divisible by 33. Our main result is that C6∈C6∈G.

McCabe Olsen, University of Kentucky

Hilbert bases and lecture hall partitions

In the interest of finding the minimum additive generating set for the set of ss-lecture hall partitions, we compute the Hilbert bases for the ss-lecture hall cones in certain cases. In particular, we compute the Hilbert bases for two well-studied families of sequences, namely the 1modk1modk sequences and the ℓℓ-sequences. Additionally, we provide a characterization of the Hilbert bases for uu-generated Gorenstein ss-lecture hall cones in low dimensions.

Alperen Ozdemir, University of Southern California

A random walk on the symmetric group

We study the mixing time of the Markov chain on SnSn starting with a random (n−k)(n−k)-cycle then continuing with random transpositions where kk is a fixed number. The bounds that yield the mixing time involve certain estimates on the characters of the symmetric group. The analysis is carried out by using combinatorics of Young tableaux.

Alex Schaefer, Binghamton University

Signed Graphs, Permutability, and 22-Transitive Perfect Matchings

A signed graph is a triple (V,E,σ)(V,E,σ) where (V,E)(V,E) is a graph and σ:E↦{+,−}σ:E↦{+,−} is a function. A switching of a signed graph results from choosing a (possibly empty) edge cut and negating all the edges in the cut, which partitions the ways of signing a graph. The search for an invariant of these classes led to a vector space of negative cycle vectors, of which a natural spanning set seems to arise from classes of graphs whose sets of negative edges correspond to matchings, but only when the matching obeys a permutability property. Attempts to understand this phenomenon led to (in joint work with E. Swartz) a complete classification of graphs with perfect matchings such that the automorphism group is 22-transitive on the matching.

Alex Schulte, Iowa State University

Anti-van der Waerden number of 33-term arithmetic progressions

A set is rainbow if each element of the set is a different color. A coloring is unitary if at least one color is used exactly once. The anti-van der Waerden number of the integers from 11 to nn, denoted by aw([n],3)aw([n],3), is the least positive integer rr such that every exact rr-coloring of [n][n] contains a rainbow 33-term arithmetic progression. The unitary anti-van der Waerden number of the integers from 11 to nn, denoted by awu([n],3)awu([n],3), is the least positive integer rr such that every exact unitary rr-coloring of [n][n] contains a rainbow 33-term arithmetic progression. The anti-van der Waerden number of a graph GG, denoted by aw(G,3)aw(G,3), is the least positive integer rr such that every exact rr-coloring of GG contains a rainbow 33-term arithmetic progression. Bounds for the anti-van der Waerden number and the unitary anti-van der Waerden number on the integers have been established. The exact value of the unitary anti-van der Waerden number of the integers is equal to the anti-van der Waerden number of the integers and these are given by aw([n],3)=awu([n],3)=⌈log3n⌉+2aw([n],3)=awu([n],3)=⌈log3⁡n⌉+2. 

Elizabeth Sheridan Rossi, University of Connecticut

Homomesy for Foatic actions on the symmetric group

Homomesy is a phenomenon identified by Tom Roby and James Propp in 2013. By looking at a group action on a set of combinatorial objects, we partition them into orbits. From here we discuss statistics that are homomesic, meaning they have the same average value over each orbit. In this talk we will focus primarily on homomesies for actions on the symmetric group, in particular the so called "Foatic maps", created using the well known "fundamental bijection" of Rényi and Foata.

Rahul Singh, Northeastern University

Conormal variety of Schubert variety in a cominuscule Grassmannian

Let GG be a Chevalley group associated to an irreducible root system and PP a co-minuscule parabolic subgroup of GG. Lakshmibai et al have shown that the cotangent bundle T∗G/PT∗G/P embeds as an open subset of a Schubert variety associated to the loop group of GG. We give a complete classification of the Schubert varieties X(w)X(w) in G/PG/P whose conormal variety N∗X(W)N∗X(W) is itself dense in a Schubert subvariety under this identification.

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}{0,1,−1} matrices in bijection with semistandard Young tableaux. We investigate various properties of these polytopes, including their inequality descriptions, vertices, and facets.

Avery St. Dizier, Cornell University

Flow polytopes and degree sequences

The flow polytope associated to an acyclic directed graph is the set of all nonnegative flows on the edges of the graph with a fixed netflow at each vertex. I will describe basic properties and some interesting examples of flow polytopes. Next, I'll examine a procedure for triangulating certain flow polytopes and some nice properties of the resulting triangulation. If there's time, I'll briefly explain how special cases of this construction have been shown to encode some Schubert and Grothendieck polynomials, and present some open questions for further research.

Everett Sullivan, Dartmouth College

Linear chord diagrams with long chords

A linear chord diagram of size nn is a partition of the set {1,2,…,2n}{1,2,…,2n} into sets of size two, called chords. From a table showing the number of linear chord diagrams of degree nn such that every chord has length at least kk, we observe that if we proceed far enough along the diagonals, they are given by a geometric sequence. We prove that this holds for all diagonals, and identify when the effect starts.

Justin Troyka, Dartmouth College

Exact and asymptotic enumeration of classes of centrosymmetric permutations

Roughly speaking, a permutation class is a set of permutations avoiding a certain set of forbidden patterns. Permutation classes and pattern-avoiding permutations have been studied in enumerative combinatorics for several decades. This talk concerns the counting of permutations in a given class that are centrosymmetric, meaning they are fixed by the reverse--complement map. At the Permutation Patterns conference of summer 2016, Alex Woo presented the following open question: in which permutation classes is it true that the exponential growth rate of the permutations of nn is the same as that of the centrosymmetric permutations of 2n2n? In this talk I will present preliminary findings from my investigation of this question, including some examples where the growth rates are not equal. I conjecture that equality holds for any class that is closed under direct sum or closed under skew sum; I also conjecture that one direction of inequality holds in the general case. This talk will be accessible to people who are not familiar with permutation patterns.

Shira Viel, North Carolina State University

Surfaces, orbifolds, and dominance

Consider the set of all triangulations of a convex (n+3)(n+3)-gon. These triangulations are related to one another by diagonal flips, and the graph defined by these flips is the 1-skeleton of the familiar nn-dimensional polytope known as the associahedron. The nn-dimensional cyclohedron is constructed analogously using centrally-symmetric triangulations of a regular (2n+2)(2n+2)-gon, with relations given by centrally-symmetric diagonal flips. Modding out by the symmetry, we may equivalently view the cyclohedron as arising from "triangulations of an orbifold": the (n+1)(n+1)-gon with a single two-fold branch point at the center. 

In this talk we will introduce orbifold-resection, a simple combinatorial operation which maps the "once-orbifolded" (n+1)(n+1)-gon to the (n+3)(n+3)-gon. More generally, orbifold-resection maps a triangulated orbifold to a triangulated surface while preserving the number of diagonals and respecting adjacencies. This induces a relationship on the signed adjacency matrices of the triangulations, called dominance, which gives rise to many interesting phenomena. For example, the normal fan of the cyclohedron refines that of the associahedron; work is in progress to show that such fan refinement holds generally in the case of orbifold-resection. If time allows, we will explore other dominance phenomena in the context of the surfaces-and-orbifolds model.

Corey Vorland, North Dakota State University

Homomesy for J([2]×[a]×[b])J([2]×[a]×[b]) and multidimensional recombination

We generalize the notion of recombination defined by D. Einstein and J. Propp in order to study homomesy on 33-dimensional posets under rowmotion and promotion. We have two main results. We state and prove conditions under which recombination can be performed in nn-dimensions. We also apply recombination to show a homomesy result on the product of chains [2]×[a]×[b][2]×[a]×[b] under rowmotion and promotion. Additionally, we determine that this homomesy result does not generalize to arbitrary products of 33-chains.

George Wang, University of Pennsylvania

Properties and product formulas for quasi-Yamanouchi tableaux

Quasi-Yamanouchi tableaux connect the two most studied families of tableaux. They are a subset of semistandard Young tableaux that are also a refinement on standard Young tableaux, and they can be used to improve the fundamental quasisymmetric expansion of Schur polynomials. We prove a product formula for enumerating certain quasi-Yamanouchi tableaux and provide strong evidence that no product formula exists in general for other shapes. Along the way, we also prove some nice properties of their distribution and symmetry.

Zhaochen Wang, University of Wisconsin-Madison

Total positivity of Riordan-like arrays

A Riordan-like array is an infinite lower triangular matrix [Rn,k]n,k≥0[Rn,k]n,k≥0 defined by the recursive system

R0,0=1,Rn+1,0=∑j≥0zjRn,j,Rn+1,k+1=∑j≥0ajRn,k+j(n,k≥0),R0,0=1,Rn+1,0=∑j≥0zjRn,j,Rn+1,k+1=∑j≥0ajRn,k+j(n,k≥0),

where (an)n≥0(an)n≥0 and (zn)n≥0(zn)n≥0 called the A−A− and Z−Z−sequences of RR. This provides a common framework for Riordan arrays and triangles corresponding to the Catalan-like numbers. Our concern is the total positivity of such matrices, the log-convexity of the 0th column and the log-concavity of each row. This talk starts at the total positivity of a special case of Riordan arrays called the Catalan triangle. Then We will provide results of more general cases of Riordan arrays

Isaac Wass, Iowa State University

Rainbow paths and trees in properly-colored graphs

A graph GG is properly kk-colored if the colors {1,2,…,k}{1,2,…,k} are assigned to each vertex such that uu and vv have different colors if uvuv is an edge and each color is assigned to some vertex. A rainbow kk-path, a rainbow kk-star and a rainbow kk-tree is a path, star or tree, respectively, on kk vertices such that each vertex is a different color. We prove several results about the existence of rainbow paths, stars and trees in properly colored graphs, as well as their uses in proving various criteria about a graph's chromatic number. In particular, any graph GG properly colored with the minimum number of colors χ(G)χ(G) always contains every possible rainbow χ(G)χ(G)-tree.

Rupei Xu, University of Texas at Dallas

A new graph densification method and its applications

Given a graph G(V,E)G(V,E), the graph densification task is to find another graph H(V,E′)H(V,E′) such that E′E′ is significantly larger than EE while HHstill approximately maintains the desired properties of G.G. As dense graph has more established mature research results than sparse graphs, graph densification is a potentially powerful way to study sparse graphs. For example, MAX Cut has a PTAS on dense graphs, many property testing algorithms and sublinear time approximation algorithms rely on structural properties of dense graphs, Szemerédi's regularity lemma also works best for dense graphs. Unlike the well studied graph sparsification, we have little fundamental understanding of graph densification. In the literature, graph densification has been investigated in terms of spectral densifers and cut densifiers, as well as its connection to metric embedding. However, graph densifiers that are based on these methods do not always exist, and their principal understanding is still largely open. In this paper, a new graph densification method is investigated, based on the distance sequence approach by Bollobás. This method works for any graph, and it has deep connections with ball approximation and doubling metric approximation of graphs. This provides help in better understanding important issues, such as graph small world navigability, metric embedding, greedy rounding, failure detection and other applications. This is joint work with Professor Andras Farago.

Li Ying, Texas A&M University

Stability of the Heisenberg product on symmetric functions

The Heisenberg product is an associative product defined on symmetric functions which interpolates between the usual product and Kronecker product. I will give the definition of this product and describe some properties of it. One well known thing about the Kronecker product of Schur functions is the stability phenomenon discovered by Murnaghan in 1938. I will give an analogous result for the Heisenberg product of Schur functions.

Xiaowei Yu, Shandong University

Relaxed antimagic labeling of graphs

A kk-labeling of a graph GG is a mapping ϕϕ: E(G)→{1,2,…,m+k}E(G)→{1,2,…,m+k} such that all the edges receive different labels, where m=|E(G)|m=|E(G)|. Let μ(v)=∑uv∈E(G)ϕ(uv)μ(v)=∑uv∈E(G)ϕ(uv). A graph is called kk-antimagic if GG admits a kk-labeling with μ(u)≠μ(v)μ(u)≠μ(v) for any pair u,v∈V(G)u,v∈V(G). A kk-antimagic labeling is called an antimagic labeling if k=0k=0. If a graph GG admits an antimagic labeling, then GG is antimagic. In 2003, Hartsfield and Ringel proposed the famous Antimagic Graph Conjecture: Every graph without K2K2 is antimagic. Since this conjecture is widely open, they even conjectured that all the nice trees were antimagic, which is open as well. Recently, Bensmail et al. conjectured that a labeling of GG can guarantee that μ(u)≠μ(v)μ(u)≠μ(v) for any uv∈E(G)uv∈E(G), which is called edge-injective neighbor sum distinguishing edge-kk-coloring. In this talk, I will present the results about edge-injective neighbor sum distinguishing edge-kk-coloring.

Yan Zhuang, Brandeis University

On the joint distribution of peaks and descents over restricted sets of permutations

Let des(π)des(π) be the number of descents and pk(π)pk(π) the number of peaks of a permutation ππ. In 2008, Brändén proved that for any subset Π⊆𝔖nΠ⊆Sn invariant under a group action called the "modified Foata--Strehl action", the descent polynomial A(Π;t):=∑π∈Πtdes(π)A(Π;t):=∑π∈Πtdes(π) is γγ-positive and is related to the peak polynomial P(Π;t):=∑π∈Πtpk(π)P(Π;t):=∑π∈Πtpk(π) by the formula

A(Π;t)=(1+t2)n−1P(Π;4t(1+t)2).A(Π;t)=(1+t2)n−1P(Π;4t(1+t)2).

By taking Π=𝔖nΠ=Sn, this yields well-known results of Foata--Schützenberger (1970) and Stembridge (1997). In this talk, we produce a refinement of Brändén's formula: For any Π⊆𝔖nΠ⊆Sn invariant under the modified Foata--Strehl action, the descent polynomial A(Π;t)A(Π;t) and the polynomial P(Π;y,t):=∑π∈Πypk(π)tdes(π)P(Π;y,t):=∑π∈Πypk(π)tdes(π) encoding the joint distribution of the peak number and descent number over ΠΠ satisfy the relation 

A(Π;t)=(1+yt1+y)n−1P(Π;(1+y)2t(y+t)(1+yt),y+t1+yt).A(Π;t)=(1+yt1+y)n−1P(Π;(1+y)2t(y+t)(1+yt),y+t1+yt).

We then observe that many sets invariant under the modified Foata--Strehl action can be characterized in terms of pattern avoidance, and thus pose the question: Can we characterize all pattern classes invariant under the modified Foata--Strehl action? We conclude with some preliminary results in this direction, which is joint work with Richard Zhou (Lexington High School).