A family of -element subsets of is called a -simplex-cluster if , , and the intersection of any of the sets in is nonempty. In 2010, Keevash and Mubayi conjectured that for any , the largest family of -element subsets of that does not contain a -simplex-cluster is the family of all -subsets that contain a given element. We prove the conjecture for all for an arbitrarily small , provided that . We call a family of -element subsets of a -cluster if and . We also show that for any the largest family of -element subsets of that does not contain a -cluster is again the family of all -subsets that contain a given element, provided that . Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.
The of a (naturally labeled) poset is a quasisymmetric function enumerating order-preserving maps from to . Using the Hopf algebra of posets, we give necessary conditions for two posets to have the same generating function. In particular, we show that they must have the same number of antichains of each size, as well as the same shape (as defined by Greene). We also discuss which shapes guarantee uniqueness of the -partition generating function and give a method of constructing pairs of non-isomorphic posets with the same generating function.
As shown by Bousquet-Mélou–Claesson–Dukes–Kitaev (2010), ascent sequences can be used to encode -free posets. It is known that ascent sequences are enumerated by the Fishburn numbers, which appear as the coefficients of the formal power series In this paper, we present a novel way to recursively decompose ascent sequences, which leads to: This work is motivated by a double Eulerian equidistribution of Foata (1977) and a tempting bi-symmetry conjecture, which asserts that the quadruples and are equidistributed on ascent sequences.
Let be the standard -element set, its power set. The size of a family is the number of sets . In the present paper we consider the more equitable measurement where the contribution of each is . In particular, . Our main result is that for every positive integer , implies the existence of pairwise disjoint members in . Moreover, this is best possible for all . A classical result of Kleitman is an easy consequence. The relatively simple proofs seem to indicate that is the right measurement for such problems.
We study “holomorphic quadratic differentials” on graphs. We relate them to the reactive power in an LC circuit, and also to the chromatic polynomial of a graph. Specifically, we show that the chromatic polynomial of a graph , at negative integer values, can be evaluated as the degree of a certain rational mapping, arising from the defining equations for a holomorphic quadratic differential. This allows us to give an explicit integral expression for .
We continue the study by Melo and Winter (2019) on the possible intersection sizes of a -dimensional subspace with the vertices of the -dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than (the “large” sizes) are of the form . We show that this is almost true: the large intersection sizes are either of this form or of the form . We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.
In this paper we compute the dimension of the Grassmann embeddings of the polar Grassmannians associated to a possibly degenerate Hermitian, alternating or quadratic form with possibly non-maximal Witt index. Moreover, in the characteristic 2 case, when the form is quadratic and non-degenerate with bilinearization of minimal Witt index, we define a generalization of the so-called Weyl embedding (see ) and prove that the Grassmann embedding is a quotient of this generalized ‘Weyl-like’ embedding. We also estimate the dimension of the latter.
In this paper, we study quantum modular forms in connection to quantum invariants of plumbed 3-manifolds introduced recently by Gukov, Pei, Putrov, and Vafa. We explicitly compute these invariants for any 3-leg star plumbing graphs whose associated matrix is unimodular and positive definite. For these graphs we confirm a quantum modularity conjecture of Gukov. We also analyze the invariants for general -leg star graphs with unimodular plumbing matrices, and prove that they can be expressed as linear combinations of quantum modular forms.
In this paper, we present a number of results surrounding Caselli's conjecture on the equidistribution of the major index with sign over the two subsets of permutations of containing respectively the word and the word as a subsequence, under a parity condition of and . We derive broader bijective results on permutations containing varied subsequences. As a consequence, we obtain the signed mahonian identities on families of restricted permutations, in the spirit of a well-known formula of Gessel–Simion, covering a combinatorial proof of Caselli's conjecture. We also derive an extension of the insertion lemma of Han and Haglund–Loehr–Remmel which allows us to obtain a signed enumerator of the major-index increments resulting from the insertion of a pair of consecutive numbers in any place of a given permutation.
A Diophantine -tuple with property , where is a non-zero integer, is a set of positive integers such that is a perfect square for all . It is known that exists and is . In this paper, we show that the Paley graph conjecture implies that the upper bound can be improved to , for any .
The closure of a generic torus orbit in the flag variety of type is known to be a permutohedral variety and well studied. In this paper we introduce the notion of a generic torus orbit in the Schubert variety and study its closure . We identify the maximal cone in the fan of corresponding to a fixed point , associate a graph to each , and show that is smooth at if and only if is a forest. We also introduce a polynomial for each , which agrees with the Eulerian polynomial when is the longest element of , and show that the Poincaré polynomial of agrees with when is smooth.
Big Ramsey degrees of finite structures are usually considered with respect to a Fraïssé limit. The only available strategy to prove that a Fraïssé limit supports finite big Ramsey degrees was suggested by Sauer in 2006 and relies on representing structures by binary trees and then invoking Milliken's Theorem. In this paper we consider structures which are Fraïssé limits, and still have the property that their finite substructures have finite big Ramsey degrees in them. For example, the class of all finite acyclic oriented graphs is not a Fraïssé age, and yet we show that there is a countably infinite acyclic oriented graph in which every finite acyclic oriented graph has finite big Ramsey degree. Our approach to proving this and a few more statements of similar kind is based on a new strategy of transporting the property from one category of structures to another using the machinery of category theory.
We study the tropicalization of intersections of plane curves, under the assumption that they have the same tropicalization. We show that the set of tropical divisors that arise in this manner is a pure dimensional balanced polyhedral complex and compute its dimension. When the genus is at most 1, we show that all the tropical divisors that move in the expected dimension are realizable. As part of the proof, we introduce a combinatorial tool for explicitly constructing large families of realizable tropical divisors.
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.
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 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 .