Talks are in Math Sciences (MS) Room 6627, coffee/tea and poster session is in Room 6620 ("grad lounge")
9:00 - 9:15: welcome, introductions, coffee
9:15 - 9:45: Jason Fulman, Carries and shuffling
9:45 - 10:15: Olya Mandelshtam, Combinatorics of hopping particles on a ring
10:15 - 10:45: Daniel Johnston, Rainbow Turán numbers of paths and forests of stars
10:45 - 11:15: coffee/tea break and photo
11:15 - 11:45: Stephan Garcia, The graphic nature of supercharacters
11:45 - 12:15: Daniel Katz, Rudin-Shapiro-Like Polynomials with Low Correlation
12:15 - 1:45: lunch (we have made a group reservation at Wolfgang Puck Express on campus, they have several lunch menus for $10-$12)
1:45 - 2:15: Daqing Wan, Distinct coordinate sieving and applications
2:15 - 2:45: Nathan Williams, Sweeping up Zeta
2:45 - 3:15: Dominic Searles, Kohnert tableaux and quasi-key polynomials
3:15 - 3:45: poster session and coffee
3:45 - 4:15: Daniele Rosso, Geometric Robinson-Schensted Correspondence in type C
4:15 - 4:45: Damir Yeliussizov, Ehrhart polynomial of some Schlafli simplices
4:45 - 5:15: Shachar Lovett, The Birkhoff polytope and coding for distributed storage
Speakers:
Carries and shuffling
The "carries" when n random numbers are added base b form a Markov chain with an "amazing" transition matrix determined by Holte. This same Markov chain occurs in following the number of descents or rising sequences when n cards are repeatedly riffle shuffled. We give generating and symmetric function proofs and determine the rate of convergence of this Markov chain to stationarity. This work is joint with Persi Diaconis.
The graphic nature of supercharacters
The theory of supercharacters was developed by Diaconis-Isaacs and C. Andre to answer questions in combinatorial representation theory. Recent work has shown that this perspective sheds light on exponential sums of interest in number theory. We survey a few recent results about Gaussian periods and related sums. The talk features attractive visuals, see the corresponding Notices of the AMS article ("Gauss' hidden menagerie....", 62 (2015), no. 8, 878-888)
Rainbow Turán numbers of paths and forests of stars
For a fixed graph F, we consider the maximum number of edges in a properly edge-colored graph on n vertices which does not contain a rainbow copy of F, that is, a copy of F all of whose edges receive a different color. This maximum, denoted by ex*(n; F), is the rainbow Turán number of F, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Combinatorics, Probability and Computing 16 (2007)]. In this talk, we look at ex*(n; F) when F is a forest of stars, and consider bounds on ex*(n; F) when F is a path with l edges, disproving a conjecture in the aforementioned paper for l = 4.
Rudin-Shapiro-Like Polynomials with Low Correlation
The {\it Rudin-Shapiro polynomials} are a sequence of polynomials with coefficients in $\{-1,1\}$ arising from an elegant recursive construction that gives them interesting analytic and combinatorial properties. They are known to be very {\it flat} on the complex unit circle: if $f(z)$ is a Rudin-Shapiro polynomial, then the ratio of the largest value of $|f(e^{i\theta})|$ to the root mean square value is never larger than $\sqrt{2}$. If $f_0+f_1 z+\cdots + f_d z^d$ is Rudin-Shapiro polynomial, then calculations of Littlewood show that the sequence $f=(f_0,f_1,\ldots,f_d)$ of coefficients has very low {\it autocorrelation}: the inner products of $f$ with nontrivial translates of itself have considerably smaller mean square magnitude than what one would obtain with a typical random sequence in $\{-1,1\}^{d+1}$. The fact that the inner product is only large when the sequences are perfectly aligned makes such sequences very useful for synchronization in communications networks. For multi-user networks, we want to avoid confusing one user's sequence with another's, so we demand pairs of sequences that also have low {\it cross-correlation} (inner product with each other) at all shifts. We investigate pairs of {\it Rudin-Shapiro-Like polynomials}, a generalization of Shapiro's original recursive construction, and derive a general formula for their mean square cross-correlation. Borwein and Mossinghoff had shown that there are Rudin-Shapiro-like polynomials with low autocorrelation, and now we have found pairs of polynomials such that both have low autocorrelation and the pair has low mutual cross-correlation. There is a bound on how low these quantities can simultaneously be, and we have found infinite families of pairs that are close to the bound. This is joint work with Sangman Lee and Stanislav A. Trunov.
The Birkhoff polytope and coding for distributed storage
I will describe a journey that starts at error correcting codes for distributed storage, and leads to graph labeling, the study of the Birkhoff polytope graph and the representation theory of the symmetric group. On the technical side, we prove tight bounds for the chromatic number of the Birkhoff polytope graph, and use it to characterize the alphabet size needed for maximally recoverable codes in grid topologies. Joint work with Daniel Kane (UCSD) and Sankeerth Rao (UCSD).
Geometric Robinson-Schensted Correspondence in type C
The Robinson-Schensted correspondence is a combinatorial bijection between permutations of n elements and pairs of standard Young tableaux of the same shape with n boxes. It was proved by Spaltenstein and Steinberg that this bijection has a geometric interpretation in terms of the variety of complete flags in an n-dimensional vector space V. The correspondence can be generalized: for example we can consider signed permutations and pairs of standard bitableaux. I will explain how this generalization naturally appears geometrically when considering flags in Kato’s “exotic” version of symplectic space, although the combinatorial side is not completely understood yet. This is joint work with Vinoth Nandakumar and Neil Saunders.
Kohnert tableaux and quasi-key polynomials
We introduce the combinatorial model of Kohnert tableaux, based on the diagram model of A. Kohnert. We use Kohnert tableaux to introduce the quasi-key basis of the polynomial ring, which lifts the quasi-Schur polynomials of Haglund, Luoto, Mason and van Willigenburg. Key polynomials expand positively in quasi-key polynomials which in turn expand positively in fundamental slide polynomials. We give simple, positive combinatorial formulas for these expansions in terms of Kohnert tableaux, lifting the parallel expansions of a Schur polynomial into quasi-Schur polynomials into fundamental quasisymmetric polynomials. (Joint work with S. Assaf.)
Combinatorics of hopping particles on a ring
The inhomogeneous multispecies TASEP on a ring is an exclusion process that describes particles of different species hopping clockwise on a ring with parameters giving the hopping rates for different species. We introduce a combinatorial object that we call \emph{toric rhombic alternative tableaux} (TRAT), which are certain fillings of tableaux on a triangular lattice tiled with rhombi, and are in bijection with the well-studied \emph{multiline queues} of Ferrari and Martin. Using the TRAT, we obtain a formula for the stationary probabilities of this TASEP. Our results generalize results of Ayyer and Linusson and consequently give another proof for a special case of a conjecture of Lam and Williams which concerns a Markov chain on the symmetric group with remarkable enumerative properties.
Distinct coordinate sieving and applications
For symmetric subsets with distinct coordinates, we introduce a new sievie that greatly improves the standard inclusion-exclusion sieve using the cycle structure of the permutation group action. This has many applications in coding theory and combinatorics. This talk will be based on joint work with Jiyou Li.
Sweeping up Zeta
I will present my joint work with Hugh Thomas on the bijectivity of Drew Armstrong, Nick Loehr, and Greg Warrington's sweep maps.
Ehrhart polynomial of some Schlafli simplices
We show that Ehrhart polynomial of certain Schlafli simplices can be computed in polynomial time. We apply this result to the problem of counting integer partitions. In particular, we prove that the number of binary partitions of N can be computed in poly(log N) time. Joint work with Igor Pak.
Poster presenters:
Complexity of short generating functions
Short Generating Functions (GFs) were invented by Barvinok to count integer points in polyhedra. These objects allow one to take finite unions and intersections of boundedly many integer point sets in polynomial time. First, we extend a theorem by Barvinok and Woods to enumerate projections of integer points in infinite polyhedra using short GFs. Second, we show that the technology of short Generating Functions has some limits: one cannot hope to project an arbitrary short GF in polynomial time, unless #P = FP/poly. We also pose a question asking whether the set of PRIMES and SQUARES can be represented as short GFs. This is joint work with Igor Pak.
Enumeration of Basketball Walks
As coined by Arvind Ayyer and Doron Zeilberger, (old-time) basketball walks are directed lattice paths with steps in the set {(1,-2),(1,-1),(1,+1),(1,+2)}. We will show how to enumerate such walks of length n starting at the origin ending at altitude 1 that always stay above the x-axis in-between. Links to increasing trees avoiding a certain pattern will also be discussed.
On the poset and asymptotics of Tesler Matrices
Tesler matrices are certain integral matrices counted by the Kostant partition function and have appeared recently in Haglund's study of diagonal harmonics. In 2014, Drew Armstrong defined a poset on such matrices and conjectured that the characteristic polynomial of this poset is a power of (q−1). We use a method of Hallam and Sagan to prove a stronger version of this conjecture for posets of a certain class of generalized Tesler matrices. We also study bounds for the number of Tesler matrices and how they compare to the number of parking functions, the dimension of the space of diagonal harmonics.
Double-n Circular Societies
A society is a geometric space with a collection of subsets that represent voter preferences. We call this space the spectrum and these preference sets approval sets. The agreement proportion is the largest fraction of approval sets that intersect in a common point. Klawe et al. considered linear societies where approval sets are the disjoint union of two intervals, or double intervals. We examine arc-shaped double intervals on circular societies. We consider the case of pairwise-intersecting intervals of equal length and call these double-n circular societies. What is the minimal agreement proportion for double-n societies? We will show that the asymptotic agreement proportion is bounded between 0.2500 and 0.3529, and conjecture that the proportion approaches 1/3.