Combinatorics

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


Binary Codes and Period-2 Orbits of Sequential Dynamical Systems

Defant, Colin.
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 […]

Refined Enumeration of Corners in Tree-like Tableaux

Yan, Sherry H. F. ; Zhou, Robin D. P..
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 […]

Stammering tableaux

Josuat-Vergès, Matthieu.
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 […]

Rises in forests of binary shrubs

Remmel, Jeffrey ; Zheng, Sai-nan.
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 […]

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

Wei, Chuanan ; Wang, Xiaoxia.
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 […]

On universal partial words

Chen, Herman Z. Q. ; Kitaev, Sergey ; Mütze, Torsten ; Sun, Brian Y..
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 […]

S-Restricted Compositions Revisited

Zolfaghari, Behrouz ; Fallah, Mehran S. ; Sedighi, Mehdi.
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- […]

On the shelling antimatroids of split graphs

Cardinal, Jean ; Doignon, Jean-Paul ; Merckx, Keno.
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 […]

Wilf classification of triples of 4-letter patterns II

Callan, David ; Mansour, Toufik ; Shattuck, Mark.
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 […]

Wilf classification of triples of 4-letter patterns I

Callan, David ; Mansour, Toufik ; Shattuck, Mark.
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 […]

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

Campbell, John.
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 […]

Postorder Preimages

Defant, Colin.
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 […]

Enumeration of Corners in Tree-like Tableaux

Gao, Alice L. L. ; Gao, Emily X. L. ; Laborde-Zubieta, Patxi ; Sun, Brian Y..
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 […]

Stokes posets and serpent nests

Chapoton, Frédéric.
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 […]

Constructions of words rich in palindromes and pseudopalindromes

Pelantová, Edita ; Starosta, Štěpán.
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 […]

Ramsey-type theorems for lines in 3-space

Cardinal, Jean ; Payne, Michael S. ; Solomon, Noam.
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 […]

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

Mikhaylova, Inna.
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 […]

Statistics for 3-letter patterns with repetitions in compositions

Shabani, Armend ; Gjergji, Rexhep.
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 […]

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

Bóna, Miklós.
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

Ackerman, Eyal ; Allen, Michelle M. ; Barequet, Gill ; Löffler, Maarten ; Mermelstein, Joshua ; Souvaine, Diane L. ; Tóth, Csaba D..
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 […]

Asymptotic Density of Zimin Words

Cooper, Joshua ; Rorabaugh, Danny.
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 […]

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

Hoang-Nghia, Nguyen ; Tanasa, Adrian ; Tollu, Christophe.
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 […]

Avoiding patterns in irreducible permutations

Baril, Jean-Luc.
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 […]

A relation on 132-avoiding permutation patterns

Aisbett, Natalie.
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 […]

Symmetries of Monocoronal Tilings

Frettlöh, Dirk ; Garber, Alexey.
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 […]

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

Mansour, Toufik ; Shattuck, Mark.
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 […]

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

Lopes, Pedro ; Matias, João.
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., […]

Intervals and factors in the Bruhat order

Tenner, Bridget Eileen.
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 […]

Avoider-enforcer star games

Grzesik, Andrzej ; Mikalački, Mirjana ; Nagy, Zoltán Lóránt ; Naor, Alon ; Patkós, Balázs ; Skerman, Fiona.
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 […]

Bootstrapping and double-exponential limit laws

Prodinger, Helmut ; Wagner, Stephan.
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 […]

Classification of skew translation generalized quadrangles, I

Thas, Koen.
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

Aichholzer, Oswin ; Cardinal, Jean ; Hackl, Thomas ; Hurtado, Ferran ; Korman, Matias ; Pilz, Alexander ; Silveira, Rodrigo I. ; Uehara, Ryuhei ; Valtr, Pavel ; Vogtenhuber, Birgit 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 […]

On the numbers of radial orderings of planar point sets

Dıaz-Banez, José Miguel ; Fabila-Monroy, Ruy ; Pérez-Lantero, Pablo.
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. […]

On the number of regular edge labelings

Buchin, Kevin ; Speckmann, Bettina ; Verdonschot, Sander.
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 […]

Biased weak polyform achievement games

Norris, Ian ; Sieben, Nándor.
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 […]

On permutation complexity of fixed points of some uniform binary morphisms

Valyuzhenich, Alexandr.
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

Tanasa, Adrian ; Duchamp, Gerard ; Foissy, Loïc ; Hoang-Nghia, Nguyen ; Manchon, Dominique.
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 […]

Congruence successions in compositions

Mansour, Toufik ; Shattuck, Mark ; Wilson, Mark, .
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 […]

Descents after maxima in compositions

Blecher, Aubrey ; Brennan, Charlotte ; Knopfmacher, Arnold.
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 […]

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

Gravier, Sylvain ; Janson, Svante ; Laihonen, Tero ; Ranto, Sanna.
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$ […]

Coloring and Guarding Arrangements

Bose, Prosenjit ; Cardinal, Jean ; Collette, Sébastien ; Hurtado, Ferran ; Korman, Matias ; Langerman, Stefan ; Taslakian, Perouz.
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 […]

The Magnus-Derek game in groups

Gerbner, Dániel.
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), […]

Two player game variant of the Erd\H os-Szekeres problem

Kolipaka, Parikshit ; Govindarajan, Sathish.
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 […]

On the connectedness and diameter of a geometric Johnson graph

Bautista-Santiago, Crevel ; Cano, Javier ; Fabila-Monroy, Ruy ; Flores-Peñaloza, David ; González-Aguilar, Hernàn ; Lara, Dolores ; Sarmiento, Eliseo ; Urrutia, Jorge.
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 […]

Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Gosselin, Shonda ; Szymański, Andrzej ; Wojda, Adam Pawel.
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 […]

Topological structuring of the digital plane

Šlapal, Josef.
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

Boussicault, Adrien.
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 […]

Descent variation of samples of geometric random variables

Brennan, Charlotte ; Knopfmacher, Arnold.
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 […]

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

Champarnaud, Jean-Marc ; Dubernard, Jean-Philippe ; Jeanne, Hadrien.
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 […]

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

Barba, Luis ; Fabila-Monroy, Ruy ; Lara, Dolores ; Leaños, Jesús ; Rodrıguez, Cynthia ; Salazar, Gelasio ; Zaragoza, Francisco.
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 […]

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

Cygan, Marek ; Pilipczuk, Marcin ; Škrekovski, Riste.
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 […]

Random Horn formulas and propagation connectivity for directed hypergraphs

Sloan, Robert H. ; Stasi, Despina ; Turán, György.
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 […]

Adaptive Identification of Sets of Vertices in Graphs

Junnila, Ville.
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 […]

The largest singletons in weighted set partitions and its applications

Sun, Yidong ; Xu, Yanjie.
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 […]

On the number of maximal independent sets in a graph

Wood, David, .
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

Zhang, Xin ; Wu, Jian-Liang ; Liu, Guizhen.
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 […]

A Combinatorial Approach to the Tanny Sequence

Das, Anita.
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 […]

Sturmian Sequences and Invertible Substitutions

Peng, Li ; Tan, Bo.
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 […]

A de Bruijn - Erdos theorem and metric spaces

Chiniforooshan, Ehsan ; Chvatal, Vasek.
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

Loehr, Nicholas A. ; Niese, Elizabeth.
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, […]

Structure of spanning trees on the two-dimensional Sierpinski gasket

Chang, Shu-Chiuan ; Chen, Lung-Chi.
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 […]

q-Enumeration of words by their total variation

Cristea, Ligia Loreta ; Prodinger, Helmut.
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 […]

Generating involutions, derangements, and relatives by ECO

Vajnovszki, Vincent.
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

Paquin, Geneviève.
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, […]

The Laplacian spread of Cactuses

Liu, Ying.
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

Glen, Amy ; Halldorsson, Bjarni V. ; Kitaev, Sergey.
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 […]

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

Rhoades, Brendon.
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 […]

On the existence of block-transitive combinatorial designs

Huber, Michael.
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 […]

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

Michos, Ioannis C..
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 […]

Symmetric monochromatic subsets in colorings of the Lobachevsky plane

Banakh, Taras ; Dudko, Artem ; Repovs, Dusan.
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

Kauffman, Louis H. ; Lopes, Pedro.
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

Brennan, Charlotte ; Knopfmacher, Arnold.
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 […]

String pattern avoidance in generalized non-crossing trees

Sun, Yidong ; Wang, Zhiping.
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 […]

Enumeration of words by the sum of differences between adjacent letters

Mansour, Toufik.
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 […]

The Eulerian distribution on centrosymmetric involutions

Barnabei, Marilena ; Bonetti, Flavio ; Silimbani, Matteo.
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 […]

Number of connected spanning subgraphs on the Sierpinski gasket

Chang, Shu-Chiuan ; Chen, Lung-Chi.
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 […]

Asymptotic enumeration on self-similar graphs with two boundary vertices

Teufl, Elmar ; Wagner, Stephan.
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 […]

On symmetric structures of order two

Bousquet, Michel ; Lamathe, Cédric.
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 […]

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

Callan, David.
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 […]

Simultaneous generation for zeta values by the Markov-WZ method

Pilehrood, Khodabakhsh Hessami ; Pilehrood, Tatiana Hessami.
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 […]

On quadratic residue codes and hyperelliptic curves

Joyner, David.
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 […]

Sufficient conditions for labelled 0-1 laws

Burris, Stanley N. ; Yeats, Karen A..
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 […]

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

Kitaev, Sergey ; Mansour, Toufik ; Remmel, Jeff.
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 […]

Spanning forests on the Sierpinski gasket

Chang, Shu-Chiuan ; Chen, Lung-Chi.
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 […]

VC-dimensions of random function classes

Ycart, Bernard ; Ratsaby, Joel.
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 […]

A perimeter enumeration of column-convex polyominoes

Feretić, Svjetlan.
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 […]

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

Amdeberhan, Tewodros ; Zeilberger, Doron.
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 […]

Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

Duque, Frank ; Fabila-Monroy, Ruy ; Hidalgo-Toscano, Carlos ; Pérez-Lantero, Pablo.
An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2\ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$. […]