Discrete Mathematics & Theoretical Computer Science |

This section seeks high quality research articles in all aspects of combinatorics, including enumerative combinatorics, probabilistic combinatorics, extremal combinatorics, algebraic combinatorics, additive combinatorics, bijections and mappings to enumeration, structural and enumerative properties of combinatorial objects, ordered sets, posets, quasi-orderings, combinatorial structures with geometric properties, combinatorial geometry, combinatorial objects in statistical physics, positional games, power series and generating functions.

Editors: Olivier Bernardi ; Michael Drmota ; Sergi Elizalde ; Stefan Felsner ; Kolja Knauer ; Matjaz Konvalinka ; Christian Krattenthaler ; Milos Stojakovic

The exponential recursive trees model several kinds of networks. At each step of growing of these trees, each node independently attracts a new node with probability p, or fails to do with probability 1 − p. Here, we investigate the number of protected nodes, total path length of protected nodes, and a mean study of the protected node profile of such trees.

Symmetric edge polytopes are lattice polytopes associated with finite simplegraphs that are of interest in both theory and applications. We investigate thefacet structure of symmetric edge polytopes for various models of randomgraphs. For an Erdős-Renyi random graph, we identify a thresholdprobability at which with high probability the symmetric edge polytope sharesmany facet-supporting hyperplanes with that of a complete graph. We alsoinvestigate the relationship between the average local clustering, also knownas the Watts-Strogatz clustering coefficient, and the number of facets forgraphs with either a fixed number of edges or a fixed degree sequence. We usewell-known Markov Chain Monte Carlo sampling methods to generate empiricalevidence that for a fixed degree sequence, higher average local clustering in aconnected graph corresponds to higher facet numbers in the associated symmetricedge polytope.

We study the enumeration of inversion sequences that avoid the pattern 021 and another pattern of length four. We determine the generating trees for all possible pattern pairs and compute the corresponding generating functions. We introduce the concept of dregular generating trees and conjecture that for any 021-avoiding pattern τ , the generating tree T ({021, τ }) is d-regular for some integer d.

The bivariate chromatic polynomial $\chi_G(x,y)$ of a graph $G = (V, E)$,introduced by Dohmen-Pönitz-Tittmann (2003), counts all $x$-colorings of$G$ such that adjacent vertices get different colors if they are $\le y$. Weextend this notion to mixed graphs, which have both directed and undirectededges. Our main result is a decomposition formula which expresses $\chi_G(x,y)$as a sum of bivariate order polynomials (Beck-Farahmand-Karunaratne-Zuniga Ruiz2020), and a combinatorial reciprocity theorem for $\chi_G(x,y)$.

The analysis of strings of $n$ random variables with geometric distributionhas recently attracted renewed interest: Archibald et al. consider the numberof distinct adjacent pairs in geometrically distributed words. They obtain theasymptotic ($n\rightarrow\infty$) mean of this number in the cases of differentand identical pairs. In this paper we are interested in all asymptotic momentsin the identical case, in the asymptotic variance in the different case and inthe asymptotic distribution in both cases. We use two approaches: the firstone, the probabilistic approach, leads to variances in both cases and to someconjectures on all moments in the identical case and on the distribution inboth cases. The second approach, the combinatorial one, relies on multivariatepattern matching techniques, yielding exact formulas for first and secondmoments. We use such tools as Mellin transforms, Analytic Combinatorics, MarkovChains.

The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained bychanging each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is anonempty word of the form $x\, \overline{x}$. In this paper, we study infinitebinary words that do not contain arbitrarily large antisquares. For example, weshow that the repetition threshold for the language of infinite binary wordscontaining exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also studyrepetition thresholds for related classes, where "two" in the previous sentenceis replaced by a larger number. We say a binary word is $\textit{good}$ if the only antisquares it containsare $01$ and $10$. We characterize the minimal antisquares, that is, thosewords that are antisquares but all proper factors are good. We determine thegrowth rate of the number of good words of length $n$ and determine therepetition threshold between polynomial and exponential growth for the numberof good words.

We obtain an explicit formula for the variance of the number of $k$-peaks ina uniformly random permutation. This is then used to obtain an asymptoticformula for the variance of the length of longest $k$-alternating subsequencein random permutations. Also a central limit is proved for the latterstatistic.

Recently geometric hypergraphs that can be defined by intersections ofpseudohalfplanes with a finite point set were defined in a purely combinatorialway. This led to extensions of earlier results about points and halfplanes topseudohalfplanes, including polychromatic colorings and discrete Helly-typetheorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convexsets of such pseudohalfplane hypergraphs. In this context we prove severalresults corresponding to classical results about convexity, namely Helly'sTheorem, Carathéodory's Theorem, Kirchberger's Theorem, Separation Theorem,Radon's Theorem and the Cup-Cap Theorem. These results imply the respectiveresults about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using orientedmatroids and topological affine planes (TAPs) but our approach is differentfrom both of them. Compared to oriented matroids, our theory is based on alinear ordering of the vertex set which makes our definitions and proofs quitedifferent and perhaps more elementary. Compared to TAPs, which are continuousobjects, our proofs are purely combinatorial and again quite different inflavor. Altogether, we believe that our new approach can further ourunderstanding of these fundamental convexity results.

In this paper, we study a variant of graph domination known as $(t, r)$broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretourin 2015. In this variant, each broadcast provides $t-d$ reception to eachvertex a distance $d < t$ from the broadcast. If $d \ge t$ then no reception isprovided. A vertex is considered dominated if it receives $r$ total receptionfrom all broadcasts. Our main results provide some upper and lower bounds onthe density of a $(t, r)$ dominating pattern of an infinite grid, as well asmethods of computing them. Also, when $r \ge 2$ we describe a family ofcounterexamples to a generalization of Vizing's Conjecture to $(t,r)$ broadcastdomination.

In this paper we first study $k \times n$ Youden rectangles of small orders.We have enumerated all Youden rectangles for a range of small parameter values,excluding the almost square cases where $k = n-1$, in a large scale computersearch. In particular, we verify the previous counts for $(n,k) = (7,3),(7,4)$, and extend this to the cases $(11,5), (11,6), (13,4)$ and $(21,5)$. Forsmall parameter values where no Youden rectangles exist, we also enumeraterectangles where the number of symbols common to two columns is always one oftwo possible values, differing by 1, which we call \emph{near Youdenrectangles}. For all the designs we generate, we calculate the order of theautotopism group and investigate to which degree a certain transformation canyield other row-column designs, namely double arrays, triple arrays and sesquiarrays. Finally, we also investigate certain Latin rectangles with threepossible pairwise intersection sizes for the columns and demonstrate that thesecan give rise to triple and sesqui arrays which cannot be obtained from Youdenrectangles, using the transformation mentioned above.

The following problem has been known since the 80's. Let $\Gamma$ be anAbelian group of order $m$ (denoted $|\Gamma|=m$), and let $t$ and $m_i$, $1\leq i \leq t$, be positive integers such that $\sum_{i=1}^t m_i=m-1$.Determine when $\Gamma^*=\Gamma\setminus\{0\}$, the set of non-zero elements of$\Gamma$, can be partitioned into disjoint subsets $S_i$, $1 \leq i \leq t$,such that $|S_i|=m_i$ and $\sum_{s\in S_i}s=0$ for every $i$, $1 \leq i \leqt$. It is easy to check that $m_i\geq 2$ (for every $i$, $1 \leq i \leq t$) and$|I(\Gamma)|\neq 1$ are necessary conditions for the existence of suchpartitions, where $I(\Gamma)$ is the set of involutions of $\Gamma$. It wasproved that the condition $m_i\geq 2$ is sufficient if and only if$|I(\Gamma)|\in\{0,3\}$. For other groups (i.e., for which $|I(\Gamma)|\neq 3$and $|I(\Gamma)|>1$), only the case of any group $\Gamma$ with$\Gamma\cong(Z_2)^n$ for some positive integer $n$ has been analyzed completelyso far, and it was shown independently by several authors that $m_i\geq 3$ issufficient in this case. Moreover, recently Cichacz and Tuza proved that, if$|\Gamma|$ is large enough and $|I(\Gamma)|>1$, then $m_i\geq 4$ is sufficient.In this paper we generalize this result for every Abelian group of order $2^n$.Namely, we show that the condition $m_i\geq 3$ is sufficient for $\Gamma$ suchthat $|I(\Gamma)|>1$ and $|\Gamma|=2^n$, for every positive integer $n$. Wealso present some applications of this result to graph magic- […]

In 1946, Erdős posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $n$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erdős' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $\mathbb{R}^3$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $\mathbb{R}^2$and $\mathbb{R}^3$.

We define and study positional marked patterns, permutations $\tau$ where oneof elements in $\tau$ is underlined. Given a permutation $\sigma$, we say that$\sigma$ has a $\tau$-match at position $i$ if $\tau$ occurs in $\sigma$ insuch a way that $\sigma_i$ plays the role of the underlined element in theoccurrence. We let $pmp_\tau(\sigma)$ denote the number of positions $i$ which$\sigma$ has a $\tau$-match. This defines a new class of statistics onpermutations, where we study such statistics and prove a number of results. Inparticular, we prove that two positional marked patterns $1\underline{2}3$ and$1\underline{3}2$ give rise to two statistics that have the same distribution.The equidistibution phenomenon also occurs in other several collections ofpatterns like $\left \{1\underline{2}3 , 1\underline{3}2 \right \}$, and $\left\{ 1\underline234, 1\underline243, \underline2134, \underline2 1 4 3 \right\}$, as well as two positional marked patterns of any length $n$: $\left \{1\underline 2\tau , \underline 21\tau \right \}$.

The number of down-steps between pairs of up-steps in $k_t$-Dyck paths, ageneralization of Dyck paths consisting of steps $\{(1, k), (1, -1)\}$ suchthat the path stays (weakly) above the line $y=-t$, is studied. Results areproved bijectively and by means of generating functions, and lead to severalinteresting identities as well as links to other combinatorial structures. Inparticular, there is a connection between $k_t$-Dyck paths and perforationpatterns for punctured convolutional codes (binary matrices) used in codingtheory. Surprisingly, upon restriction to usual Dyck paths this yields a newcombinatorial interpretation of Catalan numbers.

Let $P$ be a set of $n\geq 3$ points in general position in the plane. Theedge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all theclosed straight line segments with endpoints in $P$, two of which are adjacentin $D(P)$ if and only if they are disjoint. We show that the connectivity of$D(P)$ is at least$\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$,and that this bound is tight for each $n\geq 3$.

Motivated by the study of pattern avoidance in the context of permutationsand ordered partitions, we consider the enumeration of weak-ordering chainsobtained as leaves of certain restricted rooted trees. A tree of order $n$ isgenerated by inserting a new variable into each node at every step. A nodebecomes a leaf either after $n$ steps or when a certain stopping condition ismet. In this paper we focus on conditions of size 2 ($x=y$, $x

## Efficient recurrence for the enumeration of permutations with fixed pinnacle set

Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative studyof pinnacle sets of permutations has attracted a fair amount of attentionrecently. In this article, we provide a recurrence that can be used to computeefficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with agiven pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$of size $k$. A symbolic expression can also be computed in this way forpinnacle sets of fixed size. A weighted sum $q_n(P)$ of $|\mathfrak{S}_n(P)|$proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simpleform, and a conjectural form is given recently by Flaque, Novelli and Thibon(2021+). We settle the problem by providing and proving an alternative form of$q_n(P)$, which has a strong combinatorial flavor. We also study admissibleorderings of a given pinnacle set, first considered by Rusu (2020) andcharacterized by Rusu and Tenner (2021), and we give an efficient algorithm fortheir counting.

## Further enumeration results concerning a recent equivalence of restricted inversion sequences

Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.

## Antipowers in Uniform Morphic Words and the Fibonacci Word

Fici, Restivo, Silva, and Zamboni define a $k$-antipower to be a wordcomposed of $k$ pairwise distinct, concatenated words of equal length. Bergerand Defant conjecture that for any sufficiently well-behaved aperiodic morphicword $w$, there exists a constant $c$ such that for any $k$ and any index $i$,a $k$-antipower with block length at most $ck$ starts at the $i$th position of$w$. They prove their conjecture in the case of binary words, and we extendtheir result to alphabets of arbitrary finite size and characterize those wordsfor which the result does not hold. We also prove their conjecture in thespecific case of the Fibonacci word.

## Certificate complexity and symmetry of nested canalizing functions

Boolean nested canalizing functions (NCFs) have important applications inmolecular regulatory networks, engineering and computer science. In this paper,we study their certificate complexity. For both Boolean values $b\in\{0,1\}$,we obtain a formula for $b$-certificate complexity and consequently, we developa direct proof of the certificate complexity formula of an NCF. Symmetry isanother interesting property of Boolean functions and we significantly simplifythe proofs of some recent theorems about partial symmetry of NCFs. We alsodescribe the algebraic normal form of $s$-symmetric NCFs. We obtain the generalformula of the cardinality of the set of $n$-variable $s$-symmetric BooleanNCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetricBoolean NCFs.

## On the density of sets of the Euclidean plane avoiding distance 1

A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forallx,y \in A, \left\| x-y \right\|_2 \neq 1.$ In this paper we study the number$m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurablesets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbbR^2)$ represents the highest proportion of the plane that can be filled by aset avoiding distance 1. This parameter is related to the fractional chromaticnumber $\chi_f(\mathbb R^2)$ of the plane. We establish that $m_1(\mathbb R^2) \leq 0.25647$ and $\chi_f(\mathbb R^2)\geq 3.8991$.

## On the VC-dimension of half-spaces with respect to convex sets

A family S of convex sets in the plane defines a hypergraph H = (S, E) asfollows. Every subfamily S' of S defines a hyperedge of H if and only if thereexists a halfspace h that fully contains S' , and no other set of S is fullycontained in h. In this case, we say that h realizes S'. We say a set S isshattered, if all its subsets are realized. The VC-dimension of a hypergraph His the size of the largest shattered set. We show that the VC-dimension forpairwise disjoint convex sets in the plane is bounded by 3, and this is tight.In contrast, we show the VC-dimension of convex sets in the plane (notnecessarily disjoint) is unbounded. We provide a quadratic lower bound in thenumber of pairs of intersecting sets in a shattered family of convex sets inthe plane. We also show that the VC-dimension is unbounded for pairwisedisjoint convex sets in R^d , for d > 2. We focus on, possibly intersecting,segments in the plane and determine that the VC-dimension is always at most 5.And this is tight, as we construct a set of five segments that can beshattered. We give two exemplary applications. One for a geometric set coverproblem and one for a range-query data structure problem, to motivate ourfindings.

## A birational lifting of the Stanley-Thomas word on products of two chains

The dynamics of certain combinatorial actions and their liftings to actionsat the piecewise-linear and birational level have been studied lately with aneye towards questions of periodicity, orbit structure, and invariants. One keyproperty enjoyed by the rowmotion operator on certain finite partially-orderedsets is homomesy, where the average value of a statistic is the same for allorbits. To prove refined versions of homomesy in the product of two chainposets, J. Propp and the second author used an equivariant bijection discovered(less formally) by R. Stanley and H. Thomas. We explore the lifting of this "Stanley--Thomas word" to thepiecewise-linear, birational, and noncommutative realms. Although the map is nolonger a bijection, so cannot be used to prove periodicity directly, it stillgives enough information to prove the homomesy at the piecewise-linear andbirational levels (a result previously shown by D. Grinberg, S. Hopkins, and S.Okada). Even at the noncommutative level, the Stanley--Thomas word of a posetlabeling rotates cyclically with the lifting of antichain rowmotion. Along theway we give some formulas for noncommutative antichain rowmotion that we hopewill be first steps towards proving the conjectured periodicity at this level.

## The Elser nuclei sum revisited

Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$be the set of edges of $\Gamma$. We call a subset $F$ of $E$ pandemic if eachedge of $\Gamma$ has at least one endpoint that can be connected to $v$ by an$F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed thatthe sum of $\left(-1\right)^{\left| F\right|}$ over all pandemic subsets $F$ of$E$ is $0$ if $E\neq \varnothing$. We give a simple proof of this result via asign-reversing involution, and discuss variants, generalizations andrefinements, revealing connections to abstract convexity (the notion of anantimatroid) and discrete Morse theory.

## Row bounds needed to justifiably express flagged Schur functions with Gessel-Viennot determinants

Let $\lambda$ be a partition with no more than $n$ parts. Let $\beta$ be aweakly increasing $n$-tuple with entries from $\{ 1, ... , n \}$. The flaggedSchur function in the variables $x_1, ... , x_n$ that is indexed by $\lambda$and $\beta$ has been defined to be the sum of the content weight monomials forthe semistandard Young tableaux of shape $\lambda$ whose values are row-wisebounded by the entries of $\beta$. Gessel and Viennot gave a determinantexpression for the flagged Schur function indexed by $\lambda$ and $\beta$;this could be done since the pair $(\lambda, \beta)$ satisfied their"nonpermutable" condition for the sequence of terminals of an $n$-tuple oflattice paths that they used to model the tableaux. We generalize flagged Schurfunctions by dropping the requirement that $\beta$ be weakly increasing. Thenfor each $\lambda$ we give a condition on the entries of $\beta$ for the pair$(\lambda, \beta)$ to be nonpermutable that is both necessary and sufficient.When the parts of $\lambda$ are not distinct there will be multiple row bound$n$-tuples $\beta$ that will produce the same set of tableaux. We accordinglygroup the bounding $\beta$ into equivalence classes and identify the mostefficient $\beta$ in each class for the determinant computation. We recentlyshowed that many other sets of objects that are indexed by $n$ and $\lambda$are enumerated by the number of these efficient $n$-tuples. We called thesecounts "parabolic Catalan numbers". It is noted that the $GL(n)$ […]

## Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

We give three applications of a recently-proven "Decomposition Lemma," whichallows one to count preimages of certain sets of permutations under West'sstack-sorting map $s$. We first enumerate the permutation class$s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new exampleof an unbalanced Wilf equivalence. This result is equivalent to the enumerationof permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubblesort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$,$s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$,and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ arecounted by the so-called "Boolean-Catalan numbers," settling a conjecture ofthe current author and another conjecture of Hossain. This completes theenumerations of all sets of the form$s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for$\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set$\{321\}$. We also find an explicit formula for$|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents.This allows us to prove a conjectured identity involving Catalan numbers andorder ideals in Young's lattice.

## Exponential multivalued forbidden configurations

The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum numberof unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is arow and column permutation of $F$, has been widely studied in extremal settheory. Recently, this function was extended to $r$-matrices, whose entries liein $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden numberis less well-studied. In this paper, we provide exact bounds for many$(0,1)$-matrices $F$, including all $2$-rowed matrices when $r > 3$. We alsoprove a stability result for the $2\times 2$ identity matrix. Along the way, weexpose some interesting qualitative differences between the cases $r=2$, $r =3$, and $r > 3$.

## Determining Genus From Sandpile Torsor Algorithms

We provide a pair of ribbon graphs that have the same rotor routing andBernardi sandpile torsors, but different topological genus. This resolves aquestion posed by M. Chan [Cha]. We also show that if we are given a graph, butnot its ribbon structure, along with the rotor routing sandpile torsors, we areable to determine the ribbon graph's genus.

## On an alternative sequence comparison statistic of Steele

The purpose of this paper is to study a statistic that is used to compare thesimilarity between two strings, which is first introduced by Michael Steele in1982. It was proposed as an alternative to the length of the longest commonsubsequences, for which the variance problem is still open. Our results includemoment asymptotics and distributional asymptotics for Steele's statistic and avariation of it in random words and random permutations.

## Inversion sequences avoiding pairs of patterns

The enumeration of inversion sequences avoiding a single pattern wasinitiated by Corteel--Martinez--Savage--Weselcouch and Mansour--Shattuckindependently. Their work has sparked various investigations of generalizedpatterns in inversion sequences, including patterns of relation triples byMartinez and Savage, consecutive patterns by Auli and Elizalde, and vincularpatterns by Lin and Yan. In this paper, we carried out the systematic study ofinversion sequences avoiding two patterns of length $3$. Our enumerativeresults establish further connections to the OEIS sequences and some classicalcombinatorial objects, such as restricted permutations, weighted ordered treesand set partitions. Since patterns of relation triples are some specialmultiple patterns of length $3$, our results complement the work by Martinezand Savage. In particular, one of their conjectures regarding the enumerationof $(021,120)$-avoiding inversion sequences is solved.

## Dissecting a square into congruent polygons

We study the dissection of a square into congruent convex polygons. Yuan\emph{et al.} [Dissecting the square into five congruent parts, Discrete Math.\textbf{339} (2016) 288-298] asked whether, if the number of tiles is a primenumber $\geq 3$, it is true that the tile must be a rectangle. We conjecture that the same conclusion still holds even if the number oftiles is an odd number $\geq 3$. Our conjecture has been confirmed for triangles in earlier works. We provethat the conjecture holds if either the tile is a convex $q$-gon with $q\geq 6$or it is a right-angle trapezoid.

## On the heapability of finite partial orders

We investigate the partitioning of partial orders into a minimal number ofheapable subsets. We prove a characterization result reminiscent of the proofof Dilworth's theorem, which yields as a byproduct a flow-based algorithm forcomputing such a minimal decomposition. On the other hand, in the particularcase of sets and sequences of intervals we prove that this minimaldecomposition can be computed by a simple greedy-type algorithm. The paper endswith a couple of open problems related to the analog of the Ulam-Hammersleyproblem for decompositions of sets and sequences of random intervals intoheapable sets.

## Complementary symmetric Rote sequences: the critical exponent and the recurrence function

We determine the critical exponent and the recurrence function ofcomplementary symmetric Rote sequences. The formulae are expressed in terms ofthe continued fraction expansions associated with the S-adic representations ofthe corresponding standard Sturmian sequences. The results are based on athorough study of return words to bispecial factors of Sturmian sequences.Using the formula for the critical exponent, we describe all complementarysymmetric Rote sequences with the critical exponent less than or equal to 3,and we show that there are uncountably many complementary symmetric Rotesequences with the critical exponent less than the critical exponent of theFibonacci sequence. Our study is motivated by a~conjecture on sequences rich inpalindromes formulated by Baranwal and Shallit. Its recent solution by Curie,Mol, and Rampersad uses two particular complementary symmetric Rote sequences.

## The 3-way flower intersection problem for Steiner triple systems

The flower at a point x in a Steiner triple system (X; B) is the set of alltriples containing x. Denote by J3F(r) the set of all integers k such thatthere exists a collection of three STS(2r+1) mutually intersecting in the sameset of k + r triples, r of them being the triples of a common flower. In this article we determine the set J3F(r) for any positive integer r = 0, 1(mod 3) (only some cases are left undecided for r = 6, 7, 9, 24), and establishthat J3F(r) = I3F(r) for r = 0, 1 (mod 3) where I3F(r) = {0, 1,...,2r(r-1)/3-8, 2r(r-1)/3-6, 2r(r-1)/3}.

## On the inducibility of small trees

The quantity that captures the asymptotic value of the maximum number ofappearances of a given topological tree (a rooted tree with no vertices ofoutdegree $1$) $S$ with $k$ leaves in an arbitrary tree with sufficiently largenumber of leaves is called the inducibility of $S$. Its precise value is knownonly for some specific families of trees, most of them exhibiting a symmetricalconfiguration. In an attempt to answer a recent question posed by Czabarka,Székely, and the second author of this article, we provide bounds for theinducibility $J(A_5)$ of the $5$-leaf binary tree $A_5$ whose branches are asingle leaf and the complete binary tree of height $2$. It was indicated beforethat $J(A_5)$ appears to be `close' to $1/4$. We can make this precise byshowing that $0.24707\ldots \leq J(A_5) \leq 0.24745\ldots$. Furthermore, wealso consider the problem of determining the inducibility of the tree $Q_4$,which is the only tree among $4$-leaf topological trees for which theinducibility is unknown.

## Proofs of Conjectures about Pattern-Avoiding Linear Extensions

After fixing a canonical ordering (or labeling) of the elements of a finiteposet, one can associate each linear extension of the poset with a permutation.Some recent papers consider specific families of posets and ask how many linearextensions give rise to permutations that avoid certain patterns. We build offof two of these papers. We first consider pattern avoidance in $k$-ary heaps,where we obtain a general result that proves a conjecture of Levin, Pudwell,Riehl, and Sandberg in a special case. We then prove some conjectures thatAnderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoidinglinear extensions of rectangular posets.

## On the centroid of increasing trees

A centroid node in a tree is a node for which the sum of the distances to allother nodes attains its minimum, or equivalently a node with the property thatnone of its branches contains more than half of the other nodes. We generalisesome known results regarding the behaviour of centroid nodes in randomrecursive trees (due to Moon) to the class of very simple increasing trees,which also includes the families of plane-oriented and $d$-ary increasingtrees. In particular, we derive limits of distributions and moments for thedepth and label of the centroid node nearest to the root, as well as for thesize of the subtree rooted at this node.

## Consecutive patterns in restricted permutations and involutions

It is well-known that the set $\mathbf I_n$ of involutions of the symmetricgroup $\mathbf S_n$ corresponds bijectively - by the Foata map $F$ - to the setof $n$-permutations that avoid the two vincular patterns $\underline{123},$$\underline{132}.$ We consider a bijection $\Gamma$ from the set $\mathbf S_n$to the set of histoires de Laguerre, namely, bicolored Motzkin paths withlabelled steps, and study its properties when restricted to $\mathbfS_n(1\underline{23},1\underline{32}).$ In particular, we show that the set$\mathbf S_n(\underline{123},{132})$ of permutations that avoids theconsecutive pattern $\underline{123}$ and the classical pattern $132$corresponds via $\Gamma$ to the set of Motzkin paths, while its image under $F$is the set of restricted involutions $\mathbf I_n(3412).$ We exploit theseresults to determine the joint distribution of the statistics des and inv over $\mathbf S_n(\underline{123},{132})$ and over $\mathbf I_n(3412).$ Moreover, we determine the distribution in these two sets of everyconsecutive pattern of length three. To this aim, we use a modified version ofthe well-known Goulden-Jacson cluster method.

## Number of orbits of Discrete Interval Exchanges

A new recursive function on discrete interval exchange transformationassociated to a composition of length $r$, and the permutation $\sigma(i) = r-i +1$ is defined. Acting on composition $c$, this recursive function countsthe number of orbits of the discrete interval exchange transformationassociated to the composition $c$. Moreover, minimal discrete intervalexchanges transformation i.e. the ones having only one orbit, are reduced tothe composition which label the root of the Raney tree. Therefore, we describea generalization of the Raney tree using our recursive function.

## $K_{1,3}$-covering red and blue points in the plane

We say that a finite set of red and blue points in the plane in generalposition can be $K_{1,3}$-covered if the set can be partitioned into subsets ofsize $4$, with $3$ points of one color and $1$ point of the other color, insuch a way that, if at each subset the fourth point is connected bystraight-line segments to the same-colored points, then the resulting set ofall segments has no crossings. We consider the following problem: Given a set$R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in generalposition, how many points of $R\cup B$ can be $K_{1,3}$-covered? and we provethe following results: (1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$,then there are point sets $R\cup B$, like $\{1,3\}$-equitable sets (i.e.,$r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered. (2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position,then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight. (3) There are arbitrarily large point sets $R\cup B$ in general position,with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered. (4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b-8)$ points of $R\cup B$can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and atleast $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute thecorresponding coverings.

## A Note on Flips in Diagonal Rectangulations

Rectangulations are partitions of a square into axis-aligned rectangles. Anumber of results provide bijections between combinatorial equivalence classesof rectangulations and families of pattern-avoiding permutations. Other resultsdeal with local changes involving a single edge of a rectangulation, referredto as flips, edge rotations, or edge pivoting. Such operations induce a graphon equivalence classes of rectangulations, related to so-called flip graphs ontriangulations and other families of geometric partitions. In this note, weconsider a family of flip operations on the equivalence classes of diagonalrectangulations, and their interpretation as transpositions in the associatedBaxter permutations, avoiding the vincular patterns { 3{14}2, 2{41}3 }. Thiscomplements results from Law and Reading (JCTA, 2012) and provides a completecharacterization of flip operations on diagonal rectangulations, in bothgeometric and combinatorial terms.

## The 26 Wilf-equivalence classes of length five quasi-consecutive patterns

We present two families of Wilf-equivalences for consecutive andquasi-consecutive vincular patterns. These give new proofs of theclassification of consecutive patterns of length $4$ and $5$. We then proveadditional equivalences to explicitly classify all quasi-consecutive patternsof length $5$ into 26 Wilf-equivalence classes.

## Summation formulas for Fox-Wright function

By means of inversion techniques and several known hypergeometric seriesidentities, summation formulas for Fox-Wright function are explored. They givesome new hypergeometric series identities when the parameters are specified.

## Convexity of tableau sets for type A Demazure characters (key polynomials), parabolic Catalan numbers

This is the first of three papers that develop structures which are countedby a "parabolic" generalization of Catalan numbers. Fix a subset R of{1,..,n-1}. Consider the ordered partitions of {1,..,n} whose block sizes aredetermined by R. These are the "inverses" of (parabolic) multipermutationswhose multiplicities are determined by R. The standard forms of the orderedpartitions are refered to as "R-permutations". The notion of 312-avoidance isextended from permutations to R-permutations. Let lambda be a partition of Nsuch that the set of column lengths in its shape is R or R union {n}. Fix anR-permutation pi. The type A Demazure character (key polynomial) in x_1, ..,x_n that is indexed by lambda and pi can be described as the sum of the weightmonomials for some of the semistandard Young tableau of shape lambda that areused to describe the Schur function indexed by lambda. Descriptions of these"Demazure" tableaux developed by the authors in earlier papers are used toprove that the set of these tableaux is convex in Z^N if and only if pi isR-312-avoiding if and only if the tableau set is the entire principal idealgenerated by the key of pi. These papers were inspired by results of Reiner andShimozono and by Postnikov and Stanley concerning coincidences between Demazurecharacters and flagged Schur functions. This convexity result is used in thenext paper to deepen those results from the level of polynomials to the levelof tableau sets. The R-parabolic Catalan number is defined […]

## Permutation complexity of images of Sturmian words by marked morphisms

We show that the permutation complexity of the image of a Sturmian word by abinary marked morphism is $n+k$ for some constant $k$ and all lengths $n$sufficiently large.

## Rowmotion and generalized toggle groups

We generalize the notion of the toggle group, as defined in [P. Cameron-D.Fon-der-Flaass '95] and further explored in [J. Striker-N. Williams '12], fromthe set of order ideals of a poset to any family of subsets of a finite set. Weprove structure theorems for certain finite generalized toggle groups, similarto the theorem of Cameron and Fon-der-Flaass in the case of order ideals. Weapply these theorems and find other results on generalized toggle groups in thefollowing settings: chains, antichains, and interval-closed sets of a poset;independent sets, vertex covers, acyclic subgraphs, and spanning subgraphs of agraph; matroids and convex geometries. We generalize rowmotion, an actionstudied on order ideals in [P. Cameron-D. Fon-der-Flaass '95] and [J.Striker-N. Williams '12], to a map we call cover-closure on closed sets of aclosure operator. We show that cover-closure is bijective if and only if theset of closed sets is isomorphic to the set of order ideals of a poset, whichimplies rowmotion is the only bijective cover-closure map.

## Non-adaptive Group Testing on Graphs

Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problemof learning a hidden graph for some especial cases, such as hamiltonian cycle,cliques, stars, and matchings. This problem is motivated by problems inchemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, weconsider a graph G and a subgraph H of G and we assume that G contains exactlyone defective subgraph isomorphic to H. The goal is to find the defectivesubgraph by testing whether an induced subgraph contains an edge of thedefective subgraph, with the minimum number of tests. We present an upper boundfor the number of tests to find the defective subgraph by using the symmetricand high probability variation of Lovász Local Lemma.

## Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials)

Fix an integer partition lambda that has no more than n parts. Let beta be aweakly increasing n-tuple with entries from {1,..,n}. The flagged Schurfunction indexed by lambda and beta is a polynomial generating function in x_1,.., x_n for certain semistandard tableaux of shape lambda. Let pi be ann-permutation. The type A Demazure character (key polynomial, Demazurepolynomial) indexed by lambda and pi is another such polynomial generatingfunction. Reiner and Shimozono and then Postnikov and Stanley studiedcoincidences between these two families of polynomials. Here their results aresharpened by the specification of unique representatives for the equivalenceclasses of indexes for both families of polynomials, extended by theconsideration of more general beta, and deepened by proving that the polynomialcoincidences also hold at the level of the underlying tableau sets. Let R bethe set of lengths of columns in the shape of lambda that are less than n.Ordered set partitions of {1,..,n} with block sizes determined by R, calledR-permutations, are used to describe the minimal length representatives for theparabolic quotient of the nth symmetric group specified by the set{1,..,n-1}\R. The notion of 312-avoidance is generalized from n-permutations tothese set partitions. The R-parabolic Catalan number is defined to be thenumber of these. Every flagged Schur function arises as a Demazure polynomial.Those Demazure polynomials are precisely indexed by the R-312-avoidingR-permutations. […]

## Periodic balanced binary triangles

A binary triangle of size $n$ is a triangle of zeroes and ones, with $n$ rows, built with the same local rule as the standard Pascal triangle modulo $2$. A binary triangle is said to be balanced if the absolute difference between the numbers of zeroes and ones that constitute this triangle is at most $1$. In this paper, the existence of balanced binary triangles of size $n$, for all positive integers $n$, is shown. This is achieved by considering periodic balanced binary triangles, that are balanced binary triangles where each row, column or diagonal is a periodic sequence.

## Binary Codes and Period-2 Orbits of Sequential Dynamical Systems

Let $[K_n,f,\pi]$ be the (global) SDS map of a sequential dynamical system(SDS) defined over the complete graph $K_n$ using the update order $\pi\in S_n$in which all vertex functions are equal to the same function $f\colon\mathbbF_2^n\to\mathbb F_2^n$. Let $\eta_n$ denote the maximum number of periodicorbits of period $2$ that an SDS map of the form $[K_n,f,\pi]$ can have. Weshow that $\eta_n$ is equal to the maximum number of codewords in a binary codeof length $n-1$ with minimum distance at least $3$. This result is significantbecause it represents the first interpretation of this fascinatingcoding-theoretic sequence other than its original definition.

## Refined Enumeration of Corners in Tree-like Tableaux

Tree-like tableaux are certain fillings of Ferrers diagrams originallyintroduced by Aval et al., which are in simple bijections with permutationtableaux coming from Postnikov's study of totally nonnegative Grassmanian andalternative tableaux introduced by Viennot. In this paper, we confirm twoconjectures of Gao et al. on the refined enumeration of non-occupied corners intree-like tableaux and symmetric tree-like tableaux via intermediate structuresof alternative tableaux, linked partitions, type $B$ alternative tableaux andtype $B$ linked partitions.

## Stammering tableaux

The PASEP (Partially Asymmetric Simple Exclusion Process) is a probabilisticmodel of moving particles, which is of great interest in combinatorics, sinceit appeared that its partition function counts some tableaux. These tableauxhave several variants such as permutations tableaux, alternative tableaux,tree- like tableaux, Dyck tableaux, etc. We introduce in this context certainexcursions in Young's lattice, that we call stammering tableaux (by analogywith oscillating tableaux, vacillating tableaux, hesitating tableaux). Somenatural bijections make a link with rook placements in a double staircase,chains of Dyck paths obtained by successive addition of ribbons, Laguerrehistories, Dyck tableaux, etc.

## Rises in forests of binary shrubs

The study of patterns in permutations associated with forests of binaryshrubs was initiated by D. Bevan et al.. In this paper, we study five differenttypes of rise statistics that can be associated with such permutations and findthe generating functions for the distribution of such rise statistics.

## Evaluations of series of the $q$-Watson, $q$-Dixon, and $q$-Whipple type

Using $q$-series identities and series rearrangement, we establish severalextensions of $q$-Watson formulas with two extra integer parameters. Then theyand Sears' transformation formula are utilized to derive some generalizationsof $q$-Dixon formulas and $q$-Whipple formulas with two extra integerparameters. As special cases of these results, many interesting evaluations ofseries of $q$-Watson,$q$-Dixon, and $q$-Whipple type are displayed.

## On universal partial words

A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is aword over $A$ such that every word in $A^n$ appears exactly once as a subword(cyclically or linearly). It is well-known and easy to prove that universalwords exist for any $A$ and $n$. In this work we initiate the systematic studyof universal partial words. These are words that in addition to the lettersfrom $A$ may contain an arbitrary number of occurrences of a special `joker'symbol $\Diamond\notin A$, which can be substituted by any symbol from $A$. Forexample, $u=0\Diamond 011100$ is a linear partial word for the binary alphabet$A=\{0,1\}$ and for $n=3$ (e.g., the first three letters of $u$ yield thesubwords $000$ and $010$). We present results on the existence andnon-existence of linear and cyclic universal partial words in differentsituations (depending on the number of $\Diamond$s and their positions),including various explicit constructions. We also provide numerous examples ofuniversal partial words that we found with the help of a computer.

## S-Restricted Compositions Revisited

An S-restricted composition of a positive integer n is an ordered partitionof n where each summand is drawn from a given subset S of positive integers.There are various problems regarding such compositions which have receivedattention in recent years. This paper is an attempt at finding a closed- formformula for the number of S-restricted compositions of n. To do so, we reducethe problem to finding solutions to corresponding so-called interpreters whichare linear homogeneous recurrence relations with constant coefficients. Then,we reduce interpreters to Diophantine equations. Such equations are not ingeneral solvable. Thus, we restrict our attention to those S-restrictedcomposition problems whose interpreters have a small number of coefficients,thereby leading to solvable Diophantine equations. The formalism developed isthen used to study the integer sequences related to some well-known cases ofthe S-restricted composition problem.

## On the shelling antimatroids of split graphs

Chordal graph shelling antimatroids have received little attention withregard to their combinatorial properties and related optimization problems, ascompared to the case of poset shelling antimatroids. Here we consider a specialcase of these antimatroids, namely the split graph shelling antimatroids. Weshow that the feasible sets of such an antimatroid relate to some posetshelling antimatroids constructed from the graph. We discuss a fewapplications, obtaining in particular a simple polynomial-time algorithm tofind a maximum weight feasible set. We also provide a simple description of thecircuits and the free sets.

## Wilf classification of triples of 4-letter patterns II

This is the second of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. This amounts to counting avoiders for 107 representative triples. The insertion encoding algorithm (INSENC) applies to many of them and some others have been previously counted. There remain 36 triples and the first paper dealt with the first 18. In this paper, we find the generating function for the last 18 triples which turns out to be algebraic in each case. Our methods are both combinatorial and analytic, including decomposi-tions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A particularly nice so-called cell decomposition is used in one of the cases (Case 238).

## Wilf classification of triples of 4-letter patterns I

This is the first of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. This amounts to counting avoiders for 107 representative triples. The insertion encoding algorithm (INSENC) applies to many of them and some others have been previously counted. Thus there remain 36 triples. In this paper, we find the generating function for the first 18 of these triples and in a second paper, we treat the other 18. The generating function turns out to be algebraic in each case. Our methods are both combinatorial and analytic, including decompositions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A bijection is used in one of the cases (Case 50).

## A class of symmetric difference-closed sets related to commuting involutions

Recent research on the combinatorics of finite sets has explored the structure of symmetric difference-closed sets, and recent research in combinatorial group theory has concerned the enumeration of commuting involutions in $S_{n}$ and $A_{n}$. In this article, we consider an interesting combination of these two subjects, by introducing classes of symmetric difference-closed sets of elements which correspond in a natural way to commuting involutions in $S_{n}$ and $A_{n}$. We consider the natural combinatorial problem of enumerating symmetric difference-closed sets consisting of subsets of sets consisting of pairwise disjoint $2$-subsets of $[n]$, and the problem of enumerating symmetric difference-closed sets consisting of elements which correspond to commuting involutions in $A_{n}$. We prove explicit combinatorial formulas for symmetric difference-closed sets of these forms, and we prove a number of conjectured properties related to such sets which had previously been discovered experimentally using the On-Line Encyclopedia of Integer Sequences.

## Postorder Preimages

Given a set $Y$ of decreasing plane trees and a permutation $\pi$, how manytrees in $Y$ have $\pi$ as their postorder? Using combinatorial and geometricconstructions, we provide a method for answering this question for certain sets$Y$ and all permutations $\pi$. We then provide applications of our results tothe study of the deterministic stack-sorting algorithm.

## Enumeration of Corners in Tree-like Tableaux

In this paper, we confirm conjectures of Laborde-Zubieta on the enumerationof corners in tree-like tableaux and in symmetric tree-like tableaux. In theprocess, we also enumerate corners in (type $B$) permutation tableaux and(symmetric) alternative tableaux. The proof is based on Corteel and Nadeau'sbijection between permutation tableaux and permutations. It allows us tointerpret the number of corners as a statistic over permutations that is easierto count. The type $B$ case uses the bijection of Corteel and Kim between type$B$ permutation tableaux and signed permutations. Moreover, we give a bijectionbetween corners and runs of size 1 in permutations, which gives an alternativeproof of the enumeration of corners. Finally, we introduce conjecturalpolynomial analogues of these enumerations, and explain the implications on thePASEP.

## Stokes posets and serpent nests

We study two different objects attached to an arbitrary quadrangulation of a regular polygon. The first one is a poset, closely related to the Stokes polytopes introduced by Baryshnikov. The second one is a set of some paths configurations inside the quadrangulation, satisfying some specific constraints. These objects provide a generalisation of the existing combinatorics of cluster algebras and nonnesting partitions of type A.

## Constructions of words rich in palindromes and pseudopalindromes

A narrow connection between infinite binary words rich in classicalpalindromes and infinite binary words rich simultaneously in palindromes andpseudopalindromes (the so-called $H$-rich words) is demonstrated. The correspondence between rich and $H$-rich words is based on the operation$S$ acting over words over the alphabet $\{0,1\}$ and defined by$S(u_0u_1u_2\ldots) = v_1v_2v_3\ldots$, where $v_i= u_{i-1} + u_i \mod 2$. The operation $S$ enables us to construct a new class of rich words and a newclass of $H$-rich words. Finally, the operation $S$ is considered on the multiliteral alphabet$\mathbb{Z}_m$ as well and applied to the generalized Thue--Morse words. As abyproduct, new binary rich and $H$-rich words are obtained by application of$S$ on the generalized Thue--Morse words over the alphabet $\mathbb{Z}_4$.

## Ramsey-type theorems for lines in 3-space

We prove geometric Ramsey-type statements on collections of lines in 3-space.These statements give guarantees on the size of a clique or an independent setin (hyper)graphs induced by incidence relations between lines, points, andreguli in 3-space. Among other things, we prove that: (1) The intersectiongraph of n lines in R^3 has a clique or independent set of size Omega(n^{1/3}).(2) Every set of n lines in R^3 has a subset of n^{1/2} lines that are allstabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no6-subset is stabbed by one line. (3) Every set of n lines in general positionin R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or asubset of Omega(n^{1/3}) lines such that no 4-subset is contained in a regulus.The proofs of these statements all follow from geometric incidence bounds --such as the Guth-Katz bound on point-line incidences in R^3 -- combined withTurán-type results on independent sets in sparse graphs and hypergraphs.Although similar Ramsey-type statements can be proved using existing genericalgebraic frameworks, the lower bounds we get are much larger than what can beobtained with these methods. The proofs directly yield polynomial-timealgorithms for finding subsets of the claimed size.

## A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups

Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.

## Statistics for 3-letter patterns with repetitions in compositions

A composition $\pi = \pi_1 \pi_2 \cdots \pi_m$ of a positive integer $n$ is an ordered collection of one or more positive integers whose sum is $n$. The number of summands, namely $m$, is called the number of parts of $\pi$. Using linear algebra, we determine formulas for generating functions that count compositions of $n$ with $m$ parts, according to the number of occurrences of the subword pattern $\tau$, and according to the sum, over all occurrences of $\tau$, of the first integers in their respective occurrences, where $\tau$ is any pattern of length three with exactly 2 distinct letters.

## On the number of vertices of each rank in phylogenetic trees and their generalizations

We find surprisingly simple formulas for the limiting probability that therank of a randomly selected vertex in a randomly selected phylogenetic tree orgeneralized phylogenetic tree is a given integer.

## The Flip Diameter of Rectangulations and Convex Subdivisions

We study the configuration space of rectangulations and convex subdivisionsof $n$ points in the plane. It is shown that a sequence of $O(n\log n)$elementary flip and rotate operations can transform any rectangulation to anyother rectangulation on the same set of $n$ points. This bound is the bestpossible for some point sets, while $\Theta(n)$ operations are sufficient andnecessary for others. Some of our bounds generalize to convex subdivisions of$n$ points in the plane.

## Asymptotic Density of Zimin Words

Word $W$ is an instance of word $V$ provided there is a homomorphism $\phi$mapping letters to nonempty words so that $\phi(V) = W$. For example, taking$\phi$ such that $\phi(c)=fr$, $\phi(o)=e$ and $\phi(l)=zer$, we see that"freezer" is an instance of "cool". Let $\mathbb{I}_n(V,[q])$ be the probability that a random length $n$ word onthe alphabet $[q] = \{1,2,\cdots q\}$ is an instance of $V$. Having previouslyshown that $\lim_{n \rightarrow \infty} \mathbb{I}_n(V,[q])$ exists, we nowcalculate this limit for two Zimin words, $Z_2 = aba$ and $Z_3 = abacaba$.

## Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras

We endow the set of isomorphism classes of matroids with a new Hopf algebra structure, in which the coproduct is implemented via the combinatorial operations of restriction and deletion. We also initiate the investigation of dendriform coalgebra structures on matroids and introduce a monomial invariant which satisfy a convolution identity with respect to restriction and deletion.

## Avoiding patterns in irreducible permutations

We explore the classical pattern avoidance question in the case of irreducible permutations,i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.

## A relation on 132-avoiding permutation patterns

A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-avoidingif it does not contain the permutation $τ$. For any $n$, thepopularityof a permutation $τ$, denoted $A$_{$n$}($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$_{$n$}($τ$) ≤ $A$_{$n$}($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.

## Symmetries of Monocoronal Tilings

The vertex corona of a vertex of some tiling is the vertex together with the adjacent tiles. A tiling where all vertex coronae are congruent is called monocoronal. We provide a classification of monocoronal tilings in the Euclidean plane and derive a list of all possible symmetry groups of monocoronal tilings. In particular, any monocoronal tiling with respect to direct congruence is crystallographic, whereas any monocoronal tiling with respect to congruence (reflections allowed) is either crystallographic or it has a one-dimensional translation group. Furthermore, bounds on the number of the dimensions of the translation group of monocoronal tilings in higher dimensional Euclidean space are obtained.

## On avoidance of patterns of the form σ-τ by words over a finite alphabet

Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the equivalences witnessed for such patterns of length four. When combined with previous results, numerical evidence, and some arguments in specific cases, we obtain the complete Wilf-classification for all vincular patterns of length four containing a single dash. In some cases, our proof shows further that the equivalence holds for multiset permutations since it is seen to respect the number of occurrences of each letter within a word. Some related enumerative results are provided for patterns $τ$ of length four, among them generating function formulas for the number of members of [$k$]^{$n$}avoiding any $τ$ of the form 11$a-b$.

## Minimum Number of Colors: the Turk’s Head Knots Case Study

An $r$-coloring of a knot diagram is an assignment of integers modulo $r$ to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo $r$. The number of $r$-colorings is a knot invariant i.e., for each knot, it does not depend on the diagram we are using for counting them. In this article we calculate the number of $r$-colorings for the so-called Turk's Head Knots, for each modulus $r$. Furthermore, it is also known that whenever a knot admits an $r$-coloring using more than one color then all other diagrams of the same knot admit such $r$-colorings (called non-trivial $r$-colorings). This leads to the question of what is the minimum number of colors it takes to assemble such an $r$-coloring for the knot at issue. In this article we also estimate and sometimes calculate exactly what is the minimum numbers of colors for each of the Turk's Head Knots, for each relevant modulus $r$.

## Intervals and factors in the Bruhat order

In this paper we study those generic intervals in the Bruhat order of the symmetric group that are isomorphic to the principal order ideal of a permutation w, and consider when the minimum and maximum elements of those intervals are related by a certain property of their reduced words. We show that the property does not hold when w is a decomposable permutation, and that the property always holds when w is the longest permutation.

## Avoider-enforcer star games

In this paper, we study (1 : b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k≥3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games — the strict and the monotone — and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases fmonF, f-F and f+F, where F is the hypergraph of the game.

## Bootstrapping and double-exponential limit laws

We provide a rather general asymptotic scheme for combinatorial parameters that asymptotically follow a discrete double-exponential distribution. It is based on analysing generating functions Gh(z) whose dominant singularities converge to a certain value at an exponential rate. This behaviour is typically found by means of a bootstrapping approach. Our scheme is illustrated by a number of classical and new examples, such as the longest run in words or compositions, patterns in Dyck and Motzkin paths, or the maximum degree in planted plane trees.

## Classification of skew translation generalized quadrangles, I

We describe new classification results in the theory of generalized quadrangles (= Tits-buildings of rank 2 and type B2), more precisely in the (large) subtheory of skew translation generalized quadrangles (``STGQs''). Some of these involve, and solve, long-standing open problems.

## Cell-paths in mono- and bichromatic line arrangements in the plane

We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells where red and blue lines are crossed alternatingly.

## On the numbers of radial orderings of planar point sets

Given a set S of n points in the plane, a radial ordering of S with respect to a point p (not in S) is a clockwise circular ordering of the elements in S by angle around p. If S is two-colored, a colored radial ordering is a radial ordering of S in which only the colors of the points are considered. In this paper, we obtain bounds on the number of distinct non-colored and colored radial orderings of S. We assume a strong general position on S, not three points are collinear and not three lines 14;each passing through a pair of points in S 14;intersect in a point of ℝ2 S. In the colored case, S is a set of 2n points partitioned into n red and n blue points, and n is even. We prove that: the number of distinct radial orderings of S is at most O(n4) and at least Ω(n3); the number of colored radial orderings of S is at most O(n4) and at least Ω(n); there exist sets of points with Θ(n4) colored radial orderings and sets of points with only O(n2) colored radial orderings.

## On the number of regular edge labelings

We prove that any irreducible triangulation on n vertices has O(4.6807n) regular edge labelings and that there are irreducible triangulations on n vertices with Ω(3.0426n) regular edge labelings. Our upper bound relies on a novel application of Shearer's entropy lemma. As an example of the wider applicability of this technique, we also improve the upper bound on the number of 2-orientations of a quadrangulation to O(1.87n).

## Biased weak polyform achievement games

In a biased weak (a,b) polyform achievement game, the maker and the breaker alternately mark a,b previously unmarked cells on an infinite board, respectively. The maker's goal is to mark a set of cells congruent to a polyform. The breaker tries to prevent the maker from achieving this goal. A winning maker strategy for the (a,b) game can be built from winning strategies for games involving fewer marks for the maker and the breaker. A new type of breaker strategy called the priority strategy is introduced. The winners are determined for all (a,b) pairs for polyiamonds and polyominoes up to size four.

## On permutation complexity of fixed points of some uniform binary morphisms

We study properties of infinite permutations generated by fixed points of some uniform binary morphisms, and find the formula for their complexity.

## A combinatorial non-commutative Hopf algebra of graphs

A non-commutative, planar, Hopf algebra of planar rooted trees was defined independently by one of the authors in Foissy (2002) and by R. Holtkamp in Holtkamp (2003). In this paper we propose such a non-commutative Hopf algebra for graphs. In order to define a non-commutative product we use a quantum field theoretical (QFT) idea, namely the one of introducing discrete scales on each edge of the graph (which, within the QFT framework, corresponds to energy scales of the associated propagators). Finally, we analyze the associated quadri-coalgebra and codendrifrom structures.

## Congruence successions in compositions

A composition is a sequence of positive integers, called parts, having a fixed sum. By an m-congruence succession, we will mean a pair of adjacent parts x and y within a composition such that x=y(modm). Here, we consider the problem of counting the compositions of size n according to the number of m-congruence successions, extending recent results concerning successions on subsets and permutations. A general formula is obtained, which reduces in the limiting case to the known generating function formula for the number of Carlitz compositions. Special attention is paid to the case m=2, where further enumerative results may be obtained by means of combinatorial arguments. Finally, an asymptotic estimate is provided for the number of compositions of size n having no m-congruence successions.

## Descents after maxima in compositions

We consider compositions of n, i.e., sequences of positive integers (or parts) (σi)i=1k where σ1+σ2+...+σk=n. We define a maximum to be any part which is not less than any other part. The variable of interest is the size of the descent immediately following the first and the last maximum. Using generating functions and Mellin transforms, we obtain asymptotic expressions for the average size of these descents. Finally, we show with the use of a simple bijection between the compositions of n for n>1, that on average the descent after the last maximum is greater than the descent after the first.

## Graphs where every k-subset of vertices is an identifying set

Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in V$ the intersection of $C$ and the closed neighbourhood of $x$ is nonempty, and these intersections are different for different vertices $x$. Let $k$ be a positive integer. We will consider graphs where \emph{every} $k$-subset is identifying. We prove that for every $k>1$ the maximal order of such a graph is at most $2k-2.$ Constructions attaining the maximal order are given for infinitely many values of $k.$ The corresponding problem of $k$-subsets identifying any at most $\ell$ vertices is considered as well.

## Coloring and Guarding Arrangements

Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between Ω(logn/loglogn). and O(n√). Similarly, we give bounds on the minimum size of a subset S of the intersections of the lines in A such that every cell is bounded by at least one of the vertices in S. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.

## The Magnus-Derek game in groups

The Magnus-Derek game (also called the maximal variant of the vector game), introduced by Nedev and Muthukrishnan is the following: a token is moved around a table with n positions. In each round of the game Magnus chooses a number and then Derek chooses a direction (clockwise or counterclockwise), and the token moves that many positions into that direction. The goal of Magnus is to maximize the number of positions visited, the goal of Derek is the opposite. In the minimal variant of the game the goals of the two players are exchanged: Magnus wants to minimize the number of positions visited and Derek wants the opposite. Here we introduce a generalization of these games: the token is moved in a group, Magnus chooses an element of the group and Derek decides if the current position is multiplied or divided by that element.

## Two player game variant of the Erdős-Szekeres problem

The classical Erd˝os-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erd˝os-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdös-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations

## On the connectedness and diameter of a geometric Johnson graph

Let P be a set of n points in general position in the plane. A subset I of P is called an island if there exists a convex set C such that I = P \C. In this paper we define the generalized island Johnson graph of P as the graph whose vertex consists of all islands of P of cardinality k, two of which are adjacent if their intersection consists of exactly l elements. We show that for large enough values of n, this graph is connected, and give upper and lower bounds on its diameter.

## Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

A \em cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form \F,F^θ,F^θ², \ldots, F^θ^q-1\ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of V_n-1, we let \mathcalKₙ^(K) denote the hypergraph ≤ft(Vₙ, \bigcup_k∈ K Vₙ\choose k\right). In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic q-partition of \mathcalKₙ^(V_k). In particular, we prove that if p is prime then there is a cyclic p^α-partition of \mathcalK^(Vₖ)ₙ if and only if p^α + β divides n, where β = \lfloor \logₚ k\rfloor. As an application of this result, we obtain two sufficient conditions on n₁,n₂,\ldots,n_t, k, α and a prime p for the existence of a cyclic p^α-partition of the complete t-partite k-uniform hypergraph \mathcal K^(k)_n₁,n₂,\ldots,n_t.

## Topological structuring of the digital plane

We discuss an Alexandroff topology on ℤ2 having the property that its quotient topologies include the Khalimsky and Marcus-Wyse topologies. We introduce a further quotient topology and prove a Jordan curve theorem for it.

## Operations on partially ordered sets and rational identities of type A

We consider the family of rational functions ψw= ∏( xwi - xwi+1 )-1 indexed by words with no repetition. We study the combinatorics of the sums ΨP of the functions ψw when w describes the linear extensions of a given poset P. In particular, we point out the connexions between some transformations on posets and elementary operations on the fraction ΨP. We prove that the denominator of ΨP has a closed expression in terms of the Hasse diagram of P, and we compute its numerator in some special cases. We show that the computation of ΨP can be reduced to the case of bipartite posets. Finally, we compute the numerators associated to some special bipartite graphs as Schubert polynomials.

## Descent variation of samples of geometric random variables

In this paper, we consider random words ω1ω2ω3⋯ωn of length n, where the letters ωi ∈ℕ are independently generated with a geometric probability such that Pωi=k=pqk-1 where p+q=1 . We have a descent at position i whenever ωi+1 < ωi. The size of such a descent is ωi-ωi+1 and the descent variation is the sum of all the descent sizes for that word. We study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities, and find the probability generating functions for descent variation of such words.

## A generic method for the enumeration of various classes of directed polycubes

Following the track of polyominoes, in particular the column-by-column construction of Temperley and its interpretation in terms of functional equations due to Bousquet-Mélou, we introduce a generic method for the enumeration of classes of directed polycubes the strata of which satisfy some property P. This method is applied to the enumeration of two new families of polycubes, the s-directed polycubes and the vertically-convex s-directed polycubes, with respect to width and volume. The case of non-directed polycubes is also studied and it is shown that the generic method can be applied in this case too. Finally the general case of d-dimensional polycubes, with d≥4, is investigated, and the generic method is extended in order to handle the enumeration of classes of directed d-polycubes.

## The Erdős-Sós conjecture for geometric graphs

Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that ( 1 / 2 )n2 / k-1-n / 2≤f(n,k) ≤2 n(n-2) / k-2. For the case when k=n, we show that 2 ≤f(n,n) ≤3. For the case when k=n and G is a geometric graph on a set of points in convex position, we completely solve the problem and prove that at least three edges must be removed.

## A bound on the number of perfect matchings in Klee-graphs

The famous conjecture of Lovász and Plummer, very recently proven by Esperet et al. (2011), asserts that every cubic bridgeless graph has exponentially many perfect matchings. In this paper we improve the bound of Esperet et al. for a specific subclass of cubic bridgeless graphs called the Klee-graphs. We show that every Klee-graph with n ≥8 vertices has at least 3 *2(n+12)/60 perfect matchings.

## Random Horn formulas and propagation connectivity for directed hypergraphs

We consider the property that in a random definite Horn formula of size-3 clauses over n variables, where every such clause is included with probability p, there is a pair of variables for which forward chaining produces all other variables. We show that with high probability the property does not hold for p <= 1/(11n ln n), and does hold for p >= (5 1n ln n)/(n ln n).

## Adaptive Identification of Sets of Vertices in Graphs

In this paper, we consider a concept of adaptive identification of vertices and sets of vertices in different graphs, which was recently introduced by Ben-Haim, Gravier, Lobstein and Moncel (2008). The motivation for adaptive identification comes from applications such as sensor networks and fault detection in multiprocessor systems. We present an optimal adaptive algorithm for identifying vertices in cycles. We also give efficient adaptive algorithms for identifying sets of vertices in different graphs such as cycles, king lattices and square lattices. Adaptive identification is also considered in Hamming spaces, which is one of the most widely studied graphs in the field of identifying codes.

## The largest singletons in weighted set partitions and its applications

Recently, Deutsch and Elizalde studied the largest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let A (n,k) (t) denote the total weight of partitions on [n + 1] = \1,2,..., n + 1\ with the largest singleton \k + 1\. In this paper, explicit formulas for A (n,k) (t) and many combinatorial identities involving A (n,k) (t) are obtained by umbral operators and combinatorial methods. In particular, the permutation case leads to an identity related to tree enumerations, namely, [GRAPHICS] where D-k is the number of permutations of [k] with no fixed points.

## On the number of maximal independent sets in a graph

Miller and Muller (1960) and independently Moon and Moser (1965) determined the maximum number of maximal independent sets in an n-vertex graph. We give a new and simple proof of this result.

## New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K 4 is light in the family of 1-planar graphs of minimum degree 7, with its height at most 11.

## A Combinatorial Approach to the Tanny Sequence

The Tanny sequence T (i) is a sequence defined recursively as T(i) = T(i - 1 - T(i - 1)) + T(i - 2 - T(i - 2)), T(0) = T(1) = T(2) = 1. In the first part of this paper we give combinatorial proofs of all the results regarding T(i), that Tanny proved in his paper "A well-behaved cousin of the Hofstadter sequence", Discrete Mathematics, 105(1992), pp. 227-239, using algebraic means. In most cases our proofs turn out to be simpler and shorter. Moreover, they give a "visual" appeal to the theory developed by Tanny. We also generalize most of Tanny's results. In the second part of the paper we present many new results regarding T(i) and prove them combinatorially. Given two integers n and k, it is interesting to know if T(n) = k or not. In this paper we characterize such numbers.

## Sturmian Sequences and Invertible Substitutions

It is known that a Sturmian sequence S can be defined as a coding of the orbit of rho (called the intercept of S) under a rotation of irrational angle alpha (called the slope). On the other hand, a fixed point of an invertible substitution is Sturmian. Naturally, there are two interrelated questions: (1) Given an invertible substitution, we know that its fixed point is Sturmian. What is the slope and intercept? (2) Which kind of Sturmian sequences can be fixed by certain non-trivial invertible substitutions? In this paper we give a unified treatment to the two questions. We remark that though the results are known, our proof is very elementary and concise.

## A de Bruijn - Erdos theorem and metric spaces

De Bruijn and Erdos proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.

## Recursions and divisibility properties for combinatorial Macdonald polynomials

For each integer partition mu, let e (F) over tilde (mu)(q; t) be the coefficient of x(1) ... x(n) in the modified Macdonald polynomial (H) over tilde (mu). The polynomial (F) over tilde (mu)(q; t) can be regarded as the Hilbert series of a certain doubly-graded S(n)-module M(mu), or as a q, t-analogue of n! based on permutation statistics inv(mu) and maj(mu) that generalize the classical inversion and major index statistics. This paper uses the combinatorial definition of (F) over tilde (mu) to prove some recursions characterizing these polynomials, and other related ones, when mu is a two-column shape. Our result provides a complement to recent work of Garsia and Haglund, who proved a different recursion for two-column shapes by representation-theoretical methods. For all mu, we show that e (F) over tilde (mu)(q, t) is divisible by certain q-factorials and t-factorials depending on mu. We use our recursion and related tools to explain some of these factors bijectively. Finally, we present fermionic formulas that express e (F) over tilde ((2n)) (q, t) as a sum of q, t-analogues of n!2(n) indexed by perfect matchings.

## Structure of spanning trees on the two-dimensional Sierpinski gasket

Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ∈{1,2,3,4} at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as φ1=10957/40464, φ2=6626035/13636368, φ3=2943139/13636368, φ4=124895/4545456.

## q-Enumeration of words by their total variation

In recent work, Mansour [Discrete Math. Theoret. Computer Science 11, 2009, 173--186] considers the problem of enumerating all words of length n over {1,2,...,k} (where k is a given integer), that have the total variation equal to a given integer m. In the present paper we study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities. We are interested in the probabilities of words of given type to have a given total variation.

## Crucial abelian k-power-free words

In 1961, Erdos asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX' where X' is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1X2 ... X-k where X-i is a permutation of X-1 for 2 <= i <= k. In this paper, we consider crucial words for abelian k-th powers, i. e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an n-letter alphabet A(n) = \1, 2, ..., n\ avoiding abelian squares has length 4n - 7 for n >= 3. Extending this result, we prove that a minimal crucial word over A(n) avoiding abelian cubes has length 9n - 13 for n >= 5, and it has length 2, 5, 11, and 20 for n = 1, 2, 3, and 4, respectively. Moreover, for n >= 4 and k >= 2, we give a construction of length k(2) (n - 1) - k - 1 of a crucial word over A(n) avoiding abelian k-th powers. This construction gives the minimal length for k = 2 and k = 3. For k >= 4 and n >= 5, we provide a lower bound for the length of […]

## The cluster and dual canonical bases of Z[x(11), ..., x(33)] are equal

The polynomial ring Z[x(11), ..., x(33)] has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group U-q(sl(3) (C)). On the other hand, Z[x(1 1), ... , x(33)] inherits a basis from the cluster monomial basis of a geometric model of the type D-4 cluster algebra. We prove that these two bases are equal. This extends work of Skandera and proves a conjecture of Fomin and Zelevinsky.

## On the existence of block-transitive combinatorial designs

Block-transitive Steiner t-designs form a central part of the study of highly symmetric combinatorial configurations at the interface of several disciplines, including group theory, geometry, combinatorics, coding and information theory, and cryptography. The main result of the paper settles an important open question: There exist no non-trivial examples with t = 7 (or larger). The proof is based on the classification of the finite 3-homogeneous permutation groups, itself relying on the finite simple group classification.

## On the support of the free Lie algebra: the Schutzenberger problems

M.-P. Schutzenberger asked to determine the support of the free Lie algebra L(Zm) (A) on a finite alphabet A over the ring Z(m) of integers mod m and all pairs of twin and anti-twin words, i.e., words that appear with equal (resp. opposite) coefficients in each Lie polynomial. We characterize the complement of the support of L(Zm) (A) in A* as the set of all words w such that m divides all the coefficients appearing in the monomials of l* (w), where l* is the adjoint endomorphism of the left normed Lie bracketing l of the free Lie ring. Calculating l* (w) via the shuffle product, we recover the well known result of Duchamp and Thibon (Discrete Math. 76 (1989) 123-132) for the support of the free Lie ring in a much more natural way. We conjecture that two words u and v of common length n, which lie in the support of the free Lie ring, are twin (resp. anti-twin) if and only if either u = v or n is odd and u = (v) over tilde (resp. if n is even and u = (v) over tilde), where (v) over tilde denotes the reversal of v and we prove that it suffices to show this for a two-lettered alphabet. These problems can be rephrased, for words of length n, in terms of the action of the Dynkin operator l(n) on lambda-tabloids, where lambda is a partition of n. Representing a word w in two letters by the subset I of [n] = \1, 2, ... , n\ that consists of all positions that one of the letters occurs in w, the computation of l* (w) leads us to the notion of the Pascal descent polynomial p(n)(I), a […]

## Generating involutions, derangements, and relatives by ECO

We show how the ECO method can be applied to exhaustively generate some classes of permutations. A previous work initiating this technique and motivating our research was published in Ac ta Informatica, 2004, by S. Bacchelli, E. Barcucci, E. Grazzini and E. Pergola.

## A characterization of infinite smooth Lyndon words

In a recent paper, Brlek, Jamet and Paquin showed that some extremal infinite smooth words are also infinite Lyndon words. This result raises a natural question: are they the only ones? If no, what do the infinite smooth words that are also Lyndon words look like? In this paper, we give the answer, proving that the only infinite smooth Lyndon words are m(\a ...

## The Laplacian spread of Cactuses

Connected graphs in which any two of its cycles have at most one common vertex are called cactuses. In this paper, we continue the work on Laplacian spread of graphs, and determine the graph with maximal Laplacian spread in all cactuses with n vertices.

## Symmetric monochromatic subsets in colorings of the Lobachevsky plane

We prove that for each partition of the Lobachevsky plane into finitely many Borel pieces one of the cells of the partition contains an unbounded centrally symmetric subset.

## Determinants of rational knots

We study the Fox coloring invariants of rational knots. We express the propagation of the colors down the twists of these knots and ultimately the determinant of them with the help of finite increasing sequences whose terms of even order are even and whose terms of odd order are odd.

## The Eulerian distribution on centrosymmetric involutions

We present an extensive study of the Eulerian distribution on the set of centrosymmetric involutions, namely, involutions in S(n) satisfying the property sigma(i) + sigma(n + 1 - i) = n + 1 for every i = 1 ... n. We find some combinatorial properties for the generating polynomial of such distribution, together with an explicit formula for its coefficients. Afterwards, we carry out an analogous study for the subset of centrosymmetric involutions without fixed points.

## Number of connected spanning subgraphs on the Sierpinski gasket

We study the number of connected spanning subgraphs f(d,b) (n) on the generalized Sierpinski gasket SG(d,b) (n) at stage n with dimension d equal to two, three and four for b = 2, and layer b equal to three and four for d = 2. The upper and lower bounds for the asymptotic growth constant, defined as zSG(d,b) = lim(v ->infinity) ln f(d,b)(n)/v where v is the number of vertices, on SG(2,b) (n) with b = 2, 3, 4 are derived in terms of the results at a certain stage. The numerical values of zSG(d,b) are obtained.

## Asymptotic enumeration on self-similar graphs with two boundary vertices

We study two graph parameters, namely the number of spanning forests and the number of connected subgraphs, for self-similar graphs with exactly two boundary vertices. In both cases, we determine the general behavior for these and related auxiliary quantities by means of polynomial recurrences and a careful asymptotic analysis. It turns out that the so-called resistance scaling factor of a graph plays an essential role in both instances, a phenomenon that was previously observed for the number of spanning trees. Several explicit examples show that our findings are likely to hold in an even more general setting.

## The distribution of ascents of size d or more in compositions

A composition of a positive integer n is a finite sequence of positive integers a(1), a(2), ..., a(k) such that a(1) + a(2) + ... + a(k) = n. Let d be a fixed nonnegative integer. We say that we have an ascent of size d or more if a(i+1) >= a(i) + d. We determine the mean, variance and limiting distribution of the number of ascents of size d or more in the set of compositions of n. We also study the average size of the greatest ascent over all compositions of n.

## String pattern avoidance in generalized non-crossing trees

The problem of string pattern avoidance in generalized non-crossing trees is studied. The generating functions for generalized non-crossing trees avoiding string patterns of length one and two are obtained. The Lagrange inversion formula is used to obtain the explicit formulas for some special cases. A bijection is also established between generalized non-crossing trees with special string pattern avoidance and little Schr ̈oder paths.

## Enumeration of words by the sum of differences between adjacent letters

We consider the sum u of differences between adjacent letters of a word of n letters, chosen uniformly at random from a given alphabet. This paper obtains the enumerating generating function for the number of such words with respect to the sum u, as well as explicit formulas for the mean and variance of u.

## Spanning forests on the Sierpinski gasket

We study the number of spanning forests on the Sierpinski gasket SGd(n) at stage n with dimension d equal to two, three and four, and determine the asymptotic behaviors. The corresponding results on the generalized Sierpinski gasket SGd;b(n) with d = 2 and b = 3 ; 4 are obtained. We also derive upper bounds for the asymptotic growth constants for both SGd and SG2,b.

## VC-dimensions of random function classes

For any class of binary functions on [n]={1, ..., n} a classical result by Sauer states a sufficient condition for its VC-dimension to be at least d: its cardinality should be at least O(nd-1). A necessary condition is that its cardinality be at least 2d (which is O(1) with respect to n). How does the size of a 'typical' class of VC-dimension d compare to these two extreme thresholds ? To answer this, we consider classes generated randomly by two methods, repeated biased coin flips on the n-dimensional hypercube or uniform sampling over the space of all possible classes of cardinality k on [n]. As it turns out, the typical behavior of such classes is much more similar to the necessary condition; the cardinality k need only be larger than a threshold of 2d for its VC-dimension to be at least d with high probability. If its expected size is greater than a threshold of O(&log;n) (which is still significantly smaller than the sufficient size of O(nd-1)) then it shatters every set of size d with high probability. The behavior in the neighborhood of these thresholds is described by the asymptotic probability distribution of the VC-dimension and of the largest d such that all sets of size d are shattered.

## Counting descents, rises, and levels, with prescribed first element, in words

Recently, Kitaev and Remmel refined the well-known permutation statistic "descent" by fixing parity of one of the descent's numbers which was extended and generalized in several ways in the literature. In this paper, we shall fix a set partition of the natural numbers N,(N1, ..., Ns), and we study the distribution of descents, levels, and rises according to whether the first letter of the descent, rise, or level lies in Ni over the set of words over the alphabet [k] = 1, ..., k. In particular, we refine and generalize some of the results by Burstein and Mansour

## On quadratic residue codes and hyperelliptic curves

For an odd prime p and each non-empty subset S ⊂ GF(p), consider the hyperelliptic curve X_S deﬁned by y^2 = f_s(x), where f_s(x) = \P_{a2S} (x-a). Using a connection between binary quadratic residue codes and hyperelliptic curves over GF(p), this paper investigates how coding theory bounds give rise to bounds such as the following example: for all sufﬁciently large primes p there exists a subset S ⊂ GF(p) for which the bound |X_S(GF(p))| > 1.39p holds. We also use the quasi-quadratic residue codes deﬁned below to construct an example of a formally self-dual optimal code whose zeta function does not satisfy the "Riemann hypothesis."

## Sufficient conditions for labelled 0-1 laws

If F(x) = e^G(x), where F(x) = \Sum f(n)x^n and G(x) = \Sum g(n)x^n, with 0 ≤ g(n) = O(n^θn/n!), θ ∈ (0,1), and gcd(n : g(n) > 0) = 1, then f(n) = o(f(n − 1)). This gives an answer to Compton's request in Question 8.3 [Compton 1987] for an "easily verifiable sufficient condition" to show that an adequate class of structures has a labelled first-order 0-1 law, namely it sufﬁces to show that the labelled component count function is O(n^θn) for some θ ∈ (0,1). It also provides the means to recursively construct an adequate class of structures with a labelled 0-1 law but not an unlabelled 0-1 law, answering Compton's Question 8.4.

## On symmetric structures of order two

Let (w_n)0 < n be the sequence known as Integer Sequence A047749 In this paper, we show that the integer w_n enumerates various kinds of symmetric structures of order two. We ﬁrst consider ternary trees having a reflexive symmetry and we relate all symmetric combinatorial objects by means of bijection. We then generalize the symmetric structures and correspondences to an infinite family of symmetric objects.

## A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata

We show that a determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata. The proof involves a bijection from these automata to certain marked lattice paths and a sign-reversing involution to evaluate the determinant. We also give a formula for the number of acyclic automata with a given set of sources.

## Simultaneous generation for zeta values by the Markov-WZ method

By application of the Markov-WZ method, we prove a more general form of a bivariate generating function identity containing, as particular cases, Koecher's and Almkvist-Granville's Apéry-like formulae for odd zeta values. As a consequence, we get a new identity producing Apéry-like series for all ζ(2n+4m+3),n,m ≥ 0, convergent at the geometric rate with ratio 2−10.

## "Trivializing'' generalizations of some Izergin-Korepin-type determinants

We generalize (and hence trivialize and routinize) numerous explicit evaluations of determinants and pfaffians due to Kuperberg, as well as a determinant of Tsuchiya. The level of generality of our statements render their proofs easy and routine, by using Dodgson Condensation and/or Krattenthaler's factor exhaustion method.

## A perimeter enumeration of column-convex polyominoes

This work is concerned with the perimeter enumeration of column-convex polyominoes. We consider both the rectangular lattice and the hexagonal lattice. For the rectangular lattice, two formulas for the generating function (gf) already exist and, to all appearances, neither of them admits of a further simplification. We first rederive those two formulas (so as to make the paper self-contained), and then we enrich the rectangular lattice gf with some additional variables. That done, we make a change of variables, which (practically) produces the hexagonal lattice gf. This latter gf was first found by Lin and Wu in 1990. However, our present formula, in addition to having a simpler form, also allows a substantially easier Taylor series expansion. As to the methods, our one is descended from algebraic languages, whereas Lin and Wu used the Temperley methodology.