A well-known discovery of Feige's is the following : Let be nonnegative independent random variables, with , and let . Then for any , for some . This bound was later improved to 1/8 by He, Zhang, and Zhang . By a finer consideration of the first four moments, we further improve the bound to approximately .14. The conjectured true bound is .
We study the values of the Möbius function of intervals in the containment poset of permutations. We construct a sequence of permutations of size for which is given by a polynomial in of degree 7. This construction provides the fastest known growth of in terms of , improving a previous quadratic bound by Smith. Our approach is based on a formula expressing the Möbius function of an arbitrary permutation interval in terms of the number of embeddings of the elements of the interval into .
Let be a simplicial complex with vertices. A missing face of is a simplex such that for any . For a -dimensional simplex in , its degree in is the number of -dimensional simplices in containing it. Let denote the minimal degree of a -dimensional simplex in . Let denote the -Laplacian acting on real -cochains of and let denote its minimal eigenvalue. We prove the following lower bound on the spectral gaps , for complexes without missing faces of dimension larger than : As a consequence we obtain a new proof of a vanishing result for the homology of simplicial complexes without large missing faces. We present a family of examples achieving equality at all dimensions, showing that the bound is tight. For we characterize the equality case.
The distribution of descents in fixed conjugacy classes of has been studied, and it is shown that its moments have interesting properties. Fulman proved that the descent numbers of permutations in conjugacy classes with large cycles are asymptotically normal, and Kim proved that the descent numbers of fixed point free involutions are also asymptotically normal. In this paper, we generalize these results to prove a central limit theorem for descent numbers of permutations in any conjugacy class of .
The interval subdivision of a simplicial complex Δ was introduced by Walker. We give a complete combinatorial description of the entries of the transformation matrices from the - and -vectors of Δ to the - and -vectors of . We show that if Δ has a non-negative -vector then the -polynomial of its interval subdivision has only real roots. As a consequence, we prove the Charney-Davis conjecture for , if Δ has a non-negative reciprocal -vector.
Let be a (level-zero) dominant integral weight for an untwisted affine Lie algebra, and let denote the set of quantum Lakshmibai-Seshadri (QLS) paths of shape . For an element of a finite Weyl group , the specializations at and of the nonsymmetric Macdonald polynomial are explicitly described in terms of QLS paths of shape and the degree function defined on them. Also, for (level-zero) dominant integral weights , , we have an isomorphism of crystals. In this paper, we study the behavior of the degree function under the isomorphism Θ of crystals through the relationship between semi-infinite Lakshmibai-Seshadri (LS) paths and QLS paths. As an application, we give a crystal-theoretic proof of a recursion formula for the graded characters of generalized Weyl modules.
For , let denote the number of numerical semigroups of genus . A conjecture by Maria Bras-Amorós in 2008 states that the inequality holds for all . Here we show that it holds for the very large subtree of numerical semigroups satisfying , where and are the conductor and multiplicity, respectively. Our proof is given in the more flexible setting of , i.e. complements in of numerical semigroups.
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any , the graph of a cubical -polytope with minimum degree is -connected. Second, we show, for any , that every minimum separator of cardinality at most in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself.
Given a simplicial complex and a collection of subcomplexes covering it, the , a fundamental tool in topological combinatorics, guarantees a certain connectivity of the simplicial complex when connectivity conditions on the intersection of the subcomplexes are satisfied. We show that it is possible to extend this theorem by replacing some of these connectivity conditions on the intersection of the subcomplexes by connectivity conditions on their union. While this is interesting for its own sake, we use this extension to generalize in various ways the Meshulam lemma, a powerful homological version of the Sperner lemma. We also prove a generalization of the Meshulam lemma that is somehow reminiscent of the polytopal generalization of the Sperner lemma by De Loera, Peterson, and Su. For this latter result, we use a different approach and we do not know whether there is a way to get it via a nerve theorem of some kind.
A function on standard Young tableaux of size is a function that restricts to the usual descent function when is omitted, such that the number of standard Young tableaux of given shape with cyclic descent set is invariant under any modulo shift of . The notion of cyclic descent was first studied for rectangles by Rhoades, and then generalized to certain families of skew shapes by Adin, Elizalde, and Roichman. Adin, Reiner, and Roichman proved that a skew shape has a cyclic descent map if and only if it is not a connected ribbon. Unfortunately, their proof is nonconstructive; until now, explicit cyclic descent maps are known only for small families of shapes. In this paper, we construct an explicit cyclic descent map for all shapes where this is possible. We thus provide a constructive proof of Adin, Reiner, and Roichman's result. Our construction of a cyclic descent map generalizes many of the constructions in the literature.
The equivalence problem of -linear sets of rank of is investigated, also in terms of the associated variety, projecting configurations, -linear blocking sets of Rédei type and MRD-codes. We call an -linear set of rank in if for any -dimensional -subspace of , is -equivalent to only when and lie on the same orbit of . We prove that defines a simple -linear set for each . We provide examples of non-simple linear sets not of pseudoregulus type for and we prove that all -linear sets of rank 4 are simple in .
The main object of this paper is to determine the maximum number of -vectors subject to the following condition. All vectors have length , exactly of the coordinates are +1 and one is −1, . Moreover, there are no two vectors whose scalar product equals the possible minimum, −2. Thus, this problem may be seen as an extension of the classical Erdős–Ko–Rado theorem. Rather surprisingly there is a phase transition in the behaviour of the maximum at . Nevertheless, our solution is complete. The main tools are from extremal set theory and some of them might be of independent interest.
Let and denote the set of involutions and fixed-point free involutions of , respectively, and let denote the number of descents of the permutation . We prove a conjecture of Guo and Zeng which states that is -positive for and is -positive for . We also prove that the number of -avoiding permutations with double descents and descents is equal to the number of separable permutations with double descents and descents.
Let be a set of by matrices over such that the rank of is at least for all distinct . Suppose that . If , then is a maximum rank distance (MRD for short) code. Until 2016, there were only two known constructions of MRD codes for arbitrary . One was found by Delsarte (1978) and Gabidulin (1985) independently, and it was later generalized by Kshevetskiy and Gabidulin (2005) . We often call them (generalized) Gabidulin codes. Another family was recently obtained by Sheekey (2016) , and its elements are called twisted Gabidulin codes. In the same paper, Sheekey also proposed a generalization of the twisted Gabidulin codes. However the equivalence problem for it is not considered, whence it is not clear whether there exist new MRD codes in this generalization. We call the members of this putative larger family generalized twisted Gabidulin codes. In this paper, we first compute the Delsarte duals and adjoint codes of them, then we completely determine the equivalence between different generalized twisted Gabidulin codes. In particular, it can be proven that, up to equivalence, generalized Gabidulin codes and twisted Gabidulin codes are both proper subsets of this family.
Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős–Ko–Rado theorem.
We present bijections for the planar cases of two counting formulas on maps that arise from the KP hierarchy (Goulden-Jackson and Carrell-Chapuy formulas), relying on a “cut-and-slide” operation. This is the first time a bijective proof is given for quadratic map-counting formulas derived from the KP hierarchy. Up to now, only the linear one-faced case was known (Harer-Zagier recurrence and Chapuy-Féray-Fusy bijection). As far as we know, this bijection is new and not equivalent to any of the well-known bijections between planar maps and tree-like objects.
The quantum chromatic number, , of a graph was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of to prove that many spectral lower bounds for the chromatic number, , are also lower bounds for . This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.
A coloured version of classic extremal problems dates back to Erdős and Rothschild, who in 1974 asked which -vertex graph has the maximum number of 2-edge-colourings without monochromatic triangles. They conjectured that the answer is simply given by the largest triangle-free graph. Since then, this new class of coloured extremal problems has been extensively studied by various researchers. In this paper we pursue the Erdős–Rothschild versions of Sperner's Theorem, the classic result in extremal set theory on the size of the largest antichain in the Boolean lattice, and Erdős' extension to -chain-free families. Given a family of subsets of , we define an of to be an -colouring of the sets without any monochromatic -chains . We prove that for sufficiently large in terms of , the largest -chain-free families also maximise the number of -colourings. We also show that the middle level, , maximises the number of -colourings, and give asymptotic results on the maximum possible number of -colourings whenever is divisible by three.
We prove a conjecture of Reiner, Tenner, and Yong which says that the initial weak order intervals corresponding to certain vexillary permutations have the coincidental down-degree expectations (CDE) property. Actually our theorem applies more generally to certain “skew vexillary” permutations (a notion we introduce), and shows that these posets are in fact “toggle CDE.” As a corollary we obtain a homomesy result for rowmotion acting on semidistributive lattices in the sense of Barnard and of Thomas and Williams.