1pm-2:10pm: Poster Session (Extremal Combinatorics, Asymptotics, and Probability)

Moderator: Sergi Elizalde
(This is 11am US Pacific, 2pm US Eastern, 6pm GMT, 7pm in the UK, 8pm CEST, 9pm in Israel, 2am in China, 4am in Sydney, 6am in New Zealand)

Authors:

Title: Permutations and Involutions with Unique Longest Increasing Subsequences

Author: Miklos Bona (University of Florida)
Joint work with: Elijah DeJonge (University of Florida)

Abstract: We say that the permutation $p$ has a unique longest increasing subsequence, or ULIS, if $p$ has an increasing subsequence that is longer than all other increasing subsequences. For instance, 2314 has a ULIS, namely the sequence 234, but $p=246135$ does not, since 246, 245, 235, and 135 are all increasing subsequences of maximal length in $p$.

We consider permutations and involutions that avoid a given pattern $q$ of length three that have a ULIS. It is easy to see that taking reverse complements, there are four non-equivalent cases, namely 123, 132, 231, and 321, and one of them, 123, leads to a trivial situation.

We provide an explicit form for the generating function for the numbers $u_n(231)$ counting 231-avoiding permutations of length n with a ULIS, and we conclude that the exponential order of that sequence is about 3.383. The sequence $u_n(132)$ is difficult and has been studied before in the context of rooted plane unlabeled trees. It follows from that earlier work that for large $n$, about half of 132-avoiding permutations have a ULIS. We add some intriguing conjectures and questions to that discussion.

The case of $q=321$ is surprisingly challenging. We prove that the exponential order of the sequence $u_n(321)$ is 4, and that its generating function is not rational. This leaves open the question whether the sequence $u_n(321)/C_n$ converges to 0 or a positive constant. (Here $C_n$ denotes the $n$th Catalan number.) Note that this means that in the three nontrivial cases, the sequence $u_n(q)/C_n$ exhibits three different behaviors.

For involutions, the corresponding questions are straightforward, except for the case of $q=132$. For that case, we find a bijection with bidirectional lattice paths that have been studied in several papers before.

Poster: Bona_poster

[Back to the top]

Title: The feasible region for consecutive patterns of permutations is a cycle polytope

Author: Jacopo Borga (University of Zurich)
Joint work with: Raul Penaguiao (University of Zurich)

Abstract: We study proportions of consecutive occurrences of permutation patterns of a given size $k$. Specifically, the feasible limits of such proportions on large permutations form a region, called feasible region.

We show that this feasible region is a polytope, more precisely the cycle polytope of a specific graph called overlap graph. The latter is a labeled multi-graph defined as follows: the vertices are permutations of size $k-1$ and for every permutation $\pi$ of size $k$ we draw an edge labeled by $\pi$ from the pattern induced by the first $k-1$ indices of $\pi$ to the pattern induced by the last $k-1$ indices of $\pi$. The interpretation of the feasible region as a cycle polytope allows us to show that this is a $k!-(k-1)!$ dimensional polytope. Moreover, we give several descriptions of the polytope: we classify all its vertices and facets, and furthermore give a combinatorial description of its faces. All these results are generalized for any cycle polytope of a given strongly connected graph.

In our work we further connect our combinatorial results with the study of permutation limits: Indeed, we show that the limits of classical occurrences and consecutive occurrences are independent in some (precise) sense, and as a consequence, we show that the permuton limit of a sequence of permutations induces no constraints on the local limit and vice versa.

We will also present some extensions of our work to pattern avoiding permutations: Specifically, we study the feasible region restricted to permutations on a given permutation class. In this framework, we show that, for all pattern $\pi$ of size three, the feasible region of consecutive occurrences of $\pi$-avoiding permutations of a given size $k$ is still a cycle polytope but its dimension is $C_k-C_{k-1}$, where $C_k$ is the $k$-th Catalan number.

Poster: Borga_poster

[Back to the top]

Title: Counting substructures of highly symmetric structures

Author: Samuel Braunfeld (University of Maryland, College Park)

Abstract: Taking the substructures of a countable structure M naturally gives a hereditary class, and we define the growth rate of M as the function giving its number of (unlabeled) substructures of size n, up to isomorphism. In the 1970s, Peter Cameron began studying the growth rate for M satisfying the strong symmetry condition of homogeneity.

We give a classification of all homogeneous structures with subexponential growth rate, and describe the corresponding spectrum of possible growth rates. (The structures that arise are closely related to the permutation classes with growth rate below 2^n.) In particular, we prove there is a jump from polynomial growth to the partition function as well as infinite families of further jumps, and that these jumps in growth rate reflect jumps in the structural complexity of M. This confirms some conjectures of Cameron and Macpherson.

Poster: Braunfeld_poster
Video: Braunfeld_video

[Back to the top]

Title: Supertrees

Author: Colin Defant (Princeton University)
Joint work with: Noah Kravitz (Yale University), Ashwin Sah (Massachusetts Institute of Technology)

Abstract: A $k$-universal permutation, or $k$-superpermutation, is a permutation that contains all permutations of length $k$ as patterns. The problem of finding the minimum length of a $k$-superpermutation has recently received significant attention. One can ask analogous questions for other classes of objects. We will consider $k$-supertrees. For each $d\geq 2$, we focus on two types of rooted plane trees called $d$-ary plane trees and $[d]$-trees. Motivated by recent developments in the literature, we consider “contiguous” and “noncontiguous” notions of pattern containment for each type of tree. We obtain both upper and lower bounds on the minimum possible size of a $k$-supertree in three cases; in the fourth, we determine the minimum size exactly. One of our lower bounds makes use of a recent result of Albert, Engen, Pantone, and Vatter on $k$-universal layered permutations.

Poster: Defant_poster

[Back to the top]

Title: Pattern-Avoiding Involution Classes and their Growth Rates

Author: Jay Pantone (Marquette University)
Joint work with:
Part 1: Miklós Bóna (University of Florida), Cheyne Homberger (Department of Defense), Vincent Vatter (University of Florida)
Part 2: John Engbers (Marquette University), Christopher Stocker (Marquette University)

Abstract: An involution is a permutation that is its own group-theoretic inverse. For a set B of permutations (not necessarily involutions), Av^I(B) denotes the set of involutions that avoid all of the patterns in B. Note that such a set is typically not downward-closed.

There are seven Wilf-equivalence classes of pattern-avoiding involutions whose basis consists of a single pattern of length 4, although this is a little deceptive as, for example, Av^I(2413) = Av^I(2413, 3142). Gessel enumerated Av^I(1234) in 1990, and Brignall, Huczynska, and Vatter enumerated Av^I(2413) in 2008.

In 2015, Bóna, Homberger, Pantone, and Vatter enumerated two more of the seven Wilf-equivalence classes, Av^I(1342) and Av^I(2341), and pointed out several interesting features of the enumerations of the seven Wilf-equivalence classes. This is the first of two topics we discuss.

Arratia proved in 1999 that every permutation class whose basis consists of a single pattern has an exponential growth rate, i.e., the limit (a_n)^(1/n) exists. This argument does not carry over to pattern-avoiding involutions in all cases, only guaranteeing the existence of the growth rate of Av^I(beta) when beta is sum indecomposable. Among the seven Wilf-equivalence classes mentioned above, this covers all cases except Av^I(1234), Av^I(1324), and Av^I(1342). It is independently known that the first and third of these have exponential growth rates, because their enumeration is explicitly known. As our second topic we prove with a rather elaborate argument that Av^I(1324), too, has an exponential growth rate (joint with John Engbers and Christopher Stocker). Our argument generalizes to all sets of the form Av^I(1 + alpha + 1) for an involution alpha, but does not provide the actual values of these growth rates.

Poster: Pantone_poster
Video: Pantone_video

[Back to the top]

Title: Longest increasing subsequences for permutations avoiding one pattern of length three and another pattern of length four

Author: Gokhan Yildirim (Bilkent University)
Joint work with: Toufik Mansour (University of Haifa)

Abstract: The longest increasing subsequence (LIS) problem is an interesting question studied in combinatorics, probability, and computer science. It has a complete solution for uniformly random permutations in terms of determining the asymptotic order of the average length of LIS, the order of the deviations from the average, and the limiting distribution for the fluctuations. We determine the exact and asymptotic formulas for the average length of the longest increasing subsequences in random permutations avoiding one pattern of length three and another pattern of length four under the uniform probability distribution.

Poster: Yildirim_poster

[Back to the top]

Back to the Workshop Program