Search

Following Karaguezian, Reiner and Wachs we study the connectivity degree and shellability of multiple chessboard complexes. Our central new results provide sharp connectivity bounds relevant to applications in Tverberg type problems where multiple points of the same color are permitted. The results presented in this paper also serve as a foundation for the new results of Tverberg–van Kampen–Flores type, as described in the sequel to this paper. [ABSTRACT FROM AUTHOR]

Abstract: In their paper [6], Dokos et al. conjecture that the major index statistic is equidistributed among 1423-avoiding, 2413-avoiding, and 3214-avoiding permutations. In this paper we confirm this conjecture by constructing two major index preserving bijections, and . In fact, we show that Θ (respectively, Ω) preserves numerous other statistics including the descent set, right-to-left maxima (respectively, left-to-right minima), and a statistic we call steps. Additionally, Θ (respectively, Ω) fixes all permutations avoiding both 1423 and 2413 (respectively, 3214 and 2413). [Copyright &y& Elsevier]

Abstract: This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any graph is representable over all alphabets of size larger than some number depending on the graph. We also provide a characterisation of families representable over a given alphabet. Then, we associate a rank function and a closure operator to any representation which help us determine some criteria for the functions used in a representation. While linearly representable matroids can be viewed as having representations via matrices with only one row, we conclude this paper by an investigation of representations via matrices with only two rows. [Copyright &y& Elsevier]

Abstract: In a recent paper, Duane, Garsia, and Zabrocki introduced a new statistic, “ndinv”, on a family of parking functions. The definition was guided by their study of a recursion on for a Macdonald eigenoperator, a modified Hall–Littlewood operator, and a composition of n. Using their newly introduced statistic, one can give a new interpretation for as a sum of parking functions counted by area and ndinv. This is a departure from the traditional sum, as stated by the shuffle conjecture, which q, t counts area and diagonal inversion number (dinv). Since their definition is necessarily recursive, they pose the problem of obtaining a non-recursive definition. In this paper, we solve this problem by giving an explicit formula for ndinv similar to the classical definition of dinv and prove it is equivalent to the ndinv of Duane, Garsia, and Zabrocki. [Copyright &y& Elsevier]

Abstract: In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation , defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingrímsson proved the analogue of the main result of Backelin, West, and Xin in the context of involutions, and in so doing they needed to prove that commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Mélou and Steingrímsson asked if might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of , by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and . [Copyright &y& Elsevier]

Abstract: In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of alternating sign matrices where the top row as well as the left and the right column is fixed and the number of alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely. [Copyright &y& Elsevier]

Abstract: Let n and k be positive integers, and let F be an alphabet of size n. A sequence over F of length m is a k-radius sequence if any two distinct elements of F occur within distance k of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc in 2004, in order to produce an efficient caching strategy when computing certain functions on large data sets such as medical images. Let be the length of the shortest n-ary k-radius sequence. The paper shows, using a probabilistic argument, that whenever k is fixed and The paper observes that the same argument generalises to the situation when we require the following stronger property for some integer t such that : any t distinct elements of F must simultaneously occur within a distance k of each other somewhere in the sequence. [Copyright &y& Elsevier]

Abstract Let F be a family of 3-uniform linear hypergraphs. The linear Turán number of F is the maximum possible number of edges in a 3-uniform linear hypergraph on n vertices which contains no member of F as a subhypergraph. In this paper we show that the linear Turán number of the five cycle C 5 (in the Berge sense) is 1 3 3 n 3 / 2 asymptotically. We also show that the linear Turán number of the four cycle C 4 and { C 3 , C 4 } are equal asymptotically, which is a strengthening of a theorem of Lazebnik and Verstraëte [16]. We establish a connection between the linear Turán number of the linear cycle of length 2 k + 1 and the extremal number of edges in a graph of girth more than 2 k − 2. Combining our result and a theorem of Collier-Cartaino, Graber and Jiang [8] , we obtain that the linear Turán number of the linear cycle of length 2 k + 1 is Θ (n 1 + 1 k ) for k = 2 , 3 , 4 , 6. [ABSTRACT FROM AUTHOR]

Abstract The 'full' edge isoperimetric inequality for the discrete cube { 0 , 1 } n (due to Harper, Lindsey, Berstein and Hart) specifies the minimum size of the edge boundary ∂ A of a set A ⊂ { 0 , 1 } n , as function of | A |. A weaker (but more widely-used) lower bound is | ∂ A | ≥ | A | log ⁡ (2 n / | A |) , where equality holds whenever A is a subcube. In 2011, the first author obtained a sharp 'stability' version of the latter result, proving that if | ∂ A | ≤ | A | (log ⁡ (2 n / | A |) + ϵ) , then there exists a subcube C such that | A Δ C | / | A | = O (ϵ / log ⁡ (1 / ϵ)). The 'weak' version of the edge isoperimetric inequality has the following well-known generalization for the ' p -biased' measure μ p on the discrete cube: if p ≤ 1 / 2 , or if 0 < p < 1 and A is monotone increasing, then p μ p (∂ A) ≥ μ p (A) log p ⁡ (μ p (A)). In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if p μ p (∂ A) ≤ μ p (A) (log p ⁡ (μ p (A)) + ϵ) , then there exists a subcube C such that μ p (A Δ C) / μ p (A) = O (ϵ ′ / log ⁡ (1 / ϵ ′)) , where ϵ ′ : = ϵ ln ⁡ (1 / p). This result is a central component in recent work of the authors proving sharp stability versions of a number of Erdős–Ko–Rado type theorems in extremal combinatorics, including the seminal 'complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the 'full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the 'full' edge isoperimetric inequality, one relying on the Kruskal–Katona theorem. [ABSTRACT FROM AUTHOR]

Abstract: This paper gives the answer to a question of R.M. Wilson regarding the existence of group divisible designs of large order. Let k and u be positive integers such that . Then there exists an integer such that there exists a group divisible design of group type with block size k and index one for any integer satisfying the necessary arithmetic conditions [1.] , [2.] . This paper also presents a large-index asymptotic existence theorem for group divisible t-designs with a fixed number of groups, fixed group size and fixed block size. [Copyright &y& Elsevier]

Abstract: In this paper we establish an asymptotic existence result for group divisible 3-designs of large order. Let k and u be positive integers, . Then there exists an integer such that there exists a group divisible 3-design of group type with block size k and index one for all integers if and only if [1.] , [2.] , [3.] . An analogous theorem was proved by Mohácsy and Ray-Chaudhuri for group divisible 2-designs in a previously published paper in 2002. The case of this theorem gives an asymptotic existence result for transversal 3-designs which was proved by Blanchard in his unpublished manuscript as well. [Copyright &y& Elsevier]

Abstract: In this paper we present a new 4-dimensional tight Euclidean 5-design on 3 concentric spheres, together with a list of all known tight Euclidean designs which has been updated since the last survey paper by Bannai and Bannai (2009) . We also examine whether each of all known tight Euclidean designs has the structure of a coherent configuration. [ABSTRACT FROM AUTHOR]

Abstract: Difference systems of sets (DSS) were introduced in 1971 by Levenstein for the construction of codes for synchronization, and are closely related to cyclic difference families. In this paper, algebraic constructions of difference systems of sets using functions with optimum nonlinearity are presented. All the difference systems of sets constructed in this paper are perfect and optimal. One conjecture on difference systems of sets is also presented. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to provide the sufficient condition for a mass distribution in to admit an equipartition with a collection of hyperplanes some of which are parallel. The results extend the previously obtained results for the equipartitions with non-parallel hyperplanes. (See [P. Mani-Levitska, S. Vrećica, R. Živaljević, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math. 207 (2006) 266–296; E.A. Ramos, Equipartitions of mass distributions by hyperplanes, Discrete Comput. Geom. 15 (1996) 147–167].) The paper also serves as the illustration of the applicability and the power of the methods of equivariant topology (more precisely, equivariant index theory) in the problems of geometric combinatorics. [Copyright &y& Elsevier]

Abstract: In two previous papers, the study of partitions with short sequences has been developed both for its intrinsic interest and for a variety of applications. The object of this paper is to extend that study in various ways. First, the relationship of partitions with no consecutive integers to a theorem of MacMahon and mock theta functions is explored independently. Secondly, we derive in a succinct manner a relevant definite integral related to the asymptotic enumeration of partitions with short sequences. Finally, we provide the generating function for partitions with no sequences of length K and part exceeding N. [Copyright &y& Elsevier]

Successive ranks of a partition, which were introduced by Atkin, are the difference of the lengths of the i -th row and the i -th column in the Ferrers graph. Recently, in the study of singular overpartitions, Andrews revisited successive ranks and parity blocks. Motivated by his work, we investigate partitions with prescribed successive rank parity blocks. The main result of this paper is the generating function of partitions with exactly d successive ranks and m parity blocks. [ABSTRACT FROM AUTHOR]

Let G be a transitive permutation group of degree n . We say that G is 2′-elusive if n is divisible by an odd prime, but G does not contain a derangement of odd prime order. In this paper we study the structure of quasiprimitive and biquasiprimitive 2′-elusive permutation groups, extending earlier work of Giudici and Xu on elusive groups. As an application, we use our results to investigate automorphisms of finite arc-transitive graphs of prime valency. [ABSTRACT FROM AUTHOR]

In this paper we study a filtered “ K -theoretical” analog of a graded algebra associated to any loopless graph G which was introduced in [5] . We show that two such filtered algebras are isomorphic if and only if their graphs are isomorphic. We also study a large family of filtered generalizations of the latter graded algebra which includes the above “ K -theoretical” analog. [ABSTRACT FROM AUTHOR]

The only known examples of finite generalised hexagons and octagons arise from the finite almost simple groups of Lie type G 2 , D 4 3 , and F 4 2 . These groups act transitively on flags, primitively on points, and primitively on lines. The best converse result prior to the writing of this paper was that of Schneider and Van Maldeghem (2008): if a group G acts flag-transitively, point-primitively, and line-primitively on a finite generalised hexagon or octagon, then G is an almost simple group of Lie type. We strengthen this result by showing that the same conclusion holds under the sole assumption of point-primitivity. [ABSTRACT FROM AUTHOR]

The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an affine slice that projects linearly onto the polytope. The psd rank of a d -polytope is at least d + 1 , and when equality holds we say that the polytope is psd-minimal. In this paper we develop new tools for the study of psd-minimality and use them to give a complete classification of psd-minimal 4-polytopes. The main tools introduced are trinomial obstructions, a new algebraic obstruction for psd-minimality, and the slack ideal of a polytope, which encodes the space of realizations of a polytope up to projective equivalence. Our central result is that there are 31 combinatorial classes of psd-minimal 4-polytopes. We provide combinatorial information and an explicit psd-minimal realization in each class. For 11 of these classes, every polytope in them is psd-minimal, and these are precisely the combinatorial classes of the known projectively unique 4-polytopes. We give a complete characterization of psd-minimality in the remaining classes, encountering in the process counterexamples to some open conjectures. [ABSTRACT FROM AUTHOR]

Over the past twenty years, lecture hall partitions have emerged as fundamental combinatorial structures, leading to new generalizations and interpretations of classical theorems and new results. In recent years, geometric approaches to lecture hall partitions have used polyhedral geometry to discover further properties of these rich combinatorial objects. In this paper we give an overview of some of the surprising connections that have surfaced in the process of trying to understand the lecture hall partitions. [ABSTRACT FROM AUTHOR]

Tropical oriented matroids were defined by Ardila and Develin in 2007. They are a tropical analogue of classical oriented matroids in the sense that they encode the properties of the types of points in an arrangement of tropical hyperplanes — in much the same way as the covectors of “classical” oriented matroids describe the types in arrangements of linear hyperplanes. Ardila and Develin proved that tropical oriented matroids can be represented as mixed subdivisions of dilated simplices. In this paper we show that this correspondence is a bijection. Moreover, tropical analogues for the Topological Representation Theorem for “classical” oriented matroids by Folkman and Lawrence are presented. [ABSTRACT FROM AUTHOR]

Let T ( n ) denote the maximal number of transversals in an order- n Latin square. Improving on the bounds obtained by McKay et al., Taranenko recently proved that T ( n ) ≤ ( ( 1 + o ( 1 ) ) n e 2 ) n , and conjectured that this bound is tight. We prove via a probabilistic construction that indeed T ( n ) = ( ( 1 + o ( 1 ) ) n e 2 ) n . Until the present paper, no superexponential lower bound for T ( n ) was known. We also give a simpler proof of the upper bound. [ABSTRACT FROM AUTHOR]

Bollobás and Scott showed that the vertices of a graph of m edges can be partitioned into k sets such that each set contains at most m / k 2 + o ( m ) edges. They conjectured that the vertices of an r -uniform hypergraph, where r ≥ 3 , of m edges may likewise be partitioned into k sets such that each set contains at most m / k r + o ( m ) edges. In this paper, we prove the weaker statement that a partition into k sets can be found in which each set contains at most m ( k − 1 ) r + r 1 / 2 ( k − 1 ) r / 2 + o ( m ) edges. Some partial results on this conjecture are also given. [ABSTRACT FROM AUTHOR]

The classical Littlewood–Richardson rule is a rule for computing coefficients in many areas, and comes in many guises. In this paper we prove two Littlewood–Richardson rules for symmetric skew quasisymmetric Schur functions that are analogous to the famed version of the classical Littlewood–Richardson rule involving Yamanouchi words. Furthermore, both our rules contain this classical Littlewood–Richardson rule as a special case. We then apply our rules to combinatorially classify symmetric skew quasisymmetric Schur functions. This answers affirmatively a conjecture of Bessenrodt, Luoto and van Willigenburg. [ABSTRACT FROM AUTHOR]

Trace monoids and heaps of pieces appear in various contexts in combinatorics. They also constitute a model used in computer science to describe the executions of asynchronous systems. The design of a natural probabilistic layer on top of the model has been a long standing challenge. The difficulty comes from the presence of commuting pieces and from the absence of a global clock. In this paper, we introduce and study the class of Bernoulli probability measures that we claim to be the simplest adequate probability measures on infinite traces. For this, we strongly rely on the theory of trace combinatorics with the Möbius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems. [ABSTRACT FROM AUTHOR]

The invertibility of Least Common Multiple (LCM) matrices and their Hadamard powers have been extensively studied over the years by many authors. Bourque and Ligh conjectured in 1992 that the LCM matrix [ S ] = [ [ x i , x j ] ] on any GCD closed set S = { x 1 , x 2 , … , x n } is invertible, but in 1997 this was proven to be false. Nevertheless, many open conjectures concerning LCM matrices and their Hadamard powers remain. In this paper we utilize lattice-theoretic structures and the Möbius function to explain the singularity of classical LCM matrices and their Hadamard powers. As a result we disprove some open conjectures of Hong. Elementary mathematical analysis is applied to prove that for most semilattice structures there exists a set S = { x 1 , x 2 , … , x n } of positive integers and a real number α > 0 such that S possesses this structure and the power LCM matrix [ [ x i , x j ] α ] is singular. [ABSTRACT FROM AUTHOR]

Let K be a field, R = K [ X 1 , … , X n ] be the polynomial ring and J ⊊ I be two monomial ideals in R . In this paper we show that sdepth I / J − depth I / J = sdepth I p / J p − depth I p / J p , where sdepth I / J denotes the Stanley depth and I p denotes the polarization. This solves a conjecture by Herzog [9] and reduces the famous Stanley conjecture (for modules of the form I / J ) to the squarefree case. As a consequence, the Stanley conjecture for algebras of the form R / I and the well-known combinatorial conjecture that every Cohen–Macaulay simplicial complex is partitionable are equivalent. [ABSTRACT FROM AUTHOR]

Given a k × l ( 0 , 1 ) -matrix F , we denote by fs ( m , F ) the largest number for which there is an m × fs ( m , F ) ( 0 , 1 ) -matrix with no repeated columns and no induced submatrix equal to F . A conjecture of Anstee, Frankl, Füredi and Pach states that, regarding F as fixed, fs ( m , F ) = O ( m k ) . The main results of this paper are that for k = 2 , fs ( m , F ) = O ( m 2 + o m ( 1 ) ) and for k ≥ 3 that fs ( m , F ) = O ( m ( 5 / 3 ) k − 1 + o m ( 1 ) ) . [ABSTRACT FROM AUTHOR]

In this paper, we prove two conjectures on truncated series. The first conjecture made by G.E. Andrews and M. Merca is related to Jacobi's triple product identity, while the second conjecture by V.J.W. Guo and J. Zeng is related to Jacobi's identity. [ABSTRACT FROM AUTHOR]

Abstract: The crown is a height-2 poset whose Hasse diagram is a cycle of length 2t. A family of subsets of is -free if is not a weak subposet of . Let be the largest size of -free families of subsets of . De Bonis–Katona–Swanepoel proved . Griggs and Lu proved that for all even . In this paper, we prove for all odd . [Copyright &y& Elsevier]

Abstract: We show that a pair of orthogonal partial Latin squares of order n can be embedded in a pair of orthogonal Latin squares of order at most and all orders greater than or equal to . This paper provides the first direct polynomial order embedding construction for pairs of orthogonal partial Latin squares. [Copyright &y& Elsevier]

Abstract: Matt Blum conjectured that the number of tilings of the hexagonal dungeon of sides a, 2a, b, a, 2a, b (where ) is (Propp, 1999 [4]). In this paper we present a proof for this conjecture using Kuo's Graphical Condensation Theorem (Kuo, 2004 [2]). [Copyright &y& Elsevier]

Abstract: The main results of this paper are generalizations of some classical theorems about transversals for families of finite sets to some cases of families of infinite sets. [Copyright &y& Elsevier]

Abstract: A graph X is said to be G-half-arc-transitive if acts transitively on the set of vertices of X and on the set of edges of X but does not act transitively on the set of arcs of X. Such graphs can be studied via corresponding alternets, that is, equivalence classes of the so-called reachability relation, first introduced by Cameron, Praeger and Wormald (1993) in [5]. If the vertex sets of two adjacent alternets either coincide or have half of their vertices in common the graph is said to be tightly attached. In this paper graphs admitting a half-arc-transitive group action with at most five alternets are considered. In particular, it is shown that if the number of alternets is at most three, then the graph is necessarily tightly attached, but there exist graphs with four and graphs with five alternets which are not tightly attached. The exceptional graphs all admit a partition giving the rose window graph on 12 vertices as a quotient graph in case of four alternets, and a particular graph on 20 vertices in the case of five alternets. [Copyright &y& Elsevier]

Abstract: A weak c-colouring of a balanced incomplete block design (BIBD) is a colouring of the points of the design with c colours in such a way that no block of the design has all of its vertices receive the same colour. A BIBD is said to be weakly c-chromatic if c is the smallest number of colours with which the design can be weakly coloured. In this paper we show that for all and with , the obvious necessary conditions for the existence of a -BIBD are asymptotically sufficient for the existence of a weakly c-chromatic -BIBD. [Copyright &y& Elsevier]

Abstract: Linked systems of symmetric designs are equivalent to 3-class Q-antipodal association schemes. Only one infinite family of examples is known, and this family has interesting origins and is connected to important applications. In this paper, we define linking systems, collections of difference sets that correspond to systems of linked designs, and we construct linking systems in a variety of nonelementary abelian groups using Galois rings, partial difference sets, and a product construction. We include some partial results in the final section. [Copyright &y& Elsevier]

Abstract: In 1857, Cayley showed that certain sequences, now called Cayley compositions, are equinumerous with certain partitions into powers of 2. In this paper we give a simple bijective proof of this result and a geometric generalization to equality of Ehrhart polynomials between two convex polytopes. We then apply our results to give a new proof of Braunʼs conjecture proved recently by the authors [15]. [Copyright &y& Elsevier]

Abstract: In this paper we examine the resolvability of infinite designs. We show that in stark contrast to the finite case, resolvability for infinite designs is fairly commonplace. We prove that every t- design with t finite, v infinite and is resolvable and, in fact, has α orthogonal resolutions for each . We also show that, while a t- design with t and λ finite, v infinite and may or may not have a resolution, any resolution of such a design must have v parallel classes containing v blocks and at most parallel classes containing fewer than v blocks. Further, a resolution into parallel classes of any specified sizes obeying these conditions is realisable in some design. When and and when and λ is infinite, we give various examples of resolvable and non-resolvable t- designs. [Copyright &y& Elsevier]

Abstract: Frieze patterns (in the sense of Conway and Coxeter) are in close connection to triangulations of polygons. Broline, Crowe and Isaacs have assigned a symmetric matrix to each polygon triangulation and computed the determinant. In this paper we consider d-angulations of polygons and generalize the combinatorial algorithm for computing the entries in the associated symmetric matrices; we compute their determinants and the Smith normal forms. It turns out that both are independent of the particular d-angulation, the determinant is a power of , and the elementary divisors only take values and 1. We also show that in the generalized frieze patterns obtained in our setting every adjacent -determinant is 0 or 1, and we give a combinatorial criterion for when they are 1, which in the case gives back the Conway–Coxeter condition on frieze patterns. [Copyright &y& Elsevier]

Abstract: In this paper it is shown that there exists a constant such that there do not exist Cameron–Liebler line classes in with parameter x satisfying . This improves all known bounds except for small values of q. [Copyright &y& Elsevier]

Abstract: Let G be a graph with n vertices and m edges and Δ and δ the maximum degree and minimum degree of G. Suppose is the graph obtained from G by attaching pendent edges to each vertex v of G. It is well known that if G is regular (i.e., , ), then the line graph of G, denoted by , has spanning trees, where is the number of spanning trees of G. In this paper, we prove that if G is irregular (i.e., ), then , where s is the number of vertices of degree one in . [Copyright &y& Elsevier]

Abstract: When a v-set can be equipped with a set of k-subsets so that every 2-subset of the v-set appears in exactly (or at most, or at least) one of the chosen k-subsets, the result is a balanced incomplete block design (or packing, or covering, respectively). For each k, balanced incomplete block designs are known to exist for all sufficiently large values of v that meet certain divisibility conditions. When these conditions are not met, one can ask for the packing with the most blocks and/or the covering with the fewest blocks. Elementary necessary conditions furnish an upper bound on the number of blocks in a packing and a lower bound on the number of blocks in a covering. In this paper it is shown that for all sufficiently large values of v, a packing and a covering on v elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on k. [Copyright &y& Elsevier]

Recently, George Andrews investigated a variety of parity questions in classical partition identities. In particular, he involved parity restrictions in the Rogers–Ramanujan–Gordon identities. In this paper, we reveal the relationship of his results with Bressoudʼs generalization of the Rogers–Ramanujan–Gordon identities. In addition, Andrews observed that one case of his identities is related to the Göllnitz–Gordon identities. In the light of the fact that the Göllnitz–Gordon identities are special cases of a general partition theorem of Andrews, we extend Andrewsʼ identities by generalizing his observation. We also provide a generating function of the missing case of his identities. [ABSTRACT FROM AUTHOR]

Abstract: Even though the Oberwolfach problem has been solved for infinitely many orders, no complete solution is known when the number t of tables is fixed, except for . In this paper we solve all Oberwolfach problems (even those with ) with two table lengths. The fundamental step consists of proving Frucht and Salinasʼ conjecture on the gracefulness of a graph that is a vertex-disjoint union of a cycle and a path. [Copyright &y& Elsevier]

Abstract: Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of their polar cones provide external representations containing in general superfluous half-spaces. In this paper, we prove that any tropical polyhedral cone in (also known as “tropical polytope” in the literature) admits an essentially unique minimal external representation. The result is obtained by establishing a (partial) anti-exchange property of half-spaces. Moreover, we show that the apices of the half-spaces appearing in such non-redundant external representations are vertices of the cell complex associated with the polyhedral cone. We also establish a necessary condition for a vertex of this cell complex to be the apex of a non-redundant half-space. It is shown that this condition is sufficient for a dense class of polyhedral cones having “generic extremities”. [Copyright &y& Elsevier]

Abstract: The problem of the existence of large sets of Kirkman triple systems (LKTS) is one of the most celebrated open problems in design theory. Only a few sparsely distributed infinite classes have been determined, although LKTS have been investigated by many authors. The purpose of this paper is to survey constructions and results on LKTS and related designs. A systematic account of this work is provided. Most of the known constructions are unified and generalized; the approaches to LKTS are enriched; a couple of new constructions for related designs are also displayed. In particular, a new existence class of LKTS is demonstrated and some new results of overlarge sets of Kirkman triple systems are also produced. [Copyright &y& Elsevier]

Abstract: The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: . A diamond-free family in the n-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements B and C may or may not be related. There is a diamond-free family in the n-dimensional Boolean lattice of size . In this paper, we prove that any diamond-free family in the n-dimensional Boolean lattice has size at most . Furthermore, we show that the so-called Lubell function of a diamond-free family in the n-dimensional Boolean lattice which contains the empty set is at most , which is asymptotically best possible. [Copyright &y& Elsevier]

Abstract: We derive generating functions for a variety of distributions of joint permutation statistics all of which involve a bound on the maximum drop size of a permutation π, i.e., . Our main result treats the case for the joint distribution of the number of inversions, the number of descents and the maximum drop size of permutations on . A special case of this (ignoring the number of inversions) connects with earlier work of Claesson, Dukes and the authors on descent polynomials for permutations with bounded drop size. In that paper, the desired numbers of permutations were given by sampling the coefficients of certain polynomials . We find a natural interpretation of all the coefficients of the in terms of a restricted version of Eulerian numbers. [Copyright &y& Elsevier]

Abstract: Return words constitute a powerful tool for studying symbolic dynamical systems. They may be regarded as a discrete analogue of the first return map in dynamical systems. In this paper we investigate two abelian variants of the notion of return word, each of them gives rise to a new characterization of Sturmian words. We prove that a recurrent infinite word is Sturmian if and only if each of its factors has two or three abelian (or semi-abelian) returns. We study the structure of abelian returns in Sturmian words and give a characterization of those factors having exactly two abelian returns. Finally we discuss connections between abelian returns and periodicity in words. [Copyright &y& Elsevier]