Combinatorics

---

Approximating optimization problems in graphs with locational uncertainty

Marin Bougeret ; Jérémy Omer ; Michael Poss.

Many combinatorial optimization problems can be formulated as the search for a subgraph that satisfies certain properties and minimizes the total weight. We assume here that the vertices correspond to points in a metric space and can take any position in given uncertainty sets. Then, the cost function to be minimized is the sum of the distances for the worst positions of the vertices in their uncertainty sets. We propose two types of polynomial-time approximation algorithms. The first one relies on solving a deterministic counterpart of the problem where the uncertain distances are replaced with maximum pairwise distances. We study in details the resulting approximation ratio, which depends on the structure of the feasible subgraphs and whether the metric space is Ptolemaic or not. The second algorithm is a fully-polynomial time approximation scheme for the special case of $s-t$ paths.

---

About the determinant of complete non-ambiguous trees

Jean-Christophe Aval.

Complete non-ambiguous trees (CNATs) are combinatorial objects which appear in various contexts.Recently, Chen and Ohlig studied the notion of permutations associated to these objects, and proposed a series of nice conjectures.Most of them were proved by Selig and Zhu, through a connection with the abelian sandpile model.But one conjecture remained open, about the distribution of a natural statistic named determinant.We prove this conjecture, in a bijective way.

---

Ammann Bars for Octagonal Tilings

Thomas Fernique ; Carole Porrier.

Ammann bars are formed by segments (decorations) on the tiles of a tiling such that forming straight lines with them while tiling forces non-periodicity. Only a few cases are known, starting with Robert Ammann's observations on Penrose tiles, but there is no general explanation or construction. In this article we propose a general method for cut and project tilings based on the notion of subperiods and we illustrate it with an aperiodic set of 36 decorated prototiles related to what we called Cyrenaic tilings.

---

Minor-closed classes of binary functions

Benjamin R. Jones.

Binary functions are a generalisation of the cocircuit spaces of binary matroids to arbitrary functions. Every rank function is assigned a binary function, and the deletion and contraction operations of binary functions generalise matroid deletion and contraction. We give the excluded minor characterisations for the classes of binary functions with well defined minors, and those with an associated rank function. Within these classes, we also characterise the classes of binary functions corresponding to polymatroids, matroids and binary matroids by their excluded minors. This gives a new proof of Tutte's excluded minor characterisation of binary matroids in the more generalised space of binary functions.

---

Topology of matching complexes of complete graphs via discrete Morse theory

Anupam Mondal ; Sajal Mukherjee ; Kuldeep Saha.

Bouc (1992) first studied the topological properties of $M_n$, the matching complex of the complete graph of order $n$, in connection with Brown complexes and Quillen complexes. Björner et al. (1994) showed that $M_n$ is homotopically $(\nu_n-1)$-connected, where $\nu_n=\lfloor{\frac{n+1}{3}}\rfloor-1$, and conjectured that this connectivity bound is sharp. Shareshian and Wachs (2007) settled the conjecture by inductively showing that the $\nu_n$-dimensional homology group of $M_n$ is nontrivial, with Bouc's calculation of $H_1(M_7)$ serving as the pivotal base step. In general, the topology of $M_n$ is not very well-understood, even for a small $n$. In the present article, we look into the topology of $M_n$, and $M_7$ in particular, in the light of discrete Morse theory as developed by Forman (1998). We first construct a gradient vector field on $M_n$ (for $n \ge 5$) that doesn't admit any critical simplices of dimension up to $\nu_n-1$, except one unavoidable $0$-simplex, which also leads to the aforementioned $(\nu_n-1)$-connectedness of $M_n$ in a purely combinatorial way. However, for an efficient homology computation by discrete Morse theoretic techniques, we are required to work with a gradient vector field that admits a low number of critical simplices, and also allows an efficient enumeration of gradient paths. An optimal gradient vector field is one with the least number of critical simplices, but the problem of finding an optimal gradient vector field, in general, […]

---

String attractors of Rote sequences

Lubomíra Dvořáková ; Veronika Hendrychová.

In this paper, we describe minimal string attractors (of size two) of pseudopalindromic prefixes of standard complementary-symmetric Rote sequences. Such a class of Rote sequences forms a subclass of binary generalized pseudostandard sequences, i.e., of sequences obtained when iterating palindromic and antipalindromic closures. When iterating only palindromic closure, palindromic prefixes of standard Sturmian sequences are obtained and their string attractors are of size two. However, already when iterating only antipalindromic closure, antipalindromic prefixes of binary pseudostandard sequences are obtained and we prove that the minimal string attractors are of size three in this case. We conjecture that the pseudopalindromic prefixes of any binary generalized pseudostandard sequence have a minimal string attractor of size at most four.

---

Cost-sharing in Parking Games

Jennifer Elder ; Pamela E. Harris ; Jan Kretschmann ; J. Carlos Martínez Mori.

In this paper, we study the total displacement statistic of parking functions from the perspective of cooperative game theory. We introduce parking games, which are coalitional cost-sharing games in characteristic function form derived from the total displacement statistic. We show that parking games are supermodular cost-sharing games, indicating that cooperation is difficult (i.e., their core is empty). Next, we study their Shapley value, which formalizes a notion of "fair" cost-sharing and amounts to charging each car for its expected marginal displacement under a random arrival order. Our main contribution is a polynomial-time algorithm to compute the Shapley value of parking games, in contrast with known hardness results on computing the Shapley value of arbitrary games. The algorithm leverages the permutation-invariance of total displacement, combinatorial enumeration, and dynamic programming. We conclude with open questions around an alternative solution concept for supermodular cost-sharing games and connections to other areas in combinatorics.

---

On polynomials associated to Voronoi diagrams of point sets and crossing numbers

Mercè Claverol ; Andrea de las Heras-Parrilla ; David Flores-Peñaloza ; Clemens Huemer ; David Orden.

Three polynomials are defined for given sets $S$ of $n$ points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-$k$ Voronoi diagrams of $S$, the circle polynomial with coefficients the numbers of circles through three points of $S$ enclosing $k$ points of $S$, and the $E_{\leq k}$ polynomial with coefficients the numbers of (at most $k$)-edges of $S$. We present several formulas for the rectilinear crossing number of $S$ in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if, and only if, $S$ is in convex position. Further, we present bounds on the location of the roots of these polynomials.

---

Interval and $\ell$-interval Rational Parking Functions

Tomás Aguilar-Fraga ; Jennifer Elder ; Rebecca E. Garcia ; Kimberly P. Hadaway ; Pamela E. Harris ; Kimberly J. Harry ; Imhotep B. Hogan ; Jakeyl Johnson ; Jan Kretschmann ; Kobe Lawson-Chavanu et al.

Interval parking functions are a generalization of parking functions in which cars have an interval preference for their parking. We generalize this definition to parking functions with $n$ cars and $m\geq n$ parking spots, which we call interval rational parking functions and provide a formula for their enumeration. By specifying an integer parameter $\ell\geq 0$, we then consider the subset of interval rational parking functions in which each car parks at most $\ell$ spots away from their initial preference. We call these $\ell$-interval rational parking functions and provide recursive formulas to enumerate this set for all positive integers $m\geq n$ and $\ell$. We also establish formulas for the number of nondecreasing $\ell$-interval rational parking functions via the outcome map on rational parking functions. We also consider the intersection between $\ell$-interval parking functions and Fubini rankings and show the enumeration of these sets is given by generalized Fibonacci numbers. We conclude by specializing $\ell=1$, and establish that the set of $1$-interval rational parking functions with $n$ cars and $m$ spots are in bijection with the set of barred preferential arrangements of $[n]$ with $m-n$ bars. This readily implies enumerative formulas. Further, in the case where $\ell=1$, we recover the results of Hadaway and Harris that unit interval parking functions are in bijection with the set of Fubini rankings, which are enumerated by the Fubini numbers.

---

Zero-sum partitions of Abelian groups and their applications to magic- and antimagic-type labelings

Sylwia Cichacz ; Karol Suchan.

The following problem has been known since the 80s. Let $\Gamma$ be an Abelian group of order $m$ (denoted $|\Gamma|=m$), and let $t$ and $\{m_i\}_{i=1}^{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\}_{i=1}^{t}$ such that $|S_i|=m_i$ and $\sum_{s\in S_i}s=0$ for every $1 \leq i \leq t$. Such a subset partition is called a \textit{zero-sum partition}. $|I(\Gamma)|\neq 1$, where $I(\Gamma)$ is the set of involutions in $\Gamma$, is a necessary condition for the existence of zero-sum partitions. In this paper, we show that the additional condition of $m_i\geq 4$ for every $1 \leq i \leq t$, is sufficient. Moreover, we present some applications of zero-sum partitions to magic- and antimagic-type labelings of graphs.

---

Coloring Groups

Ben Adenbaum ; Alexander Wilson.

We introduce coloring groups, which are permutation groups obtained from a proper edge coloring of a graph. These groups generalize the generalized toggle groups of Striker (which themselves generalize the toggle groups introduced by Cameron and Fon-der-Flaass). We present some general results connecting the structure of a coloring group to the structure of its graph coloring, providing graph-theoretic characterizations of the centralizer and primitivity of a coloring group. We apply these results particularly to generalized toggle groups arising from trees as well as coloring groups arising from the independence posets introduced by Thomas and Williams.

---

Representing polynomial of ST-CONNECTIVITY

Jānis Iraids ; Juris Smotrovs.

We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of the Möbius function of an atomistic lattice related to this function. Using this we determine the representing polynomial of any Boolean function corresponding to a ST-CONNECTIVITY problem in acyclic quivers (directed acyclic multigraphs). Only monomials corresponding to unions of paths have non-zero coefficients which are $(-1)^D$ where $D$ is an easily computable function of the quiver corresponding to the monomial (it is the number of plane regions in the case of planar graphs). We determine that the number of monomials with non-zero coefficients for the two-dimensional $n \times n$ grid connectivity problem is $2^{\Omega(n^2)}$.

---

Associated Permutations of Complete Non-Ambiguous Trees

Daniel Chen ; Sebastian Ohlig.

We explore new connections between complete non-ambiguous trees (CNATs) and permutations. We give a bijection between tree-like tableaux and a specific subset of CNATs. This map is used to establish and solve a recurrence relation for the number of tree-like tableaux of a fixed size without occupied corners, proving a conjecture by Laborde-Zubieta. We end by establishing a row/column swapping operation on CNATs and identify new areas for future research.

---

On the $\operatorname{rix}$ statistic and valley-hopping

Nadia Lafrenière ; Yan Zhuang.

This paper studies the relationship between the modified Foata$\unicode{x2013}$Strehl action (a.k.a. valley-hopping)$\unicode{x2014}$a group action on permutations used to demonstrate the $\gamma$-positivity of the Eulerian polynomials$\unicode{x2014}$and the number of rixed points $\operatorname{rix}$$\unicode{x2014}$a recursively-defined permutation statistic introduced by Lin in the context of an equidistribution problem. We give a linear-time iterative algorithm for computing the set of rixed points, and prove that the $\operatorname{rix}$ statistic is homomesic under valley-hopping. We also demonstrate that a bijection $\Phi$ introduced by Lin and Zeng in the study of the $\operatorname{rix}$ statistic sends orbits of the valley-hopping action to orbits of a cyclic version of valley-hopping, which implies that the number of fixed points $\operatorname{fix}$ is homomesic under cyclic valley-hopping.

---

Bijective proof of a conjecture on unit interval posets

Wenjie Fang.

In a recent preprint, Matherne, Morales and Selover conjectured that two different representations of unit interval posets are related by the famous zeta map in $q,t$-Catalan combinatorics. This conjecture was proved recently by Gélinas, Segovia and Thomas using induction. In this short note, we provide a bijective proof of the same conjecture with a reformulation of the zeta map using left-aligned colored trees, first proposed in the study of parabolic Tamari lattices.

---

On the protected nodes in exponential recursive trees

Mehri Javanian ; Rafik Aguech.

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.

---

Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering

Benjamin Braun ; Kaitlin Bruegge ; Matthew Kahle.

Symmetric edge polytopes are lattice polytopes associated with finite simple graphs that are of interest in both theory and applications. We investigate the facet structure of symmetric edge polytopes for various models of random graphs. For an Erdős-Renyi random graph, we identify a threshold probability at which with high probability the symmetric edge polytope shares many facet-supporting hyperplanes with that of a complete graph. We also investigate the relationship between the average local clustering, also known as the Watts-Strogatz clustering coefficient, and the number of facets for graphs with either a fixed number of edges or a fixed degree sequence. We use well-known Markov Chain Monte Carlo sampling methods to generate empirical evidence that for a fixed degree sequence, higher average local clustering in a connected graph corresponds to higher facet numbers in the associated symmetric edge polytope.

---

Inversion sequences avoiding 021 and another pattern of length four

Toufik Mansour ; Gökhan Yıldırım.

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.

---

Bivariate Chromatic Polynomials of Mixed Graphs

Matthias Beck ; Sampada Kolhatkar.

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$. We extend this notion to mixed graphs, which have both directed and undirected edges. Our main result is a decomposition formula which expresses $\chi_G(x,y)$ as a sum of bivariate order polynomials (Beck-Farahmand-Karunaratne-Zuniga Ruiz 2020), and a combinatorial reciprocity theorem for $\chi_G(x,y)$.

---

The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis

Guy Louchard ; Werner Schachinger ; Mark Daniel Ward.

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

---

Antisquares and Critical Exponents

Aseem Baranwal ; James Currie ; Lucas Mol ; Pascal Ochem ; Narad Rampersad ; Jeffrey Shallit.

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

---

The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences

Altar Çiçeksiz ; Yunus Emre Demirci ; Ümit Işlak.

We obtain an explicit formula for the variance of the number of $k$-peaks in a uniformly random permutation. This is then used to obtain an asymptotic formula for the variance of the length of longest $k$-alternating subsequence in random permutations. Also a central limit is proved for the latter statistic.

---

A new discrete theory of pseudoconvexity

Balázs Keszegh.

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

---

Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids

Tom Shlomi.

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

---

Small Youden Rectangles, Near Youden Rectangles, and Their Connections to Other Row-Column Designs

Gerold Jäger ; Klas Markström ; Denys Shcherbak ; Lars-Daniel Öhman.

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 computer search. 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)$. For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call \emph{near Youden rectangles}. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above.

---

Zero-sum partitions of Abelian groups of order $2^n$

Sylwia Cichacz ; Karol Suchan.

The following problem has been known since the 80's. Let $\Gamma$ be an Abelian 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 \leq t$. 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 such partitions, where $I(\Gamma)$ is the set of involutions of $\Gamma$. It was proved 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 completely so far, and it was shown independently by several authors that $m_i\geq 3$ is sufficient 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$ such that $|I(\Gamma)|>1$ and $|\Gamma|=2^n$, for every positive integer $n$. We also present some applications of this result to graph […]

---

Distinct Angles and Angle Chains in Three Dimensions

Ruben Ascoli ; Livia Betti ; Jacob Lehmann Duke ; Xuyan Liu ; Wyatt Milgrim ; Steven J. Miller ; Eyvindur A. Palsson ; Francisco Romero Acosta ; Santiago Velazquez Iannuzzelli.

In 1946, Erdős posed the distinct distance problem, which seeks to find the minimum number of distinct distances between pairs of points selected from any configuration of $n$ points in the plane. The problem has since been explored along with many variants, including ones that extend it into higher dimensions. Less studied but no less intriguing is Erdős' distinct angle problem, which seeks to find point configurations in the plane that minimize the number of distinct angles. In their recent paper "Distinct Angles in General Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolf use a logarithmic spiral to establish an upper bound of $O(n^2)$ on the minimum number of distinct angles in the plane in general position, which prohibits three points on any line or four on any circle. We consider the question of distinct angles in three dimensions and provide bounds on the minimum number of distinct angles in general position in this setting. We focus on pinned variants of the question, and we examine explicit constructions of point configurations in $\mathbb{R}^3$ which use self-similarity to minimize the number of distinct angles. Furthermore, we study a variant of the distinct angles question regarding distinct angle chains and provide bounds on the minimum number of distinct chains in $\mathbb{R}^2$ and $\mathbb{R}^3$.

---

Positional Marked Patterns in Permutations

Sittipong Thamrongpairoj ; Jeffrey B. Remmel.

We define and study positional marked patterns, permutations $\tau$ where one of 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$ in such a way that $\sigma_i$ plays the role of the underlined element in the occurrence. We let $pmp_\tau(\sigma)$ denote the number of positions $i$ which $\sigma$ has a $\tau$-match. This defines a new class of statistics on permutations, where we study such statistics and prove a number of results. In particular, 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 of patterns 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 \}$.

---

Down-step statistics in generalized Dyck paths

Andrei Asinowski ; Benjamin Hackl ; Sarah J. Selkirk.

The number of down-steps between pairs of up-steps in $k_t$-Dyck paths, a generalization of Dyck paths consisting of steps $\{(1, k), (1, -1)\}$ such that the path stays (weakly) above the line $y=-t$, is studied. Results are proved bijectively and by means of generating functions, and lead to several interesting identities as well as links to other combinatorial structures. In particular, there is a connection between $k_t$-Dyck paths and perforation patterns for punctured convolutional codes (binary matrices) used in coding theory. Surprisingly, upon restriction to usual Dyck paths this yields a new combinatorial interpretation of Catalan numbers.

---

On the connectivity of the disjointness graph of segments of point sets in general position in the plane

J. Leaños ; Christophe Ndjatchi ; L. M. Ríos-Castro.

Let $P$ be a set of $n\geq 3$ points in general position in the plane. The edge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all the closed straight line segments with endpoints in $P$, two of which are adjacent in $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$.

---

Restricted generating trees for weak orderings

Daniel Birmajer ; Juan B. Gil ; David S. Kenepp ; Michael D. Weiner.

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

---

Efficient recurrence for the enumeration of permutations with fixed pinnacle set

Wenjie Fang.

Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative study of pinnacle sets of permutations has attracted a fair amount of attention recently. In this article, we provide a recurrence that can be used to compute efficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with a given 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 for pinnacle 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 simple form, 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 admissible orderings of a given pinnacle set, first considered by Rusu (2020) and characterized by Rusu and Tenner (2021), and we give an efficient algorithm for their counting.

---

Further enumeration results concerning a recent equivalence of restricted inversion sequences

Toufik Mansour ; Mark Shattuck.

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

Swapnil Garg.

Fici, Restivo, Silva, and Zamboni define a $k$-antipower to be a word composed of $k$ pairwise distinct, concatenated words of equal length. Berger and Defant conjecture that for any sufficiently well-behaved aperiodic morphic word $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 extend their result to alphabets of arbitrary finite size and characterize those words for which the result does not hold. We also prove their conjecture in the specific case of the Fibonacci word.

---

Certificate complexity and symmetry of nested canalizing functions

Yuan Li ; Frank Ingram ; Huaming Zhang.

Boolean nested canalizing functions (NCFs) have important applications in molecular 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 develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs.

---

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

Thomas Bellitto ; Arnaud Pêcher ; Antoine Sédillot.

A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forall x,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 measurable sets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbb R^2)$ represents the highest proportion of the plane that can be filled by a set avoiding distance 1. This parameter is related to the fractional chromatic number $\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

Nicolas Grelier ; Saeed Gh. Ilchi ; Tillmann Miltzow ; Shakhar Smorodinsky.

A family S of convex sets in the plane defines a hypergraph H = (S, E) as follows. Every subfamily S' of S defines a hyperedge of H if and only if there exists a halfspace h that fully contains S' , and no other set of S is fully contained in h. In this case, we say that h realizes S'. We say a set S is shattered, if all its subsets are realized. The VC-dimension of a hypergraph H is the size of the largest shattered set. We show that the VC-dimension for pairwise 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 (not necessarily disjoint) is unbounded. We provide a quadratic lower bound in the number of pairs of intersecting sets in a shattered family of convex sets in the plane. We also show that the VC-dimension is unbounded for pairwise disjoint 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 be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.

---

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

Michael Joseph ; Tom Roby.

The dynamics of certain combinatorial actions and their liftings to actions at the piecewise-linear and birational level have been studied lately with an eye towards questions of periodicity, orbit structure, and invariants. One key property enjoyed by the rowmotion operator on certain finite partially-ordered sets is homomesy, where the average value of a statistic is the same for all orbits. To prove refined versions of homomesy in the product of two chain posets, 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 the piecewise-linear, birational, and noncommutative realms. Although the map is no longer a bijection, so cannot be used to prove periodicity directly, it still gives enough information to prove the homomesy at the piecewise-linear and birational levels (a result previously shown by D. Grinberg, S. Hopkins, and S. Okada). Even at the noncommutative level, the Stanley--Thomas word of a poset labeling rotates cyclically with the lifting of antichain rowmotion. Along the way we give some formulas for noncommutative antichain rowmotion that we hope will be first steps towards proving the conjectured periodicity at this level.

---

The Elser nuclei sum revisited

Darij Grinberg.

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 each edge 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 that the 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 a sign-reversing involution, and discuss variants, generalizations and refinements, revealing connections to abstract convexity (the notion of an antimatroid) and discrete Morse theory.

---

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

Robert A. Proctor ; Matthew J. Willis.

Let $\lambda$ be a partition with no more than $n$ parts. Let $\beta$ be a weakly increasing $n$-tuple with entries from $\{ 1, ... , n \}$. The flagged Schur 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 for the semistandard Young tableaux of shape $\lambda$ whose values are row-wise bounded by the entries of $\beta$. Gessel and Viennot gave a determinant expression 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 of lattice paths that they used to model the tableaux. We generalize flagged Schur functions by dropping the requirement that $\beta$ be weakly increasing. Then for 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 accordingly group the bounding $\beta$ into equivalence classes and identify the most efficient $\beta$ in each class for the determinant computation. We recently showed 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 these counts "parabolic Catalan numbers". It is […]

---

Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

Colin Defant.

We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map $s$. We first enumerate the permutation class $s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubble sort 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})$ are counted by the so-called "Boolean-Catalan numbers," settling a conjecture of the current author and another conjecture of Hossain. This completes the enumerations 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 and order ideals in Young's lattice.

---

Exponential multivalued forbidden configurations

Travis Dillon ; Attila Sali.

The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum number of unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is a row and column permutation of $F$, has been widely studied in extremal set theory. Recently, this function was extended to $r$-matrices, whose entries lie in $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden number is 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 also prove a stability result for the $2\times 2$ identity matrix. Along the way, we expose some interesting qualitative differences between the cases $r=2$, $r = 3$, and $r > 3$.

---

Determining Genus From Sandpile Torsor Algorithms

Alex McDonough.

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

---

On an alternative sequence comparison statistic of Steele

Ümit Işlak ; Alperen Y. Özdemir.

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

---

Inversion sequences avoiding pairs of patterns

Chunyan Yan ; Zhicong Lin.

The enumeration of inversion sequences avoiding a single pattern was initiated by Corteel--Martinez--Savage--Weselcouch and Mansour--Shattuck independently. Their work has sparked various investigations of generalized patterns in inversion sequences, including patterns of relation triples by Martinez and Savage, consecutive patterns by Auli and Elizalde, and vincular patterns by Lin and Yan. In this paper, we carried out the systematic study of inversion sequences avoiding two patterns of length $3$. Our enumerative results establish further connections to the OEIS sequences and some classical combinatorial objects, such as restricted permutations, weighted ordered trees and set partitions. Since patterns of relation triples are some special multiple patterns of length $3$, our results complement the work by Martinez and Savage. In particular, one of their conjectures regarding the enumeration of $(021,120)$-avoiding inversion sequences is solved.

---

Dissecting a square into congruent polygons

Hui Rao ; Lei Ren ; Yang Wang.

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 prime number $\geq 3$, it is true that the tile must be a rectangle. We conjecture that the same conclusion still holds even if the number of tiles is an odd number $\geq 3$. Our conjecture has been confirmed for triangles in earlier works. We prove that 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

János Balogh ; Cosmin Bonchiş ; Diana Diniş ; Gabriel Istrate ; Ioan Todinca.

We investigate the partitioning of partial orders into a minimal number of heapable subsets. We prove a characterization result reminiscent of the proof of Dilworth's theorem, which yields as a byproduct a flow-based algorithm for computing such a minimal decomposition. On the other hand, in the particular case of sets and sequences of intervals we prove that this minimal decomposition can be computed by a simple greedy-type algorithm. The paper ends with a couple of open problems related to the analog of the Ulam-Hammersley problem for decompositions of sets and sequences of random intervals into heapable sets.

---

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

Lubomíra Dvořáková ; Kateřina Medková ; Edita Pelantová.

We determine the critical exponent and the recurrence function of complementary symmetric Rote sequences. The formulae are expressed in terms of the continued fraction expansions associated with the S-adic representations of the corresponding standard Sturmian sequences. The results are based on a thorough study of return words to bispecial factors of Sturmian sequences. Using the formula for the critical exponent, we describe all complementary symmetric Rote sequences with the critical exponent less than or equal to 3, and we show that there are uncountably many complementary symmetric Rote sequences with the critical exponent less than the critical exponent of the Fibonacci sequence. Our study is motivated by a~conjecture on sequences rich in palindromes 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

H. Amjadi ; N. Soltankhah.

The flower at a point x in a Steiner triple system (X; B) is the set of all triples containing x. Denote by J3F(r) the set of all integers k such that there exists a collection of three STS(2r+1) mutually intersecting in the same set 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 establish that 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

Audace A. V. Dossou-Olory ; Stephan Wagner.

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

---

Proofs of Conjectures about Pattern-Avoiding Linear Extensions

Colin Defant.

After fixing a canonical ordering (or labeling) of the elements of a finite poset, one can associate each linear extension of the poset with a permutation. Some recent papers consider specific families of posets and ask how many linear extensions give rise to permutations that avoid certain patterns. We build off of 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 that Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding linear extensions of rectangular posets.

---

On the centroid of increasing trees

Kevin Durant ; Stephan Wagner.

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

---

Consecutive patterns in restricted permutations and involutions

M. Barnabei ; F. Bonetti ; N. Castronuovo ; M. Silimbani.

It is well-known that the set $\mathbf I_n$ of involutions of the symmetric group $\mathbf S_n$ corresponds bijectively - by the Foata map $F$ - to the set of $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 with labelled steps, and study its properties when restricted to $\mathbf S_n(1\underline{23},1\underline{32}).$ In particular, we show that the set $\mathbf S_n(\underline{123},{132})$ of permutations that avoids the consecutive 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 these results 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 every consecutive pattern of length three. To this aim, we use a modified version of the well-known Goulden-Jacson cluster method.

---

Number of orbits of Discrete Interval Exchanges

Mélodie Lapointe.

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

---

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

Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero ; Carlos Seara ; Javier Tejel.

We say that a finite set of red and blue points in the plane in general position can be $K_{1,3}$-covered if the set can be partitioned into subsets of size $4$, with $3$ points of one color and $1$ point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all 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 general position, how many points of $R\cup B$ can be $K_{1,3}$-covered? and we prove the 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 at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.

---

A Note on Flips in Diagonal Rectangulations

Jean Cardinal ; Vera Sacristán ; Rodrigo I. Silveira.

Rectangulations are partitions of a square into axis-aligned rectangles. A number of results provide bijections between combinatorial equivalence classes of rectangulations and families of pattern-avoiding permutations. Other results deal with local changes involving a single edge of a rectangulation, referred to as flips, edge rotations, or edge pivoting. Such operations induce a graph on equivalence classes of rectangulations, related to so-called flip graphs on triangulations and other families of geometric partitions. In this note, we consider a family of flip operations on the equivalence classes of diagonal rectangulations, and their interpretation as transpositions in the associated Baxter permutations, avoiding the vincular patterns { 3{14}2, 2{41}3 }. This complements results from Law and Reading (JCTA, 2012) and provides a complete characterization of flip operations on diagonal rectangulations, in both geometric and combinatorial terms.

---

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

Evan Chen ; Shyam Narayanan.

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

---

Summation formulas for Fox-Wright function

Chuanan Wei ; Lily Li Liu ; Dianxuan Gong.

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

---

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

Robert A. Proctor ; Matthew J. Willis.

This is the first of three papers that develop structures which are counted by a "parabolic" generalization of Catalan numbers. Fix a subset R of {1,..,n-1}. Consider the ordered partitions of {1,..,n} whose block sizes are determined by R. These are the "inverses" of (parabolic) multipermutations whose multiplicities are determined by R. The standard forms of the ordered partitions are refered to as "R-permutations". The notion of 312-avoidance is extended from permutations to R-permutations. Let lambda be a partition of N such that the set of column lengths in its shape is R or R union {n}. Fix an R-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 weight monomials for some of the semistandard Young tableau of shape lambda that are used to describe the Schur function indexed by lambda. Descriptions of these "Demazure" tableaux developed by the authors in earlier papers are used to prove that the set of these tableaux is convex in Z^N if and only if pi is R-312-avoiding if and only if the tableau set is the entire principal ideal generated by the key of pi. These papers were inspired by results of Reiner and Shimozono and by Postnikov and Stanley concerning coincidences between Demazure characters and flagged Schur functions. This convexity result is used in the next paper to deepen those results from the level of polynomials to the level of tableau sets. The R-parabolic Catalan […]

---

Permutation complexity of images of Sturmian words by marked morphisms

Adam Borchert ; Narad Rampersad.

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

---

Rowmotion and generalized toggle groups

Jessica Striker.

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], from the set of order ideals of a poset to any family of subsets of a finite set. We prove structure theorems for certain finite generalized toggle groups, similar to the theorem of Cameron and Fon-der-Flaass in the case of order ideals. We apply these theorems and find other results on generalized toggle groups in the following settings: chains, antichains, and interval-closed sets of a poset; independent sets, vertex covers, acyclic subgraphs, and spanning subgraphs of a graph; matroids and convex geometries. We generalize rowmotion, an action studied 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 a closure operator. We show that cover-closure is bijective if and only if the set of closed sets is isomorphic to the set of order ideals of a poset, which implies rowmotion is the only bijective cover-closure map.

---

Non-adaptive Group Testing on Graphs

Hamid Kameli.

Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problem of learning a hidden graph for some especial cases, such as hamiltonian cycle, cliques, stars, and matchings. This problem is motivated by problems in chemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, we consider a graph G and a subgraph H of G and we assume that G contains exactly one defective subgraph isomorphic to H. The goal is to find the defective subgraph by testing whether an induced subgraph contains an edge of the defective subgraph, with the minimum number of tests. We present an upper bound for the number of tests to find the defective subgraph by using the symmetric and 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)

Robert A. Proctor ; Matthew J. Willis.

Fix an integer partition lambda that has no more than n parts. Let beta be a weakly increasing n-tuple with entries from {1,..,n}. The flagged Schur function 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 an n-permutation. The type A Demazure character (key polynomial, Demazure polynomial) indexed by lambda and pi is another such polynomial generating function. Reiner and Shimozono and then Postnikov and Stanley studied coincidences between these two families of polynomials. Here their results are sharpened by the specification of unique representatives for the equivalence classes of indexes for both families of polynomials, extended by the consideration of more general beta, and deepened by proving that the polynomial coincidences also hold at the level of the underlying tableau sets. Let R be the 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, called R-permutations, are used to describe the minimal length representatives for the parabolic quotient of the nth symmetric group specified by the set {1,..,n-1}\R. The notion of 312-avoidance is generalized from n-permutations to these set partitions. The R-parabolic Catalan number is defined to be the number of these. Every flagged Schur function arises as a Demazure polynomial. Those Demazure polynomials are precisely indexed by the R-312-avoiding […]

---

Periodic balanced binary triangles

Jonathan Chappelon.

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

Colin Defant.

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\mathbb F_2^n\to\mathbb F_2^n$. Let $\eta_n$ denote the maximum number of periodic orbits of period $2$ that an SDS map of the form $[K_n,f,\pi]$ can have. We show that $\eta_n$ is equal to the maximum number of codewords in a binary code of length $n-1$ with minimum distance at least $3$. This result is significant because it represents the first interpretation of this fascinating coding-theoretic sequence other than its original definition.

---

Refined Enumeration of Corners in Tree-like Tableaux

Sherry H. F. Yan ; Robin D. P. Zhou.

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

---

Stammering tableaux

Matthieu Josuat-Vergès.

The PASEP (Partially Asymmetric Simple Exclusion Process) is a probabilistic model of moving particles, which is of great interest in combinatorics, since it appeared that its partition function counts some tableaux. These tableaux have several variants such as permutations tableaux, alternative tableaux, tree- like tableaux, Dyck tableaux, etc. We introduce in this context certain excursions in Young's lattice, that we call stammering tableaux (by analogy with oscillating tableaux, vacillating tableaux, hesitating tableaux). Some natural bijections make a link with rook placements in a double staircase, chains of Dyck paths obtained by successive addition of ribbons, Laguerre histories, Dyck tableaux, etc.

---

Rises in forests of binary shrubs

Jeffrey Remmel ; Sai-nan Zheng.

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

---

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

Chuanan Wei ; Xiaoxia Wang.

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

---

On universal partial words

Herman Z. Q. Chen ; Sergey Kitaev ; Torsten Mütze ; Brian Y. Sun.

A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is a word 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 universal words exist for any $A$ and $n$. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $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$. For example, $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 the subwords $000$ and $010$). We present results on the existence and non-existence of linear and cyclic universal partial words in different situations (depending on the number of $\Diamond$s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.

---

S-Restricted Compositions Revisited

Behrouz Zolfaghari ; Mehran S. Fallah ; Mehdi Sedighi.

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

---

On the shelling antimatroids of split graphs

Jean Cardinal ; Jean-Paul Doignon ; Keno Merckx.

Chordal graph shelling antimatroids have received little attention with regard to their combinatorial properties and related optimization problems, as compared to the case of poset shelling antimatroids. Here we consider a special case of these antimatroids, namely the split graph shelling antimatroids. We show that the feasible sets of such an antimatroid relate to some poset shelling antimatroids constructed from the graph. We discuss a few applications, obtaining in particular a simple polynomial-time algorithm to find a maximum weight feasible set. We also provide a simple description of the circuits and the free sets.

---

Wilf classification of triples of 4-letter patterns II

David Callan ; Toufik Mansour ; Mark Shattuck.

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

David Callan ; Toufik Mansour ; Mark Shattuck.

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

John Campbell.

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

Colin Defant.

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

---

Enumeration of Corners in Tree-like Tableaux

Alice L. L. Gao ; Emily X. L. Gao ; Patxi Laborde-Zubieta ; Brian Y. Sun.

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

---

Stokes posets and serpent nests

Frédéric Chapoton.

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

Edita Pelantová ; Štěpán Starosta.

A narrow connection between infinite binary words rich in classical palindromes and infinite binary words rich simultaneously in palindromes and pseudopalindromes (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 new class 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 a byproduct, 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

Jean Cardinal ; Michael S. Payne ; Noam Solomon.

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 set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space. Among other things, we prove that: (1) The intersection graph 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 all stabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no 6-subset is stabbed by one line. (3) Every set of n lines in general position in R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or a subset 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 with Turán-type results on independent sets in sparse graphs and hypergraphs. Although similar Ramsey-type statements can be proved using existing generic algebraic frameworks, the lower bounds we get are much larger than what can be obtained with these methods. The proofs directly yield polynomial-time algorithms for finding subsets of the claimed size.

---

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

Inna Mikhaylova.

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

Armend Shabani ; Rexhep Gjergji.

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

Miklós Bóna.

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

---

The Flip Diameter of Rectangulations and Convex Subdivisions

Eyal Ackerman ; Michelle M. Allen ; Gill Barequet ; Maarten Löffler ; Joshua Mermelstein ; Diane L. Souvaine ; Csaba D. Tóth.

We study the configuration space of rectangulations and convex subdivisions of $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 any other rectangulation on the same set of $n$ points. This bound is the best possible for some point sets, while $\Theta(n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.

---

Asymptotic Density of Zimin Words

Joshua Cooper ; Danny Rorabaugh.

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 on the alphabet $[q] = \{1,2,\cdots q\}$ is an instance of $V$. Having previously shown that $\lim_{n \rightarrow \infty} \mathbb{I}_n(V,[q])$ exists, we now calculate this limit for two Zimin words, $Z_2 = aba$ and $Z_3 = abacaba$.

---

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

Nguyen Hoang-Nghia ; Adrian Tanasa ; Christophe Tollu.

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

Jean-Luc Baril.

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

Natalie Aisbett.

A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of 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

Dirk Frettlöh ; Alexey Garber.

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

Toufik Mansour ; Mark Shattuck.

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

Pedro Lopes ; João Matias.

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

Bridget Eileen Tenner.

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

Andrzej Grzesik ; Mirjana Mikalački ; Zoltán Lóránt Nagy ; Alon Naor ; Balázs Patkós ; Fiona Skerman.

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

Helmut Prodinger ; Stephan Wagner.

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

Koen Thas.

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

Oswin Aichholzer ; Jean Cardinal ; Thomas Hackl ; Ferran Hurtado ; Matias Korman ; Alexander Pilz ; Rodrigo I. Silveira ; Ryuhei Uehara ; Pavel Valtr ; Birgit Vogtenhuber et al.

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

José Miguel Dıaz-Banez ; Ruy Fabila-Monroy ; Pablo Pérez-Lantero.

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

Kevin Buchin ; Bettina Speckmann ; Sander Verdonschot.

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

Ian Norris ; Nándor Sieben.

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

Alexandr Valyuzhenich.

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

Adrian Tanasa ; Gerard Duchamp ; Loïc Foissy ; Nguyen Hoang-Nghia ; Dominique Manchon.

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

Toufik Mansour ; Mark Shattuck ; Mark Wilson.

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

Aubrey Blecher ; Charlotte Brennan ; Arnold Knopfmacher.

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

Sylvain Gravier ; Svante Janson ; Tero Laihonen ; Sanna Ranto.

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

Prosenjit Bose ; Jean Cardinal ; Sébastien Collette ; Ferran Hurtado ; Matias Korman ; Stefan Langerman ; Perouz Taslakian.

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

Dániel Gerbner.

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

Parikshit Kolipaka ; Sathish Govindarajan.

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

Crevel Bautista-Santiago ; Javier Cano ; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Hernàn González-Aguilar ; Dolores Lara ; Eliseo Sarmiento ; Jorge Urrutia.

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

Shonda Gosselin ; Andrzej Szymański ; Adam Pawel Wojda.

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

Josef Šlapal.

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

Adrien Boussicault.

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

Charlotte Brennan ; Arnold Knopfmacher.

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

Jean-Marc Champarnaud ; Jean-Philippe Dubernard ; Hadrien Jeanne.

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

Luis Barba ; Ruy Fabila-Monroy ; Dolores Lara ; Jesús Leaños ; Cynthia Rodrıguez ; Gelasio Salazar ; Francisco Zaragoza.

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

Marek Cygan ; Marcin Pilipczuk ; Riste Škrekovski.

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

Robert H. Sloan ; Despina Stasi ; György Turán.

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

Ville Junnila.

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

Yidong Sun ; Yanjie Xu.

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

David R. Wood.

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

Xin Zhang ; Jian-Liang Wu ; Guizhen Liu.

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

Anita Das.

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

Li Peng ; Bo Tan.

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

Ehsan Chiniforooshan ; Vasek Chvatal.

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

Nicholas A. Loehr ; Elizabeth Niese.

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

Shu-Chiuan Chang ; Lung-Chi Chen.

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

Ligia Loreta Cristea ; Helmut Prodinger.

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.

---

Generating involutions, derangements, and relatives by ECO

Vincent Vajnovszki.

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

Geneviève Paquin.

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

Ying Liu.

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.

---

Crucial abelian k-power-free words

Amy Glen ; Bjarni V. Halldorsson ; Sergey Kitaev.

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

Brendon Rhoades.

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

Michael Huber.

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

Ioannis C. Michos.

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 […]

---

Symmetric monochromatic subsets in colorings of the Lobachevsky plane

Taras Banakh ; Artem Dudko ; Dusan Repovs.

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

Louis H. Kauffman ; Pedro Lopes.

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 distribution of ascents of size d or more in compositions

Charlotte Brennan ; Arnold Knopfmacher.

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

Yidong Sun ; Zhiping Wang.

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

Toufik Mansour.

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.

---

The Eulerian distribution on centrosymmetric involutions

Marilena Barnabei ; Flavio Bonetti ; Matteo Silimbani.

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

Shu-Chiuan Chang ; Lung-Chi Chen.

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

Elmar Teufl ; Stephan Wagner.

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.

---

On symmetric structures of order two

Michel Bousquet ; Cédric Lamathe.

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 first 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

David Callan.

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

Khodabakhsh Hessami Pilehrood ; Tatiana Hessami Pilehrood.

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.

---

On quadratic residue codes and hyperelliptic curves

David Joyner.

For an odd prime p and each non-empty subset S ⊂ GF(p), consider the hyperelliptic curve X_S defined 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 sufficiently 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 defined 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

Stanley N. Burris ; Karen A. Yeats.

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 suffices 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.

---

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

Sergey Kitaev ; Toufik Mansour ; Jeff Remmel.

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

---

Spanning forests on the Sierpinski gasket

Shu-Chiuan Chang ; Lung-Chi Chen.

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

Bernard Ycart ; Joel Ratsaby.

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.

---

A perimeter enumeration of column-convex polyominoes

Svjetlan Feretić.

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.

---

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

Tewodros Amdeberhan ; Doron Zeilberger.

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.

---