We present an exact formula for the number of distinct crease patterns in a square shaped region of a given size that appear in the 2 dimensional paperfolding structure.
Answering a question of Erdős and Nešetřil, we show that the maximum number of inclusion-wise minimal vertex cuts in a graph on $n$ vertices is at most $1.8899^n$ for large enough $n$.
We prove that the conjecture made by Peter Frankl in the late 1970s is true. In other words for every finite union-closed family which contains a non?empty set, there is an element that belongs to at least half of its m
For a finite subgroup G of the special unitary group SU2, we study the centralizer algebra Zk(G) = EndG(V⊗k) of G acting on the k-fold tensor product of its defining representation V = C2. The McKay corre- spondence relates the representation theory of these groups to an associated affine Dynkin diagram, and we use this connection to study the structure and representation theory of Zk(G) via the combinatorics of the Dynkin diagram. When G equals the binary tetrahedral, octahedral, or icosahedral group, we exhibit remarkable connections between Zk (G) and the Martin-Jones set partition algebras.
Following the lead of Stanley and Gessel, we consider a linear map which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as multivariate generating series of non-decreasing functions on the graph (or of P -partitions of the poset).We describe the kernel of this linear map, using a simple combinatorial operation that we call cyclic inclusion- exclusion. Our result also holds for the natural non-commutative analog and for the commutative and non-commutative restrictions to bipartite graphs.
We use Khovanov-Lauda-Rouquier (KLR) algebras to categorify a crystal isomorphism between a funda-mental crystal and the tensor product of a Kirillov-Reshetikhin crystal and another fundamental crystal, all in affine type. The nodes of the Kirillov-Reshetikhin crystal correspond to a family of “trivial” modules. The nodes of the fun-damental crystal correspond to simple modules of the corresponding cyclotomic KLR algebra. The crystal operators correspond to socle of restriction and behave compatibly with the rule for tensor product of crystal graphs.
The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion- contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This polynomial is constructed using lattice point counts in the Minkowski sum of the base polytope of a polymatroid and scaled copies of the standard simplex. We also show that, in the matroid case, our polynomial has coefficients of alternating sign, with a combinatorial interpretation closely tied to the Dawson partition.
We study the enumeration of diagonally and antidiagonally symmetric alternating sign matrices (DAS- ASMs) of fixed odd order by introducing a case of the six-vertex model whose configurations are in bijection with such matrices. The model involves a grid graph on a triangle, with bulk and boundary weights which satisfy the Yang– Baxter and reflection equations. We obtain a general expression for the partition function of this model as a sum of two determinantal terms, and show that at a certain point each of these terms reduces to a Schur function. We are then able to prove a conjecture of Robbins from the mid 1980's that the total number of (2n + 1) × (2n + 1) DASASMs is∏n (3i)! ,andaconjectureofStroganovfrom2008thattheratiobetweenthenumbersof(2n+1)×(2n+1) i=0 (n+i)! DASASMs with central entry −1 and 1 is n/(n + 1). Among the several product formulae for the enumeration of symmetric alternating sign matrices which were conjectured in the 1980's, that for odd-order DASASMs is the last to have been proved.
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.
We give a simple proof of the property discovered by Xavier Grandsart: let $W$ be a circular binary word; then the differences in the number of occurences $|W|_{0011}-|W|_{1100}$, $ |W|_{1101}-|W|_{1011}$ , $|W|_{1010}-|W|_{0101}$ and $|W|_{0100}-|W|_{0010}$ are equal.
The aim of this paper is to give a corrected bijective proof of Vershik's relations for the Kostka numbers. Our proof uses insertion and reverse insertion algorithms, as in the combinatorial proof of the Pieri rule.
Within an axiomatic framework for three-dimensional projective space based on lines alone, we explore the Fano axiom of harmonicity according to which the diagonal lines of a complete quadrilateral are not concurrent.
In this paper we show that n-dimensional dual hyperovals cannot exist in all but one classical polar space of rank n if n is even. This resolves a question posed by Yoshiara.