Pattern Avoidance, Statistical Mechanics and Computational Complexity

In this talk, we study a non-uniform distribution on permutations (of any given size), where the probability of a permutation is proportional to ${\theta }^{rec}$ where $rec$ denotes the number of records (a.k.a. left-to-right maxima). The motivation for defining this model of non-uniform random permutations is the analysis of algorithms. Indeed, when analyzing algorithms working on arrays of numbers (modeled by permutations), the uniform distribution on the set of possible inputs is usually assumed. However, the actual data on which these algorithms are used is rarely uniform, and often displays a bias towards “sortedness”. Our model has this bias towards “sortedness” while remaining tractable from the point of view of the analysis of algorithms. Our results on this model are of three types. First, we exhibit several efficient random samplers of permutations under this distribution. Second, we analyze the behavior of some classical permutation statistics, some of which with applications to the analysis of algorithms. Finally, we describe the “typical shape” of permutations in our model, by means of their (deterministic) permuton limit.

Drawing on a problem posed by Hertzsprung in 1887 (sometimes called the $n$-kings problem), we say that a permutation $w$ contains the Hertzsprung pattern $u$ if there is factor of $w$ that differ only by a constant from $u$ in the sense that there is a factor $w(d+1)w(d+2)\mathrm{\dots }w(d+k)$ such that $w(d+1)-u(1)=\mathrm{\cdots }=w(d+k)-u(k)$. Using a combination of the Goulden-Jackson cluster method and the transfer-matrix method we determine the joint distribution of occurrences of any set of Hertzsprung patterns, thus substantially generalizing earlier results by Jackson et al. on the distribution of ascending and descending runs in permutations. We apply our results to the problem of counting permutations up to pattern-replacement equivalences, and using pattern-rewriting systems – a new formalism similar to the much studied string-rewriting systems – we solve a couple of open problems raised by Linton et al. in 2012.

We will review results on the combinatorics of the exclusion process which is a classical model in statistical physics. We will explain why permutations and the pattern 31-2 appear when we study the exclusion process with open boundaries. We will then propose a series of open problems on the combinatorics of more general processes.

The independence polynomial of a graph is the generating polynomial of all its independent sets. Formally, given a graph $G$, its independence polynomial $Z_G(\lambda )$ is given by ${\sum }_I{\lambda }^{|I|}$, where the sum is over all independent sets $I$ of $G$. The independence polynomial has been an important object of study in both combinatorics, statistical physics and computer science. In particular, the algorithmic problem of estimating $Z_G(\lambda )$ for a fixed positive $\lambda$ on an input graph $G$ is a natural generalization of the problem of counting independent sets, and its study has led to some of the most striking connections between computational complexity and the theory of phase transitions. More surprisingly, the independence polynomial for negative and complex values of $\lambda$ also turns out to be related to problems in statistical physics and combinatorics. In particular, the locations of the complex roots of the independence polynomial of bounded degree graphs turn out to be very closely related to the Lovász local lemma, and also to the questions in the computational complexity of counting. In this talk we give new geometric criteria for establishing zero-free regions as well as for carrying out semi-rigorous numerical explorations. We then provide several examples of the (rigorous) use of these criteria, by establishing new zero-free regions. Joint work with Ferenc Bencs, Piyush Srivastava and Jan Vondrák.

Immanants are matrix functions that generalize determinants and permanents. Given an irreducible character $X_{\lambda }$ of $S_n$ for some partition $\lambda$ of n, the immanant associated with $\lambda$ is a sum-product over permutations $\pi$ in $S_n$, much like the determinant, but with $X_{\lambda }(\pi )$ playing the role of $sgn(\pi )$.

Hartmann showed in 1985 that immanants can be evaluated in polynomial time for sign-ish characters. More precisely, for a partition $\lambda$ of n with s parts, let $b(\lambda ):=n-s$ count the boxes to the right of the first column in the Young diagram of $\lambda$. The immanant associated with $\lambda$ can be evaluated in $n^O(b(\lambda ))$ time.

Since this initial result, complementing hardness results have been obtained for several families of immanants derived from partitions with unbounded $b(\lambda )$. This includes permanents, immanants associated with hook characters, and other classes. In this talk, we complete the picture of hard immanant families: Under a standard assumption from parameterized complexity, we rule out polynomial-time algorithms for well-behaved immanant families with unbounded $b(\lambda )$. For immanant families in which $b(\lambda )$ even grows polynomially, we establish hardness for #P and VNP.

This talk will survey three topics related to pattern avoidance, each motivated by an interesting question:

1. 1.

   Given a class $C$ of objects and a set $P$ of patterns from $C$, what is the smallest size of an object in $C$ that contains all of the patterns in $P$? We will focus on recent developments in which $C$ is either a class of words/permutations or a class of trees. The discussion of words/permutations is mostly taken from the survey article [9] as well as the more recent articles [6, 11]. The discussion of trees is taken from my article [8], which was written with Noah Kravitz and Ashwin Sah.

2. 2.

   How does permutation pattern avoidance interact with the group structure of the symmetric group? The first part of this topic will concern pattern-avoiding permutations with particular cycle types; the second part will concern permutations whose powers are required to avoid a pattern. This portion of the talk will draw from the articles [1, 3, 10, 2, 4, 5].

3. 3.

   If your socks come out of the laundry all mixed up, how should you sort them? We will discuss a novel foot-sorting algorithm that uses feet to attempt to sort a sock ordering; one can view this algorithm as an analogue of Knuth’s stack-sorting algorithm for set partitions. This part of the talk is based on my article [7], which was written with Noah Kravitz.

We describe bijections between three classes of combinatorial objects that have appeared in different contexts: lattice walks in simplicial regions as introduced by Mortimer–Prellberg (in a previous Dagstuhl Seminar), standard cylindric tableaux as introduced by Gessel–Krattenthaler and Postnikov, and sequences of states in the totally asymmetric simple exclusion process. Our perspective gives new insights into these objects, providing a vehicle to translate enumerative results and certain symmetries from one setting to another. As an example, we use a cylindric analogue of the Robinson–Schensted correspondence to give an alternative bijective proof of a recent result of Courtiel, Elvey Price and Marcovici relating forward and backward walks in simplices.

Fighting fish are combinatorial objects recently introduced by Duchi, Guerrini, Rinaldi and Schaeffer. They are polyomino-like objects which can branch out of the plane into independent substructures. The main motivation for considering such structures lies in their remarkable probabilistic properties. In particular, it is known that the average area of fighting fish having semiperimeter $n$ is of order $n^{5/4}$, which is a rather non-standard behaviour. The previously mentioned authors have discovered a lot of interesting combinatorics related to fighting fish. In particular, they have shown that the number of fighting fish of semiperimeter $n+1$ is given by $\frac{2}{(n+1)(2n+1)}\left(\genfrac{}{}{0pt}{}{3n}{n}\right)$, which is the same as the number of (West)-two-stack sortable permutations of size $n$. This result spurred much research to better understand the relationships between these objects (and others also counted by the same sequence). Wenjie Fang was able to describe a bijection between two-stack-sortable permutations and fighting fish which accounts for the above enumerative result (and also preserves a lot of other statistics). However, his bijection is recursive, and no direct bijection is known yet. In my talk I will present a general construction which maps any permutation to a certain labelled tree, which in turn encodes a unique fighting fish. Such a construction is not bijective in general, but it becomes a bijection when restricted to two-stack-sortable permutations, thus defining the (almost) direct bijection that was missing. As a matter of fact, this construction is equivalent to Fang’s one (in other words, it is a more direct version of the recursive procedure of Fang). Our hope would then be to use our construction to understand what the parameter area (on fighting fish) is on permutations, but we have not been successful yet. We have however some partial results, such as a description of those permutations (of fixed size) whose associated fighting fish has minimum area.

The sequence enumerating fighting fish with respect to semiperimeter also counts another class of permutations, namely those avoiding the two vincular patterns 3-1-4-2 and 2-41-3. Such permutations have been investigated by Claesson, Kitaev and Steingrimsson, in particular they provide a bijection with so-called $\beta (1,0)$-trees. These are trees whose recursive structure encodes somehow more naturally the recursive structures of fighting fish. This leads us to think that this class of permutations could be more useful to have a better combinatorial understanding of the area of fighting fish.

Pattern avoidance for permutations is a robust and well-established branch of enumerative combinatorics since the systematic study of Simeon and Schmidt in 1985. This talk summarizes recent progress on pattern avoidance in inversion sequences, including Mansour and Shattuck (2015), Corteel, Martinez, Savage, and Weselcouch (2016), Mansour and Yildirim (2022), and Testar (2022). Their work completely enumerated length-3 pattern avoidance except the case 120.

Recently, we completely classified all eight length-4 Wilf equivalences: 1011 = 1101 = 1110, 2110 = 2101 = 2011, 0221 = 0212, 0312 = 0321, 1102 = 1012, 2201 = 2210, 2301 = 2310, 3201 = 3210 = 3012. This talk mentions key lemmas that help establish the proofs that can be generalized to avoidance of longer patterns. Furthermore, there are four length-4 patterns whose enumeration appears in the OEIS by computer experiments: in addition to 0012 conjectured by Lin and Ma and proved by Chern, we resolve the cases 0000 and 0111 by proving the formulas for general 00…0 and 01…1 cases, giving bijections to bounded-degree label-increasing trees, and give a conjecture for 0021 which is then subsequently solved by Chern, Fu, and Lin and Mansour in 2022.

Permutation Pattern Matching (or PPM) is a fundamental decision problem in the study of permutations. Its input is a pair permutations P (the “pattern”) and T (the “text”), and the goal is to determine whether P is contained in T. While PPM is NP-hard on general inputs, it often becomes tractable when P or T are restricted to a proper hereditary permutation class.

In my talk, I will present some results and conjectures that attempt to describe the boundary between tractable and hard cases of such restrictions of PPM and other related problems. Specifically, I will focus on the relationships between these three topics: computational complexity of PPM restricted to a given permutation class; structural properties of a permutation class, such as the presence of large grid-like substructures; and the growth of width parameters, like tree-width or grid-width, within a given permutation class.

Already from the beginnings of the field, pattern-avoidance has been studied in tandem with algorithmic applications. For instance, Knuth’s study of permutation-patterns was motivated by connections to stack-sorting. In this talk I will survey results from the last few years on two related lines of work: (1) the study of algorithms, in various models of computation, for detecting, counting, or enumerating patterns, and (2) the study of pattern-avoidance as a source of algorithmic “easiness”: how pattern-avoidance of the input affects the complexity of seemingly unrelated algorithmic tasks.

A double cut-and-join (DCJ for short) is an operation that replaces two edges u, v and w, x in a graph with either u, x, v, w or u, w, v, x. This operation is of interest in a biological context, as it generalises several other well-studied mutations that are known to happen in genomes, e.g. (possibly signed) reversals or (block-)transpositions.

I consider two different graph models for representing genomes – namely, paths and perfect matchings – and study DCJs under the “prefix restriction”, which forces one of the cut edges to contain the first element of the genome. The talk focuses on sorting problems using these operations, which is a popular approach to reconstructing evolutionary scenarios between species, but also has applications in the field of interconnection network design, from which the prefix restriction originates. I will present some recent results on sorting genomes using variants of prefix DCJs using both models. Namely:

• $\mathrm{■}$

  new lower bounds on sorting genomes using prefix DCJs or prefix reversals;

• $\mathrm{■}$

  a polynomial-time algorithm for sorting signed genomes by prefix DCJs; and

• $\mathrm{■}$

  a 3/2-approximation algorithm for sorting unsigned genomes by prefix DCJs.

The latter algorithm is the first polynomial-time approximation algorithm with a ratio smaller than 2 for a prefix sorting problem not known to be in P.

Whenever we can ask if a certain mathematical object with prescribed properties exists, we can also ask how many such objects exist and how to generate a random one. We can also talk about the computational complexity of these counting and sampling problems, that is, how the running time of computer programs solving these problems increases with the input size. It turns out that counting and sampling are equally hard for a large class of computational problems. Equal hardness also frequently holds for estimating weighted sums and sampling from a distribution proportional to these weights. For example, in statistical physics, these problems are sampling from the Boltzmann distribution and estimating the partition function. In this talk, we give an overview of sampling and counting complexity, then we will focus on the most powerful approach to sampling, the Markov chain Monte Carlo method.

Suppose we take a large permutation that is chosen uniformly at random and conditioned to satisfy some restriction. What does this permutation look like? The answer depends on the choice of restriction and how one decides to scale the permutation. We introduce a few scaling limits that prove useful in answering this type of question for a variety of restrictions, especially in the case of pattern-avoiding permutations. We will explore what various scaling limits say about these objects and some associated statistics (like the number of fixed points of the permutation)

The six-vertex model is an exactly solvable model in statistical mechanics that has been widely studied by both physicists and combinatorialists for its many lovely properties.

In this talk in two parts, we first describe joint work with Daoji Huang [2] giving a bijection between alternating sign matrices (a combinatorial manifestation of six-vertex configurations) and totally symmetric self-complementary plane partitions in the reduced, 1432-avoiding case. Finding such a bijection in full generality has been an open problem for nearly 40 years; it will be interesting to see whether this new sub-bijection may lead to further (positive or negative) results on a full bijection.

We then introduce a symmetrized version of the six-vertex model that adapts nicely from the square lattice to arbitrary 4-regular graphs embedded in a disk. By modifying certain vertex configurations, we transform these to nearly planar bipartite graphs that have regions corresponding to dimer covers of hexagonal lattices. Our underlying motivation and main result is a bijection between equivalence classes of these graphs and 4-row tableaux in such a way that promotion corresponds to rotation, yielding a web basis for $S{L}_4$. This is joint work with Christian Gaetz, Oliver Pechenik, Stephan Pfannerer, and Joshua Swanson [1].

Turán-type extremal graph theory has been generalized in many directions. In this talk I survey the extremal theories of vertex- and edge-ordered graphs. In the vertex-ordered case the vertices of the host graph are linearly ordered and we only forbid a subgraph with a specified vertex order. As in the classical extremal graph theory, we are still looking for the maximal number of edges in a host graph on $n$ vertices avoiding the forbidden subgraph. The analogous extremal theory for edge ordered graphs was introduced recently in a paper of Gerbner, Methuku, Nagy, Pálvölgyi, T., Vizer (2023). In contrast, the vertex ordered theory has a much richer history going back to related extremal matrix problems studied by Füredi and Hajnal in 1992.

Both theories are rich in specific results: the extremal functions of some small forbidden ordered graphs. Some of these results found applications in combinatorial geometry. Other specific forbidden patterns lead to interesting open problems.

Another direction is to find analogues of general results from classical extremal graph theory. The analogues of the Erdős-Stone-Simonovits theorem has been found in both theories: the key is to find the “correct” version of the chromatic number that applies. For vertex-ordered graphs, this is the simple notion of interval chromatic number, for edge-ordered graphs, however, the corresponding notion is surprisingly rich.

In the classical (unordered) theory we have a very simple dichotomy: forests have linear extremal functions, while other graphs have far-from-linear extremal functions. The search for the analogue of this simple observation yielded several nice results, conjectures and open problems about vertex- and edge-ordered graphs.

An affine permutation of size $n$ is a bijection $\pi :\mathbb{Z}\to \mathbb{Z}$ satisfying certain properties, including that $\pi (i+n)=\pi (i)+n$ for all $i$. The affine permutations of size $n$ have been much studied as a Coxeter group, but our perspective is pattern avoidance. To have a finite set to count, we can require also that for each $i$; such $\pi$ we call a bounded affine permutation. We give the asymptotic number of bounded affine permutations of size $n$ that avoid $k\mathrm{\dots }1$; in particular, they have the same growth rate as the ordinary permutations avoiding $k\mathrm{\dots }1$. We also show several results about affine permutation classes with the property that every element is a shift of the infinite direct sum of an ordinary permutation, from which we obtain exact enumerations for several affine permutation classes. This talk covers joint work with Neal Madras, published in 2021 in Discrete Math. Theor. Comput. Sci. and in Ann. Comb. Our work, especially the boundedness condition, is motivated by the fruitful concept of periodic boundary conditions in statistical physics.

In the world of combinatorics, there are numerous sets of objects that are in a one-to-one correspondence with sets of permutations possessing specific properties, commonly characterized by pattern avoidance. This talk will delve into the TileScope algorithm and demonstrate its usefulness in comprehending permutation sets avoiding a finite list of patterns. Additionally, we will examine the algorithm’s output, including polynomial counting formulas, systems of equations, uniform random generation, and more. Finally, we will highlight the algorithm’s ability to discover bijections automatically, examine the atomicity of permutation classes, and preview planned future advancements. Visit www.permpal.com to see successful applications of the algorithm in action.

An inversion sequence of length $n$ is an integer sequence $e=e_1\mathrm{\cdots }{e}_n$ such that for each $0\le i\le n$. We use $I_n$ to denote the set of inversion sequences of length $n$. Any word $\tau$ of length $k$ over the alphabet $[k]:=\{0,1,\mathrm{\cdots },k-1\}$ is called a pattern. For a given pattern $\tau$, we use $I_n(\tau )$ to denote the set of all $\tau$-avoiding inversion sequences of length $n$.

Pattern-avoiding inversion sequences were systematically studied first by Mansour and Shattuck [2] for the patterns of length three with non-repeating letters and by Corteel et al. [1] for repeating and non-repeating letters. Since then, researchers have obtained several interesting results for these combinatorial objects.

We provide an algorithmic approach based on generating trees for enumerating the pattern-avoiding inversion sequences. First, by using this algorithmic approach, we determine the generating trees for many pattern classes such as $I_n(100),I_n(011,201),I_n(021,0112),\mathrm{\cdots }$. Then we obtain enumerating formulas for them through generating functions and the kernel method.

G. Yıldırım was partially supported by TUBITAK-Ardeb 120F352.

We conjecture the $\mathrm{Destop}$-Wilf equivalence classes and $(\mathrm{Destop},\mathrm{Desbot})$-Wilf equivalence classes of permutation patterns of length 4. Specifically, we conjecture that the nontrivial (i.e. non-singleton) $\mathrm{Destop}$-Wilf equivalence classes in $S_4$ are $\{1243,3412\}$, $\{1423,2413\}$, $\{2143,3421\}$, $\{2314,3124\}$, $\{2431,3142,3241,4132\}$, and the only nontrivial $(\mathrm{Destop},\mathrm{Desbot})$-Wilf equivalence class in $S_4$ is $\{3142,3241,4132\}$. This has been verified for avoiders of size up to 10.

The conjectures in this note concern the distribution of some descent-related statistics on some pattern-avoiding permutation classes.

For basic definitions regarding patterns in permutations, we refer to Bevan [3]. We will need the following additional definitions, the first of which refines Wilf-equivalence, and the second defines additional descent-related statistics.

It is straightforward to show that patterns $132$ and $231$ are both $\mathrm{Des}$-Wilf-equivalent and $\mathrm{Destop}$-Wilf equivalent, but not $(\mathrm{Des},\mathrm{Destop})$-Wilf equivalent. Indeed, define maps $\varphi ,\psi :\mathrm{Av}(132)\to \mathrm{Av}(231)$ as follows. Given a nonempty permutation $\sigma \in \mathrm{Av}(132)$, we can write $\sigma =231[{\sigma }^{\prime },1,{\sigma }^{\prime \prime }]$ for some ${\sigma }^{\prime },{\sigma }^{\prime \prime }\in \mathrm{Av}(132)$. Then let

and $\varphi (\sigma )=\psi (\sigma )=\sigma$ if ${\sigma }^{\prime }=\mathrm{\varnothing }$ or ${\sigma }^{\prime \prime }=\mathrm{\varnothing }$ or $\sigma =\mathrm{\varnothing }$. Then

West [8], Stankova [7], and Bóna [5] together established the Wilf-equivalence classes of permutation patterns of length 4. Later, some of the Wilf-equivalences were shown to have the same distribution of various permutation statistics. For example, Bloom [4] showed that patterns $3142$ and $4132$ are $\mathrm{Des}$-Wilf-equivalent.

The principal motivation for our conjectures comes from the following. A Dumont permutation of the first kind is a permutation $\sigma$ of an even length $2n$ such that $\mathrm{Destop}(\sigma )=\{2,4,6,\mathrm{\dots },2n\}$. Burstein and Jones [6] and Archer and Lauderdale [2] together conjectured Wilf-equivalences of patterns of length 4 on Dumont permutations of the first kind. We generalize this by claiming that those are exactly the nontrivial $\mathrm{Destop}$-Wilf equivalences for patterns of length 4 on all permutations.

Each of the remaining 12 patterns of length 4 is in a $\mathrm{Destop}$-Wilf-equivalence class by itself. For some of the above patterns, we have an even stronger conjecture.

It is easy to see by comparing the descent tops and descent bottoms of the patterns themselves that this is the only nontrivial $(\mathrm{Destop},\mathrm{Desbot})$-Wilf equivalence class for patterns of length 4.

Conjecture 5 can be restated by partitioning the set of all values in each permutation $\sigma \in S_n$ into four mutually disjoint parts.

• $\mathrm{■}$

  $\mathrm{Desruntop}(\sigma )=\mathrm{Destop}(\sigma )\setminus \mathrm{Desbot}(\sigma )$, the set of descent run tops of $\sigma$,

• $\mathrm{■}$

  $\mathrm{Desrunbot}(\sigma )=\mathrm{Desbot}(\sigma )\setminus \mathrm{Destop}(\sigma )$, the set of descent run bottoms of $\sigma$,

• $\mathrm{■}$

  $\mathrm{Desrunmid}(\sigma )=\mathrm{Destop}(\sigma )\cap \mathrm{Desbot}(\sigma )$, the set of descent run middles of $\sigma$,

• $\mathrm{■}$

  $\mathrm{Ascrunmid}(\sigma )=[n]\setminus (\mathrm{Destop}(\sigma )\cup \mathrm{Desbot}(\sigma ))$, the set of ascent run middles of ${\sigma }^{+}=(0,\sigma ,\mathrm{\infty })$. This includes ascent run middles of $\sigma$ together with $\sigma (1)$ if and $\sigma (n)$ if .

Both Conjectures 4 and 5 have been verified for avoiders of length $n\le 10$ with the help of Michael Albert’s PermLab [1] software.

I would like to bring attention to a particular mesh pattern. It is of length 3 and enumerating the permutations avoiding it is an open problem. Moreover, this pattern shares some features with the Hertzsprung patterns, yet it does not fall into that category.

Are there nontrivial mesh-patterns $p$ other than the Hertzsprung patterns for which there is a rational function $R(x)$ such that

It appears that the answer is yes.

This conjecture is based on computing the numbers $|{𝒮}_n(p)|$ for $n\le 14$:

At the time of writing this sequence is not in the OEIS.

In 2000, Klazar introduced a natural notion of pattern containment/avoidance for set partitions [1, 2]. Let $(A,B)$ be one of the following pairs of phrases:

• $\mathrm{■}$

  (set partition, set partition);

• $\mathrm{■}$

  (set partition, noncrossing partition);

• $\mathrm{■}$

  (set partition, nonnesting partition);

• $\mathrm{■}$

  (noncrossing partition, noncrossing partition);

• $\mathrm{■}$

  (nonnesting partition, nonnesting partition).

For each positive integer $k$, what is the smallest size of an $A$ that contains all $B$’s of size $k$ as patterns?

Let $D=(V,\overrightarrow{E})$ be (finite or infinite) directed graph. An independent vertex subset $A\subset V$ is a quasi-kernel (also known as semi-kernel) iff for each point $v$ there is a path of length at most $2$ from some point of $A$ to $v.$ Similarly, the independent vertex subset $B\subset V$ is a quasi-sink, iff for each point $v$ there is a path of length at most $2$ from $v$ to some point of $A$.

It is a well-known fact, that every finite (table-tennis) tournament has a (single-point) quasi-kernel (quasi-sink). In 1973 the following nice generalization was proved:

In 1976 the following conjecture was stated:

Theorem 1 does not hold in case of infinite directed graphs: for example if $Z$ denotes the directed graph of all integers where each edge is directed “upwards”, clearly there is nor quasi-kernel neither quasi-sink. However its vertex set can be easily partitioned into two subsets, such that one spanned sub-tournament contains a quasi-kernel, while the other one contains a quasi-sink.

Suppose that we are given a sequence of $n$ numbers, which we want to sort into ascending order by using the following iterative procedure: in each round, we partition the current sequence arbitrarily into disjoint blocks of entries in consecutive positions, not necessarily of the same length, and then in a single step we reverse the order of entries within each block. What is the smallest number of rounds needed to sort any input of length $n$? Equivalently: what is the smallest number $K(n)$ such that any permutation of length $n$ can be obtained by composing $K(n)$ layered permutations? A counting argument shows that $\mathrm{\Omega }(\log n)$ rounds are sometimes needed, and I can show that $O({\log }^{2}n)$ rounds suffice, so the problem is to close this gap.

Let a line graph L be given whose vertices are colored by black and white. Black vertices can be pressed. Pressing a black vertex has an effect that the black vertex is deleted, the neighbors of the black vertex change color and become neighbors (when there are two neighbors). A successful press- ing sequence of L is a permutation of its vertices such that the vertices can be pressed in that order and the result is the empty graph (that is, the last step must be pressing the remaining single black vertex). The open question is the computational complexity of counting the success- ful pressing sequences of a black-and-white line graph. That is, is there a polynomial running time algorithm to compute this number or is the problem #P-complete? It is also an interesting problem to prove rapid mixing of an irreducible Markov chain on successful pressing sequences, see Bixby et al. (that paper also tells the motivation of the problem, which is actually a genome rearrangement problem).

The longest increasing subsequence problem for permutations can be rephrased as the longest 21-avoiding subsequence. This leads us to generalize the problem to the longest $\tau$-avoiding subsequence for any given pattern $\tau$ [1, 2].

Hammersley’s interacting particle process on the unit interval [0,1] corresponds to the longest 21-avoiding subsequence. This particle process is in KPZ universality class. It provides an efficient algorithm to numerically understand the distributional properties of the longest 21-avoiding subsequence problem under the uniform measure(21-case is solved theoretically).

Can we find particle processes corresponding to the longest $\tau$-avoiding subsequence for a given pattern $\tau$? Specifically for patterns of length 3 except 321, which is known [3].

A temporal graph $𝒢$ is a pair $(G,\lambda )$, where $G=(V,E)$ is a simple undirected graph and $\lambda$ is a function that assigns to every edge $e$ of $G$ a finite non-empty set of natural numbers. The temporal graph $𝒢$ is simple if (1) every edge of $G$ is assigned exactly one time label, i.e., $|\lambda (e)|=1$ for every $e\in E$; and (2) no two edges get assigned the same time label. Without loss of generality, we will assume that if $𝒢$ is simple, then $\lambda$ is a bijection between $E$ and $\{1,2,\mathrm{\dots },|E|\}$. For this problem we focus only on simple temporal graphs.

A temporal $(u,v)$-path or a temporal path from $u$ to $v$ in $𝒢$ is a path $u=u_0,u_1,\mathrm{\dots },u_{\mathrm{\ell }}=v$ in $G$ such that ${\lambda }_1\le {\lambda }_2\le \mathrm{\cdots }\le {\lambda }_{\mathrm{\ell }}$, where ${\lambda }_i\in \lambda (u_{i-1}{u}_i)$.

The temporal graph $𝒢$ is temporally connected if each vertex can reach every other vertex by a temporal path. A temporal graph ${𝒢}^{\prime }=(G^{\prime },{\lambda }^{\prime })$ is a temporal subgraph of $𝒢$ if $G^{\prime }$ is a subgraph of $G$ and ${\lambda }^{\prime }$ is the restriction of $\lambda$ to the edges of $G^{\prime }$. Furthermore, if $V(G^{\prime })=V(G)$ and ${𝒢}^{\prime }$ is temporally connected, then ${𝒢}^{\prime }$ is called a temporal spanner of $𝒢$.

It is known that any temporal clique on $n$ vertices has a temporal spanner with $O(n\log n)$ edges [1]. Whether this bound is order optimal or not is open.