Authors:Olivier Bodini; Danièle Gardy; Bernhard Gittenberger; Zbigniew Gołębiewski Pages: 45 - 91 Abstract: We investigate various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions concerning the unary nodes or abstractions, respectively: we either bound their number or the allowed levels of nesting. The enumeration is done by means of a generating function approach and singularity analysis. The generating functions are composed of nested square roots and exhibit unexpected phenomena in some of the cases. Furthermore, we present some observations obtained from generating such terms randomly and explain why usually powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms. PubDate: 2018-03-01 DOI: 10.1007/s00026-018-0371-7 Issue No:Vol. 22, No. 1 (2018)

Authors:Sarah K. Mason; Elizabeth Niese Pages: 167 - 199 Abstract: We introduce a quasisymmetric generalization of Berele and Regev’s hook Schur functions and prove that these new quasisymmetric hook Schur functions decompose the hook Schur functions in a natural way. We examine the combinatorics of the quasisymmetric hook Schur functions, providing a relationship to Gessel’s fundamental quasisymmetric functions and an analogue of the Robinson-Schensted-Knuth algorithm. We also prove that the multiplication of quasisymmetric hook Schur functions with hook Schur functions behaves the same as the multiplication of quasisymmetric Schur functions with Schur functions. PubDate: 2018-03-01 DOI: 10.1007/s00026-018-0376-2 Issue No:Vol. 22, No. 1 (2018)

Authors:Lior Fishman; Keith Merrill; David Simmons Abstract: Intrinsic Diophantine approximation on fractals, such as the Cantor ternary set, was undoubtedly motivated by questions asked by K. Mahler (1984). One of the main goals of this paper is to develop and utilize the theory of infinite de Bruijn sequences in order to answer closely related questions. In particular, we prove that the set of infinite de Bruijn sequences in \({k \geq 2}\) letters, thought of as a set of real numbers via a decimal expansion, has positive Hausdorff dimension. For a given k, these sequences bear a strong connection to Diophantine approximation on certain fractals. In particular, the optimality of an intrinsic Dirichlet function on these fractals with respect to the height function defined by symbolic representations of rationals follows from these results. PubDate: 2018-04-27 DOI: 10.1007/s00026-018-0384-2

Authors:A. Stoimenow Abstract: In relation to a conjecture of Hoste on the roots of the Alexander polynomial of alternating knots, we prove that any root z of the Alexander polynomial of a 2-bridge (rational) knot or link satisfies \({ z^{1/2}-z^{-1/2} < 2}\) . We extend our result to properties of zeros for some Montesinos knots, and to an analogous statement about the skein polynomial. A similar estimate is derived for alternating 3-braid links. PubDate: 2018-04-27 DOI: 10.1007/s00026-018-0389-x

Authors:Patrick G. Cesarz; Robert S. Coulter Abstract: Neo-difference sets arise in the study of projective planes of Lenz-Barlotti types I.3 and I.4. In the course of their proof that an abelian neo-difference set of order 3n satisfies either n = 1 or 3 n, Ghinelli and Jungnickel produce a Wilbrink-like equation for neo-difference sets of order 3n. In this note we generalise that part of their proof to produce a version of this equation that holds for all neo-difference sets. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0382-4

Authors:Cristian-Silviu Radu Abstract: In this paper, we present an algorithm which can prove algebraic relations involving \({\eta}\) -quotients, where \({\eta}\) is the Dedekind eta function. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0388-y

Authors:Shu Xiao Li Abstract: The immaculate functions, \({\mathfrak{S}_a}\) , were introduced as a Schur-like basis for NSym, the ring of noncommutative symmetric functions. We investigate their structure constants. These are analogues of Littlewood-Richardson coefficents. We will give a new proof of the left Pieri rule for the \({\mathfrak{S}_a}\) , a translation invariance property for the structure coefficients of the \({\mathfrak{S}_a}\) , and a counterexample to an \({\mathfrak{S}_a}\) -analogue of the saturation conjecture. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0386-0

Authors:Guo-Niu Han; Huan Xiong Abstract: Motivated by the Nekrasov-Okounkov formula on hook lengths, the first author conjectured that the Plancherel average of the 2k-th power sum of hook lengths of partitions with size n is always a polynomial of n for any \({k \in \mathbb{N}}\) . This conjecture was generalized and proved by Stanley (Ramanujan J. 23(1–3), 91–105 (2010)). In this paper, inspired by the work of Stanley and Olshanski on the differential poset of Young lattice, we study the properties of two kinds of difference operators D and \({D^{-}}\) defined on functions of partitions. Even though the calculations for higher orders of D are extremely complex, we prove that several wellknown families of functions of partitions are annihilated by a power of the difference operator D. As an application, our results lead to several generalizations of classic results on partitions, including the marked hook formula, Stanley Theorem, Okada-Panova hook length formula, and Fujii-Kanno-Moriyama-Okada content formula. We insist that the Okada constants K r arise directly from the computation for a single partition \({\lambda}\) , without the summation ranging over all partitions of size n. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0385-1

Authors:Bart De Bruyn Abstract: We characterize the valuations of the near polygon \({\mathbb{H}_n}\) that are induced by classical valuations of the dual polar space \({DW(2n-1, 2)}\) into which it is isometrically embeddable. An application to near 2n-gons that contain \({\mathbb{H}_n}\) as a full subgeometry is given. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0383-3

Authors:Jakob Ablinger; Carsten Schneider Abstract: Indefinite nested sums are important building blocks to assemble closed forms for combinatorial counting problems or for problems that arise, e.g., in particle physics. Concerning the simplicity of such formulas an important subtask is to decide if the arising sums satisfy algebraic relations among each other. Interesting enough, algebraic relations of such formal sums can be derived from combinatorial quasi-shuffle algebras. We will focus on the following question: can one find more relations if one evaluates these sums to sequences and looks for relations within the ring of sequences. In this article we consider the sequences of the rather general class of (cyclotomic) harmonic sums and show that their relations coincide with the relations found by their underlying quasi-shuffle algebra. In order to derive this result, we utilize the quasi-shuffle algebra and construct a difference ring with the following property: (1) the generators of the difference ring represent (cyclotomic) harmonic sums, (2) they generate within the ring all (cyclotomic) harmonic sums, and (3) the sequences produced by the generators are algebraically independent among each other. This means that their sequences do not satisfy any polynomial relations. The proof of this latter property is obtained by difference ring theory and new symbolic summation results. As a consequence, any sequence produced by (cyclotomic) harmonic sums can be formulated within our difference ring in an optimal way: there does not exist a subset of the arising sums in which the sequence can be formulated as polynomial expression. PubDate: 2018-04-23 DOI: 10.1007/s00026-018-0381-5

Authors:Wenwen Fan; Cai Heng Li; Hai Peng Qu Abstract: We show that a complete bipartite graph \({{\bf K}_{{p^e}, p_{f}}}\) , where p is an odd prime, has an edge-transitive embedding in an orientable surface with all faces bounded by simple cycles if and only if e = f. There are exactly \({p^{2(e-1)}}\) such embeddings up to isomorphism. Among them, \({p^{e-1}}\) are orientably regular, one of which is reflexible and \({p^{e-1} -1}\) form chiral pairs. The remaining \({p^{2(e-1)} - p^{e-1}}\) embeddings are non-regular (not arc-transitive). All of these embeddings have genus \({\frac{1}{2} (p^{e}-1) (p^{e}-2)}\) . PubDate: 2018-02-05 DOI: 10.1007/s00026-018-0373-5

Authors:Padraig Ó Catháin Abstract: In this short note we construct codes of length 4n with 8n+8 codewords and minimum distance 2n−2 whenever 4n+4 is the order of a Hadamard matrix. This generalises work of Constantine who obtained a similar result in the special case that n is a prime power. PubDate: 2018-02-05 DOI: 10.1007/s00026-018-0379-z

Authors:Igor E. Shparlinski Abstract: We give efficient constructions of reasonably small dominating sets of various types in a circulant graph on n notes and k distinct chord lengths. The structure of a cyclic group underlying circulant graph makes them suitable for applications of methods of analytic number theory. In particular, our results are based on bounds on some double exponential sums. PubDate: 2018-02-05 DOI: 10.1007/s00026-018-0377-1

Authors:Emily Barnard; Emily Meehan; Nathan Reading; Shira Viel Abstract: We construct universal geometric coefficients for the cluster algebra associated to the four-punctured sphere and obtain, as a by-product, the g-vectors of cluster variables. We also construct the rational part of the mutation fan. These constructions rely on a classification of the allowable curves (the curves which can appear in quasi-laminations). The classification allows us to prove the Null Tangle Property for the four-punctured sphere, thus adding this surface to a short list of surfaces for which this property is known. The Null Tangle Property then implies that the shear coordinates of allowable curves are the universal coefficients. We compute shear coordinates explicitly to obtain universal geometric coefficients. PubDate: 2018-02-05 DOI: 10.1007/s00026-018-0378-0

Authors:Soojin Cho; Kyoungsuk Park Abstract: A symmetry of (t, q)-Eulerian numbers of type B is combinatorially proved by defining an involution preserving many important statistics on the set of permutation tableaux of type B, which solves the problem suggested by Corteel in [12]. This involution also proves a symmetry of the generating polynomial \({\hat{D}_{n,k} (p, q, r)}\) of the numbers of crossings and alignments, and hence q-Eulerian numbers of type A defined by Lauren K.Williams. By considering a restriction of our bijection, we were led to define a new statistic on the permutations of type D and (t, q)-Eulerian numbers of type D, which is proved to have a particular symmetry as well. We conjecture that our new statistic is in the family of Eulerian statistics for the permutations of type D. PubDate: 2018-02-05 DOI: 10.1007/s00026-018-0372-6

Authors:Rebecca L. Jayne; Kailash C. Misra Abstract: For \({\ell \geq 1}\) and \({k \geq 2}\) , we consider certain admissible sequences of k−1 lattice paths in a colored \({\ell \times \ell}\) square. We show that the number of such admissible sequences of lattice paths is given by the sum of squares of the number of standard Young tableaux of shape \({\lambda \vdash \ell}\) with \({l(\lambda) \leq k}\) , which is also the number of (k + 1)k··· 21-avoiding permutations in \({S_\ell}\) . Finally, we apply this result to the representation theory of the affine Lie algebra \({\widehat{sl}(n)}\) and show that this gives the multiplicity of certain maximal dominant weights in the irreducible highest weight \({\widehat{sl}(n)}\) -module \({V(k \Lambda_0)}\) . PubDate: 2018-02-02 DOI: 10.1007/s00026-018-0374-4

Authors:David B. Leep; Claus Schubert Abstract: We calculate the dimensions of the intersections of maximal subspaces of zeros of a nonsingular pair of quadratic forms. We then count the number of sets of distinct such subspaces that intersect in a given dimension. PubDate: 2018-02-01 DOI: 10.1007/s00026-018-0375-3

Authors:Antonio Bernini; Luca Ferrari Abstract: We introduce vincular pattern posets, then we consider in particular the quasiconsecutive pattern poset, which is defined by declaring σ ≤ τ whenever the permutation τ contains an occurrence of the permutation σ in which all the entries are adjacent in τ except at most the first and the second. We investigate the Möbius function of the quasi-consecutive pattern poset and we completely determine it for those intervals [σ, τ] such that σ occurs precisely once in τ. PubDate: 2017-08-21 DOI: 10.1007/s00026-017-0364-y

Authors:Mikhail Mazin Abstract: Pak and Stanley introduced a labeling of the regions of a k-Shi arrangement by k-parking functions and proved its bijectivity. Duval, Klivans, and Martin considered a modification of this construction associated with a graph G. They introduced the G-Shi arrangement and a labeling of its regions by G-parking functions. They conjectured that their labeling is surjective, i.e., that every G-parking function appears as a label of a region of the G-Shi arrangement. Later Hopkins and Perkinson proved this conjecture. In particular, this provided a new proof of the bijectivity of Pak-Stanley labeling in the k = 1 case. We generalize Hopkins-Perkinson’s construction to the case of arrangements associated with oriented multigraphs. In particular, our construction provides a simple straightforward proof of the bijectivity of the original Pak-Stanley labeling for arbitrary k. PubDate: 2017-08-21 DOI: 10.1007/s00026-017-0368-7

Authors:G. Lunardon; G. Marino; O. Polverino; R. Trombetti Abstract: In this paper, elaborating on the link between semifields of dimension n over their left nucleus and \({\mathbb{F}s}\) -linear sets of rank en disjoint from the secant variety \({\Omega(\mathcal{S}_{n,n})}\) of the Segre variety \({\mathcal{S}_{n,n}}\) of \({PG(n^2-1, q), q=s^e}\) , we extend some operations on semifield whose definition relies on dualising the relevant linear set. PubDate: 2017-08-07 DOI: 10.1007/s00026-017-0362-0