Authors:Benny Chor; Péter L. Erdős; Yonatan Komornik Abstract: Given two binary trees on N labeled leaves, the quartet distance between the trees is the number of disagreeing quartets. By permuting the leaves at random, the expected quartet distance between the two trees is \(\frac{2}{3}\left( {\begin{array}{c}N\\ 4\end{array}}\right) \) . However, no strongly explicit construction reaching this bound asymptotically was known. We consider complete, balanced binary trees on \(N=2^n\) leaves, labeled by n bits long sequences. Ordering the leaves in one tree by the prefix order, and in the other tree by the suffix order, we show that the resulting quartet distance is \(\left( \frac{2}{3} + o(1)\right) \left( {\begin{array}{c}N\\ 4\end{array}}\right) \) , and it always exceeds the \(\frac{2}{3}\left( {\begin{array}{c}N\\ 4\end{array}}\right) \) bound. PubDate: 2019-01-05 DOI: 10.1007/s00026-018-0411-3

Authors:Ross Atkins; Colin McDiarmid Abstract: Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection (TBR), subtree prune and regraft (SPR), and rooted subtree prune and regraft (rSPR). We show that for a pair of leaf-labelled binary trees with n leaves, the maximum number of such moves required to transform one into the other is \(n-\Theta (\sqrt{n})\) , extending a result of Ding, Grünewald, and Humphries, and this holds also if one of the trees is fixed arbitrarily. If the pair is chosen uniformly at random, then the expected number of moves required is \(n-\Theta (n^{2/3})\) . These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees. PubDate: 2018-12-13 DOI: 10.1007/s00026-018-0410-4

Authors:Brian Cook; Ákos Magyar; Tatchai Titichetrakun Abstract: Let A be a subset of positive relative upper density of \(\mathbb {P}^d\) , the d-tuples of primes. We present an essentially self-contained, combinatorial argument to show that A contains infinitely many affine copies of any finite set \(F\subseteq \mathbb {Z}^d\) . This provides a natural multidimensional extension of the theorem of Green and Tao on the existence of long arithmetic progressions in the primes. PubDate: 2018-11-30 DOI: 10.1007/s00026-018-0402-4

Authors:Victor Reiner; Eric Sommers Abstract: Catalan numbers are known to count noncrossing set partitions, while Narayana and Kreweras numbers refine this count according to the number of blocks in the set partition, and by its collection of block sizes. Motivated by reflection group generalizations of Catalan numbers and their q-analogues, this paper concerns a definition of q-Kreweras numbers for finite Weyl groups W, refining the q-Catalan numbers for W, and arising from work of the second author. We give explicit formulas in all types for the q-Kreweras numbers. In the classical types A, B, C, we also record formulas for the q-Narayana numbers and in the process show that the formulas depend only on the Weyl group (that is, they coincide in types B and C). In addition, we verify that in the classical types A, B, C, D the q-Kreweras numbers obey the expected cyclic sieving phenomena when evaluated at appropriate roots of unity. PubDate: 2018-11-13 DOI: 10.1007/s00026-018-0408-y

Authors:Louis Gaudet; David Jensen; Dhruv Ranganathan; Nicholas Wawrykow; Theodore Weisman Abstract: We study which groups with pairing can occur as the Jacobian of a finite graph. We provide explicit constructions of graphs whose Jacobian realizes a large fraction of odd groups with a given pairing. Conditional on the generalized Riemann hypothesis, these constructions yield all groups with pairing of odd order, and unconditionally, they yield all groups with pairing whose prime factors are sufficiently large. For groups with pairing of even order, we provide a partial answer to this question, for a certain restricted class of pairings. Finally, we explore which finite abelian groups occur as the Jacobian of a simple graph. There exist infinite families of finite abelian groups that do not occur as the Jacobians of simple graphs. PubDate: 2018-11-02 DOI: 10.1007/s00026-018-0406-0

Authors:Mark Wildon Abstract: This paper proves a combinatorial rule expressing the product \(s_\tau (s_{\lambda /\mu } \circ p_r)\) of a Schur function and the plethysm of a skew Schur function with a power-sum symmetric function as an integral linear combination of Schur functions. This generalizes the SXP rule for the plethysm \(s_\lambda \circ p_r\) . Each step in the proof uses either an explicit bijection or a sign-reversing involution. The proof is inspired by an earlier proof of the SXP rule due to Remmel and Shimozono (Discrete Math. 193:257–266, 1998). The connections with two later combinatorial rules for special cases of this plethysm are discussed. Two open problems are raised. The paper is intended to be readable by non-experts. PubDate: 2018-11-01 DOI: 10.1007/s00026-018-0409-x

Authors:Byungchan Kim; Pee Choon Toh Abstract: We study a crank function M(m, n) for cubic partition pairs. We show that the function M(m, n) explains a cubic partition pair congruence and we also obtain various arithmetic properties regarding M(m, n). In particular, using the \(\Theta \) -operator, we confirm a conjecture on the sign pattern of c(n), the number of cubic partition pairs of n, weighted by the parity of the crank. PubDate: 2018-10-13 DOI: 10.1007/s00026-018-0407-z

Authors:Richard Ehrenborg Abstract: We study how the shelling components behave under the pyramid and prism operations. As a consequence we obtain a concise recursion for the cubical shelling contributions. PubDate: 2018-10-11 DOI: 10.1007/s00026-018-0412-2

Authors:Raymond Cheng; David M. Jackson; Geoff J. Stanley Abstract: Quasi-triangular Hopf algebras were introduced by Drinfel’d in his construction of solutions to the Yang–Baxter Equation. This algebra is built upon \(\mathscr {U}_h(\mathfrak {sl}_2)\) , the quantized universal enveloping algebra of the Lie algebra \(\mathfrak {sl}_2\) . In this paper, combinatorial structure in \(\mathscr {U}_h(\mathfrak {sl}_2)\) is elicited, and used to assist in highly intricate calculations in this algebra. To this end, a combinatorial methodology is formulated for straightening algebraic expressions to a canonical form in the case \(n=1\) . We apply this formalism to the quasi-triangular Hopf algebras and obtain a constructive account not only for the derivation of the Drinfel’d’s \(sR\) -matrix, but also for the arguably mysterious ribbon elements of \(\mathscr {U}_h(\mathfrak {sl}_2)\) . Finally, we extend these techniques to the higher-dimensional algebras \(\mathscr {U}_h(\mathfrak {sl}_{n+1})\) . While these explicit algebraic results are well known, our contribution is in our formalism and perspective: our emphasis is on the combinatorial structure of these algebras and how that structure may guide algebraic constructions. PubDate: 2018-10-10 DOI: 10.1007/s00026-018-0404-2

Authors:Noga Alon; Steve Butler; Ron Graham; Utkrisht C. Rajkumar Abstract: Let \(M = (s_1, s_2, \ldots , s_n) \) be a sequence of distinct symbols and \(\sigma \) a permutation of \(\{1,2, \ldots , n\}\) . Denote by \(\sigma (M)\) the permuted sequence \((s_{\sigma (1)}, s_{\sigma (2)}, \ldots , s_{\sigma (n)})\) . For a given positive integer d, we will say that \(\sigma \) is d-resilient if no matter how d entries of M are removed from M to form \(M'\) and d entries of \(\sigma (M)\) are removed from \(\sigma (M)\) to form \(\sigma (M)'\) (with no symbol being removed from both sequences), it is always possible to reconstruct the original sequence M from \(M'\) and \(\sigma (M)'\) . Necessary and sufficient conditions for a permutation to be d-resilient are established in terms of whether certain auxiliary graphs are acyclic. We show that for d-resilient permutations for [n] to exist, n must have size at least exponential in d, and we give an algorithm to construct such permutations in this case. We show that for each d and all sufficiently large n, the fraction of all permutations on n elements which are d-resilient is bounded away from 0. PubDate: 2018-10-05 DOI: 10.1007/s00026-018-0403-3

Authors:Akiyoshi Tsuchiya Abstract: Let \((P,\le _P)\) and \((Q,\le _Q)\) be finite partially ordered sets with \( P = Q =d\) , and \(\mathcal {C}(P) \subset \mathbb {R}^d\) and \(\mathcal {C}(Q) \subset \mathbb {R}^d\) their chain polytopes. The twinned chain polytope of P and Q is the lattice polytope \(\Gamma (\mathcal {C}(P),\mathcal {C}(Q)) \subset \mathbb {R}^d\) which is the convex hull of \(\mathcal {C}(P) \cup (-\mathcal {C}(Q))\) . It is known that twinned chain polytopes are Gorenstein Fano polytopes with the integer decomposition property. In the present paper, we study combinatorial properties of twinned chain polytopes. First, we will give the formula of the volume of twinned chain polytopes in terms of the underlying partially ordered sets. Second, we will identify the facet-supporting hyperplanes of twinned chain polytopes in terms of the underlying partially ordered sets. Finally, we will provide the vertex representations of the dual polytopes of twinned chain polytopes. PubDate: 2018-10-05 DOI: 10.1007/s00026-018-0405-1

Authors:Dong Quan Ngoc Nguyen Abstract: For a nonnegative integer n, and a prime \({\mathcal{P}}\) in \({\mathbb{F}_{q}[T]}\) , we prove a result that provides a method for computing the number of integers m with \({0 \leq m \leq n}\) for which the Carlitz binomial coefficients \({(_{m}^{n})_{C}}\) fall into each of the residue classes modulo \({\mathcal{P}}\) . Our main result can be viewed as a function field analogue of the Garfield-Wilf theorem. PubDate: 2018-07-27 DOI: 10.1007/s00026-018-0400-6

Authors:Nate Harman Abstract: We consider the following counting problem related to the card game SET: how many k-element SET-free sets are there in an n-dimensional SET deck' Through a series of algebraic reformulations and reinterpretations, we show the answer to this question satisfies two polynomiality conditions. PubDate: 2018-07-27 DOI: 10.1007/s00026-018-0401-5

Authors:Samuel D. Judge; William J. Keith; Fabrizio Zanello Abstract: The purpose of this note is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely, the conjecture that the partition function p(n) is equidistributed modulo 2. Our main result will relate the densities, say, \({\delta_t}\) , of the odd values of the t-multipartition functions \({p_t(n)}\) , for several integers t. In particular, we will show that if \({\delta_t > 0}\) for some \({t \in \{5, 7, 11, 13, 17, 19, 23, 25\}}\) , then (assuming it exists) \({\delta_1 > 0}\) ; that is, p(n) itself is odd with positive density. Notice that, currently, the best unconditional result does not even imply that p(n) is odd for \({\sqrt{x}}\) values of \({n \leq x}\) . In general, we conjecture that \({\delta_t = 1/2}\) for all t odd, i.e., that similarly to the case of p(n), all multipartition functions are in fact equidistributed modulo 2. Our arguments will employ a number of algebraic and analytic methods, ranging from an investigation modulo 2 of some classical Ramanujan identities and several other eta product results, to a unified approach that studies the parity of the Fourier coefficients of a broad class of modular form identities recently introduced by Radu. PubDate: 2018-07-24 DOI: 10.1007/s00026-018-0397-x

Authors:George E. Andrews Abstract: The paper begins with a study of a couple of classes of partitions in which each even part is smaller than each odd. In one class, a Dyson-type crank exists to explain a mod 5 congruence. The second part of the paper treats the arithmetic and combinatorial properties of the third order mock theta function \({\nu(q)}\) and relates the even part of \({\nu(q)}\) to the partitions initially considered. We also consider a surprisingly simple combinatorial relationship between the cranks and the ranks of the partition of n. PubDate: 2018-07-16 DOI: 10.1007/s00026-018-0398-9

Authors:Kevin Grace; Stefan H. M. van Zwam Abstract: Geelen, Gerards, and Whittle [3] announced the following result: let \({q = p^k}\) be a prime power, and let \({\mathcal{M}}\) be a proper minor-closed class of GF(q)-representable matroids, which does not contain PG(r − 1, p) for sufficiently high r. There exist integers k, t such that every vertically k-connected matroid in \({\mathcal{M}}\) is a rank- \({(\leq t)}\) perturbation of a frame matroid or the dual of a frame matroid over GF(q). They further announced a characterization of the perturbations through the introduction of subfield templates and frame templates. We show a family of dyadic matroids that form a counterexample to this result. We offer several weaker conjectures to replace the ones in [3], discuss consequences for some published papers, and discuss the impact of these new conjectures on the structure of frame templates. PubDate: 2018-07-16 DOI: 10.1007/s00026-018-0396-y

Authors:L. Bossinger; X. Fang; G. Fourier; M. Hering; M. Lanini Abstract: We establish an explicit bijection between the toric degenerations of the Grassmannian Gr(2, n) arising from maximal cones in tropical Grassmannians and the ones coming from plabic graphs corresponding to Gr(2, n). We show that a similar statement does not hold for Gr(3, 6). PubDate: 2018-07-16 DOI: 10.1007/s00026-018-0395-z

Abstract: In this paper, we provide combinatorial proofs for certain partition identities which arise naturally in the context of Langlands’ beyond endoscopy proposal. These partition identities motivate an explicit plethysm expansion of \({{\rm Sym}^j}\) \({{{\rm Sym}^{k}}V}\) for \({{\rm GL}_2}\) in the case k = 3. We compute the plethysm explicitly for the cases k = 3, 4. Moreover, we use these expansions to explicitly compute the basic function attached to the symmetric power L-function of \({{\rm GL}_2}\) for these two cases. PubDate: 2018-06-06 DOI: 10.1007/s00026-018-0391-3

Abstract: Alternating sign matrices and totally symmetric self-complementary plane partitions are equinumerous sets of objects for which no explicit bijection is known. In this paper, we identify a subset of totally symmetric self-complementary plane partitions corresponding to permutations by giving a statistic-preserving bijection to permutation matrices, which are a subset of alternating sign matrices. We use this bijection to define a new partial order on permutations, and prove this new poset contains both the Tamari lattice and the Catalan distributive lattice as subposets. We also study a new partial order on totally symmetric self-complementary plane partitions arising from this perspective and show that this is a distributive lattice related to Bruhat order when restricted to permutations. PubDate: 2018-06-06 DOI: 10.1007/s00026-018-0394-0

Authors:Ginji Hamano; Takayuki Hibi; Hidefumi Ohsugi Abstract: The fractional stable set polytope FRAC(G) of a simple graph G with d vertices is a rational polytope that is the set of nonnegative vectors (x1, . . . , x d ) satisfying x i + xj \({\leq}\) 1 for every edge (i, j) of G. In this paper we show that (i) the \({\delta}\) -vector of a lattice polytope 2FRAC(G) is alternatingly increasing, (ii) the Ehrhart ring of FRAC(G) is Gorenstein, (iii) the coefficients of the numerator of the Ehrhart series of FRAC(G) are symmetric, unimodal and computed by the \({\delta}\) -vector of 2FRAC(G). PubDate: 2018-06-05 DOI: 10.1007/s00026-018-0392-2