Search

For a family of subsets of an n-element set, its matching number is the maximum number of pairwise disjoint sets. Families with matching number 1 are called intersecting. The famous Erdős–Ko–Rado theorem determines the size of the largest intersecting family of k-sets. The problem of determining the largest family of k-sets with matching number s > 1 is known under the name of the Erdős Matching Conjecture and is still open for a wide range of parameters. In this paper, we study the degree versions of both theorems. More precisely, we give degree and t-degree versions of the Erdős–Ko–Rado and the Hilton–Milner theorems, extending the results of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in which the degree version of the Erdős Matching Conjecture holds.

In 2016, Ellenberg and Gijswijt employed a method of Croot, Lev, and Pach to show that a maximal cap in A G ( n , q ) has size O ( q c n ) for some c 1 . In this paper, we show more generally that if S is a subset of A G ( n , q ) containing no m points on any ( m − 2 ) -flat, then | S | q c m n for some c m 1 , as long as q is odd or m is even.

The polynomiality of shifted Plancherel averages for summations of contents of strict partitions were established by the authors and Matsumoto independently in 2015, which is the key to determining the limit shape of random shifted Young diagram, as explained by Matsumoto. In this paper, we prove the polynomiality of shifted Plancherel averages for summations of hook lengths of strict partitions, which is an analog of the authors and Matsumoto's results on contents of strict partitions. In 2009, the first author proved the Nekrasov-Okounkov formula on hook lengths for integer partitions by using an identity of Macdonald in the framework of type A ˜ affine root systems, and conjectured that the Plancherel averages of some summations over the set of all partitions of size n are always polynomials in n. This conjecture was generalized and proved by Stanley. Recently, Petreolle derived two Nekrasov-Okounkov type formulas for C ˜ and C ˜ ˇ which involve doubled distinct and self-conjugate partitions. Inspired by all those previous works, we establish the polynomiality of t-Plancherel averages of some hook-content summations for doubled distinct and self-conjugate partitions.

Cylindric skew Schur functions, a generalization of skew Schur functions, are closely related to the well-known problem of finding a combinatorial formula for the 3-point Gromov-Witten invariants of Grassmannians. In this paper, we prove cylindric Schur positivity of cylindric skew Schur functions, as conjectured by McNamara. We also show that all the coefficients appearing in the expansion are the same as the 3-point Gromov-Witten invariants. We start by discussing the properties of affine Stanley symmetric functions for general affine permutations and 321-avoiding affine permutations, and we explain how these functions are related to cylindric skew Schur functions. In addition, we provide an effective algorithm to compute the expansion of cylindric skew Schur functions in terms of cylindric Schur functions, as well as the expansion of affine Stanley symmetric functions in terms of affine Schur functions.

We formulate three current models of discrete-time quantum walks in a combinatorial way. These walks are shown to be closely related to rotation systems and 1-factorizations of graphs. For two of the models, we compute the traces and total entropies of the average mixing matrices for some cubic graphs. The trace captures how likely a quantum walk is to revisit the state it started with, and the total entropy measures how close the limiting distribution is to uniform. Our numerical results indicate three relations between quantum walks and graph structures: for the first model, rotation systems with higher genera give lower traces and higher entropies, and for the second model, the symmetric 1-factorizations always give the highest trace.

We compute the elementary divisors of the adjacency and Laplacian matrices of families of polar graphs. These graphs have as vertices the isotropic one-dimensional subspaces of finite vector spaces with respect to non-degenerate forms, with adjacency given by orthogonality.

In this paper we describe an infinite family of Cameron–Liebler line classes of PG ( 3 , q ) with parameter ( q 2 + 1 ) / 2 , q ≡ 1 ( mod 4 ) . The example obtained admits PGL ( 2 , q ) as an automorphism group and it is shown not to be isomorphic to any of the infinite families known so far whenever q ≥ 9 .

In this paper, we study γ-positivity of descent-type polynomials by introducing the change of context-free grammars method. We first present a unified grammatical proof of the γ-positivity of Eulerian polynomials, type B Eulerian polynomials, derangement polynomials, Narayana polynomials and type B Narayana polynomials. We then provide partial γ-positive expansions for several multivariate polynomials associated to Stirling permutations, Legendre-Stirling permutations, Jacobi-Stirling permutations and type B derangements. The recurrence relations for the partial γ-coefficients of these expansions are also obtained. By using some variants of the Foata-Strehl group action, we provide combinatorial interpretations for the coefficients of most of these partial γ-positive expansions.

In 1967, Andrews found a combinatorial generalization of the Gollnitz-Gordon theorem, which can be called the Andrews-Gollnitz-Gordon theorem. In 1980, Bressoud derived a multisum Rogers-Ramanujan-type identity, which can be considered as the generating function counterpart of the Andrews-Gollnitz-Gordon theorem. Lovejoy gave an overpartition analogue of the Andrews-Gollnitz-Gordon theorem for i = k . In this paper, we give an overpartition analogue of this theorem for k ≥ i ≥ 1 . By using Bailey's lemma and a change of base formula due to Bressoud, Ismail and Stanton, we obtain an overpartition analogue of Bressoud's identity. We then give a combinatorial interpretation of this identity by introducing the Gollnitz-Gordon marking of an overpartition, which yields an overpartition analogue of the Andrews-Gollnitz-Gordon theorem.

The notion of covering type was recently introduced by Karoubi and Weibel to measure the complexity of a topological space by means of good coverings. When X has the homotopy type of a finite CW-complex, its covering type coincides with the minimum possible number of vertices of a simplicial complex homotopy equivalent to X. In this article we compute the covering type of all closed surfaces. Our results completely settle a problem posed by Karoubi and Weibel, and shed more light on the relationship between the topology of surfaces and the number of vertices of minimal triangulations from a homotopy point of view., 6 pages

We evaluate a curious determinant, first mentioned by George Andrews in 1980 in the context of descending plane partitions. Our strategy is to combine the famous Desnanot-Jacobi-Dodgson identity with automated proof techniques. More precisely, we follow the holonomic ansatz that was proposed by Doron Zeilberger in 2007. We derive a compact and nice formula for Andrews's determinant, and use it to solve a challenge problem that we posed in a previous paper. By noting that Andrews's determinant is a special case of a two-parameter family of determinants, we find closed forms for several one-parameter subfamilies. The interest in these determinants arises because they count cyclically symmetric rhombus tilings of a hexagon with several triangular holes inside.

Relying on the combinatorial classification of toric ideals using their bouquet structure, we focus on toric ideals of hypergraphs and study how they relate to general toric ideals. We show that hypergraphs exhibit a surprisingly general behavior: the toric ideal associated to any general matrix can be encoded by that of a 0/1 matrix, while preserving the essential combinatorics of the original ideal. We provide two universality results about the unboundedness of degrees of various generating sets: minimal, Graver, universal Grobner bases, and indispensable binomials. Finally, we provide a polarization-type operation for arbitrary positively graded toric ideals, which preserves all the combinatorial signatures and the homological properties of the original toric ideal.

An ordered graph H is a graph with a linear ordering on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex ( n , H ) of edges in an ordered graph on n vertices that does not contain H as an ordered subgraph. It is known that ex ( n , H ) > n 1 + e for some positive e = e ( H ) unless H is a forest that has a bipartition V 1 ∪ V 2 such that V 1 totally precedes V 2 in the ordering. Making progress towards a conjecture of Pach and Tardos, we prove that ex ( n , H ) = n 1 + o ( 1 ) holds for all such forests that are “degenerate” in a certain sense. This class includes every forest for which an n 1 + o ( 1 ) upper bound was previously known, as well as new examples. For example, the class contains all forests with | V 1 | ≤ 3 . Our proof is based on a density-increment argument.

In this paper, we describe the recurrence relation associated to the sum of diagonal elements lying along a finite ray of certain type crossing the three-dimensional Pascal pyramid. Then we determine the corresponding generating function. Finally, we deal with the so-called Morgan–Voyce phenomenon, and applying the new arguments we prove an identity, which makes it possible to prove several recurrence relations conjectured in Sloane's On-Line Encyclopedia of Integer Sequences.

Let I n and J n denote the set of involutions and fixed-point free involutions of { 1 , … , n } , respectively, and let des ( π ) denote the number of descents of the permutation π. We prove a conjecture of Guo and Zeng which states that I n ( t ) : = ∑ π ∈ I n t des ( π ) is γ-positive for n ≥ 1 and J 2 n ( t ) : = ∑ π ∈ J 2 n t des ( π ) is γ-positive for n ≥ 9 . We also prove that the number of ( 3412 , 3421 ) -avoiding permutations with m double descents and k descents is equal to the number of separable permutations with m double descents and k descents.

We give new bounds and asymptotic estimates for Kronecker and Littlewood–Richardson coefficients. Notably, we resolve Stanley's questions on the shape of partitions attaining the largest Kronecker and Littlewood–Richardson coefficients. We apply the results to asymptotics of the number of standard Young tableaux of skew shapes.

In this paper, we present a lattice-theoretic characterization for valuated matroids, which is an extension of the well-known cryptomorphic equivalence between matroids and geometric lattices ($=$ atomistic semimodular lattices). We introduce a class of semimodular lattices, called uniform semimodular lattices, and establish a cryptomorphic equivalence between integer-valued valuated matroids and uniform semimodular lattices. Our result includes a coordinate-free lattice-theoretic characterization of integer points in tropical linear spaces, incorporates the Dress-Terhalle completion process of valuated matroids, and establishes a smooth connection with Euclidean buildings of type A., Comment: To appear in Journal of Combinatorial Theory A

We compute the number of X -variables (also called coefficients) of a cluster algebra of finite type when the underlying semifield is the universal semifield. For classical types, these numbers arise from a bijection between coefficients and quadrilaterals (with a choice of diagonal) appearing in triangulations of certain marked surfaces. We conjecture that similar results hold for cluster algebras from arbitrary marked surfaces, and obtain corollaries regarding the structure of finite type cluster algebras of geometric type.

In [33] , the authors introduced a new basis of the ring of symmetric functions which evaluate to the irreducible characters of the symmetric group at roots of unity. The structure coefficients for this new basis are the stable Kronecker coefficients. In this paper we give combinatorial descriptions for several products. In addition, we identify some applications and instances where special cases of these products have occurred elsewhere in the mathematical literature.

We consider a generalization of the classical game of Nim called hypergraph Nim . Given a hypergraph H on the ground set V = { 1 , … , n } of n piles of stones, two players alternate in choosing a hyperedge H ∈ H and strictly decreasing all piles i ∈ H . The player who makes the last move is the winner. In 1980 Jenkyns and Mayberry obtained an explicit formula for the Sprague–Grundy function of the hypergraph Nim whose hypergraph contains as the hyperedges all proper subsets of V (that is, all except ∅ and V itself). Somewhat surprisingly, the same formula works for a very wide family of hypergraphs. In this paper we characterize symmetric hypergraphs in this family.

In this paper, we first determine the minimum possible size of an F q -linear set of rank k in PG ( 1 , q n ) . We obtain this result by relating it to the number of directions determined by a linearized polynomial whose domain is restricted to a subspace. We then use this result to find a lower bound on the number of points in an F q -linear set of rank k in PG ( 2 , q n ) . In the case k = n , this confirms a conjecture by Sziklai in [9] .

In 2012, N. Williams and the second author showed that on order ideals of ranked partially ordered sets (posets), rowmotion is conjugate to (and thus has the same orbit structure as) a different toggle group action, which in special cases is equivalent to promotion on linear extensions of posets constructed from two chains. In 2015, O. Pechenik and the first and second authors extended these results to show that increasing tableaux under K-promotion naturally corresponds to order ideals in a product of three chains under a toggle group action conjugate to rowmotion they called hyperplane promotion. In this paper, we generalize these results to the setting of arbitrary increasing labelings of any finite poset with given restrictions on the labels. We define a generalization of K-promotion in this setting and show it corresponds to a toggle group action we call toggle-promotion on order ideals of an associated poset. When the restrictions on labels are particularly nice (for example, specifying a global bound on all labels used), we show that toggle-promotion is conjugate to rowmotion. Additionally, we show that any poset that can be nicely embedded into a Cartesian product has a natural toggle-promotion action conjuate to rowmotion., 29 pages, 14 figures

We study a family of polynomials associated with ascent–descent statistics on labeled rooted plane k-ary trees introduced by Gessel, from a rook-theoretic perspective. We generalize the excedance statistic on permutations to maximal nonattacking rook placements on certain rectangular boards by decomposing them into staircase boards. We then relate the number of maximal nonattacking rook placements on certain skew boards to the number of regions in extended Linial arrangements by establishing a relation between the factorial polynomial of those boards to the characteristic polynomial of extended Linial arrangements. Furthermore, we give a combinatorial interpretation of the number of bounded regions in extended Linial arrangements in terms of certain labeled rooted plane k-ary trees. Finally, using the work of Goldman–Joichi–White, we identify graphs whose chromatic polynomials equal the characteristic polynomials of extended Linial arrangements up to a straightforward normalization.

The `full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary $\partial A$ of a set $A \subset \{0,1\}^n$, as a function of $|A|$. A weaker (but more widely-used) lower bound is $|\partial A| \geq |A| \log_2(2^n/|A|)$, where equality holds iff $A$ is a subcube. In 2011, the first author obtained a sharp `stability' version of the latter result, proving that if $|\partial A| \leq |A| (\log(2^n/|A|)+\epsilon)$, then there exists a subcube $C$ such that $|A \Delta C|/|A| = O(\epsilon /\log(1/\epsilon))$. The `weak' version of the edge isoperimetric inequality has the following well-known generalization for the `$p$-biased' measure $\mu_p$ on the discrete cube: if $p \leq 1/2$, or if $0 < p < 1$ and $A$ is monotone increasing, then $p\mu_p(\partial A) \geq \mu_p(A) \log_p(\mu_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\mu_p(\partial A) \leq \mu_p(A) (\log_p(\mu_p(A))+\epsilon)$, then there exists a subcube $C$ such that $\mu_p(A \Delta C)/\mu_p(A) = O(\epsilon' /\log(1/\epsilon'))$, where $\epsilon' =\epsilon \ln (1/p)$. This result is a central component in recent work of the authors proving sharp stability versions of a number of Erd\H{o}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., Comment: 36 pages. More explanations added, and minor corrections made, in response to referee comments

It is well known that many geometric properties of Schubert varieties of type A (and others) can be interpreted combinatorially. Given two permutations w , x ∈ S n we give a combinatorial consequence of the property that the smooth locus of the Schubert variety X w contains the Schubert cell Y x . This provides a necessary ingredient for the interpretation of recent representation-theoretic results of the author with Minguez in terms of identities of Kazhdan–Lusztig polynomials.

Fix a field $k$. When $\Delta$ is a simplicial complex on $n$ vertices with Stanley-Reisner ideal $I_\Delta$, we define and study an invariant called the $\textit{type defect}$ of $\Delta$. Except when $\Delta$ is of a single simplex, the type defect of $\Delta$, $\textrm{td}(\Delta)$, is the difference $ \dim_k \textrm{Tor}_c^S(S/ I_\Delta,k) - c$, where $c$ is the codimension of $\Delta$ and $S = k[x_1, \ldots x_n]$. We show that this invariant admits surprisingly nice properties. For example, it is well-behaved when one glues two complexes together along a face. Furthermore, $\Delta$ is Cohen-Macaulay if $\textrm{td}(\Delta) \leq 0$. On the other hand, if $\Delta$ is a simple graph (viewed as a one-dimensional complex), then $\textrm{td}(\Delta') \geq 0$ for every induced subgraph $\Delta'$ of $\Delta$ if and only if $\Delta$ is chordal. Requiring connected induced subgraphs to have type defect zero allows us to define a class of graphs that we call $\textit{treeish}$, and which we generalize to simplicial complexes. We then extend some of our chordality results to higher dimensions, proving sharp lower bounds for most Betti numbers of ideals with linear resolution, and classifying when equalities occur. As an application, we prove sharp lower bounds for Betti numbers of graded ideals (not necessarily monomial) with linear resolution., Comment: Several minor changes were made following suggestions by referees. Final version

Let Sym denote the algebra of symmetric functions and $P_\mu(\,\cdot\,;q,t)$ and $Q_\mu(\,\cdot\,;q,t)$ be the Macdonald symmetric functions (recall that they differ by scalar factors only). The $(q,t)$-Cauchy identity $$ \sum_\mu P_\mu(x_1,x_2,\dots;q,t)Q_\mu(y_1,y_2,\dots;q,t)=\prod_{i,j=1}^\infty\frac{(x_iy_jt;q)_\infty}{(x_iy_j;q)_\infty} $$ expresses the fact that the $P_\mu(\,\cdot\,;q,t)$'s form an orthogonal basis in Sym with respect to a special scalar product $\langle\,\cdot\,,\,\cdot\,\rangle_{q,t}$. The present paper deals with the inhomogeneous \emph{interpolation} Macdonald symmetric functions $$ I_\mu(x_1,x_2,\dots;q,t)=P_\mu(x_1,x_2,\dots;q,t)+\text{lower degree terms}. $$ These functions come from the $N$-variate interpolation Macdonald polynomials, extensively studied in the 90's by Knop, Okounkov, and Sahi. The goal of the paper is to construct symmetric functions $J_\mu(\,\cdot\,;q,t)$ with the biorthogonality property $$ \langle I_\mu(\,\cdot\,;q,t), J_\nu(\,\cdot\,;q,t)\rangle_{q,t}=\delta_{\mu\nu}. $$ These new functions live in a natural completion of the algebra Sym. As a corollary one obtains a new Cauchy-type identity in which the interpolation Macdonald polynomials are paired with certain multivariate rational symmetric functions. The degeneration of this identity in the Jack limit is also described., Comment: v2: the notation of dual functions changed in accordance with reviewer's suggestion; a few typos fixed; three unnecessary references deleted from the list; to appear in J. Combin. Theory Ser. A

In this paper we investigate the permanent of ( − 1 , 1 ) -matrices over fields of zero characteristics and our main goal is to provide a sharp upper bound for the value of the permanent of such matrices depending on matrix rank, solving Wang's problem posed in 1974 by confirming Krauter conjecture formulated in 1985.

We show that despite the proofs of both lemmas presented by Paulhus in 1998 are incorrect, the Paulhus' bounds given for three well known Moser's packing problems are valid.

Whitney's broken circuit theorem gives a graphical example of reducing the number of the terms in the sum of the inclusion–exclusion formula by a predicted cancellation. So far, the known cancellations for the formula strongly depend on the prescribed (linear or partial) ordering on the index set. We give a new cancellation method, which does not require any ordering on the index set. Our method extends all the ‘ordering-based’ methods known in the literature and in general reduces more terms. As examples, we use our method to improve some results on graph polynomials.

We study $321$-avoiding affine permutations, and prove a formula for their enumeration with respect to the inversion number by using a combinatorial approach. This is done in two different ways, both related to Viennot's theory of heaps. First, we encode these permutations using certain heaps of monomers and dimers. This method specializes to the case of affine involutions. For the second proof, we introduce periodic parallelogram polyominoes, which are new combinatorial objects of independent interest. We enumerate them by extending the approach of Bousquet-M\'elou and Viennot used for classical parallelogram polyominoes. We finally establish a connection between these new objects and $321$-avoiding affine permutations., Comment: 25 pages, 17 figures

Noncrossing arc diagrams are combinatorial models for the equivalence classes of the lattice congruences of the weak order on permutations. In this paper, we provide a general method to endow these objects with Hopf algebra structures. Specific instances of this method produce relevant Hopf algebras that appeared earlier in the literature., 15 pages, 6 figures; Version 2: exposition improvements

We prove the following conjecture of Leighton and Moitra. Let $T$ be a tournament on $[n]$ and $S_n$ the set of permutations of $[n]$. For an arc $uv$ of $T$, let $A_{uv}=\{\sigma \in S_n \, : \, \sigma(u)0$, if $\mathbb{P}$ is a probability distribution on $S_n$ such that $\mathbb{P}(A_{uv})>1/2+\varepsilon$ for every arc $uv$ of $T$, then the binary entropy of $\mathbb{P}$ is at most $(1-\vartheta_{\varepsilon})\log_2 n!$ for some (fixed) positive $\vartheta_\varepsilon$. When $T$ is transitive the theorem is due to Leighton and Moitra; for this case we give a short proof with a better $\vartheta_\varepsilon$., Comment: 10 pages

Symmetric Grothendieck polynomials are analogues of Schur polynomials in the K-theory of Grassmannians. We build dual families of symmetric Grothendieck polynomials using Schur operators. With this approach we prove skew Cauchy identity and then derive various applications: skew Pieri rules, dual filtrations of Young's lattice, generating series and enumerative identities. We also give a new explanation of the finite expansion property for products of Grothendieck polynomials.

We prove the conjectures of F. Brenti, P. Mongelli and P. Sentinelli which give a combinatorial interpretation to the parabolic Kazhdan–Lusztig polynomials of type −1 for quasi-minuscule quotients of the Weyl groups of type B n and D n .

In the theory of finite type Vassiliev knot invariants, the universal sl 2 weight system maps the chord diagrams to polynomials in a single variable with integer coefficients. In this paper, we define a family of polynomials that generalize the Kreweras triangle (known to refine the normalized median Genocchi numbers), and we show how it appears in this weight system.

Given $R \subseteq \mathbb{N}$ let ${n \brace k}_R$, ${n \brack k}_R$, and $L(n,k)_R$ be the number of ways of partitioning the set $[n]$ into $k$ non-empty subsets, cycles and lists, respectively, with each block having cardinality in $R$. We refer to these as the $R$-restricted Stirling numbers of the second and first kind and the $R$-restricted Lah numbers, respectively. Note that the classical Stirling numbers of the second kind and first kind, and Lah numbers are ${n \brace k} = {n \brace k}_{\mathbb{N}}$, ${n \brack k} = {n \brack k}_{\mathbb{N}} $ and $L(n,k) = L(n,k)_{\mathbb{N}}$, respectively. The matrices $[{n \brace k}]_{n,k \geq 1}$, $[{n \brack k}]_{n,k \geq 1}$ and $[L(n,k)]_{n,k \geq 1}$ have inverses $[(-1)^{n-k}{n \brack k}]_{n,k \geq 1}$, $[(-1)^{n-k} {n \brace k}]_{n,k \geq 1}$ and $[(-1)^{n-k} L(n,k)]_{n,k \geq 1}$ respectively. The inverse matrices $[{n \brace k}_R]^{-1}_{n,k \geq 1}$, $[{n \brack k}_R]^{-1}_{n,k \geq 1}$ and $[L(n,k)_R]^{-1}_{n,k \geq 1}$ exist if and only if $1 \in R$. We express each entry of each of these matrices as the difference between the cardinalities of two explicitly defined families of labeled forests. In particular the entries of $[{n \brace k}_{[r]}]^{-1}_{n,k \geq 1}$ have combinatorial interpretations, affirmatively answering a question of Choi, Long, Ng and Smith from 2006. If $1,2 \in R$ and if for all $n \in R$ with $n$ odd and $n \geq 3$, we have $n \pm 1 \in R$, we additionally show that each entry of $[{n \brace k}_R]^{-1}_{n,k \geq 1}$, $[{n \brack k}_R]^{-1}_{n,k \geq 1}$ and $[L(n,k)_R]^{-1}_{n,k \geq 1}$ is up to an explicit sign the cardinality of a single explicitly defined family of labeled forests. Our results also provide combinatorial interpretations of the $k$th Whitney numbers of the first and second kinds of $\Pi_n^{1,d}$, the poset of partitions of $[n]$ that have each part size congruent to $1$ mod $d$., Comment: This is a substantial revision of version 1, with more extensive results and unified proofs, as well as with new connections to certain Whitney numbers

In this paper, we establish several results concerning chains in Y X , the lattice of mappings from a finite set X into a finite totally ordered set Y. We compute the total number and the cardinalities of several collections of chains. As a byproduct we determine the total number of chained Y-fuzzy topologies defined on X. Several related and other well known results are obtained as corollaries. Also some natural questions are presented for further investigations.

We completely classify non-spanning $3$-polytopes, by which we mean lattice $3$-polytopes whose lattice points do not affinely span the lattice. We show that, except for six small polytopes (all having between five and eight lattice points), every non-spanning $3$-polytope $P$ has the following simple description: $P\cap \mathbb{Z}^3$ consists of either (1) two lattice segments lying in parallel and consecutive lattice planes or (2) a lattice segment together with three or four extra lattice points placed in a very specific manner. From this description we conclude that all the empty tetrahedra in a non-spanning $3$-polytope $P$ have the same volume and they form a triangulation of $P$, and we compute the $h^*$-vectors of all non-spanning $3$-polytopes. We also show that all spanning $3$-polytopes contain a unimodular tetrahedron, except for two particular $3$-polytopes with five lattice points., 20 pages. Changes from v2: small changes requested by journal referee; corrected typos in Thm 1.3; updated references

Ryser's Conjecture states that for any r-partite r-uniform hypergraph, the vertex cover number is at most r − 1 times the matching number. This conjecture is only known to be true for r ≤ 3 in general and for r ≤ 5 if the hypergraph is intersecting. There has also been considerable effort made for finding hypergraphs that are extremal for Ryser's Conjecture, i.e. r-partite hypergraphs whose cover number is r − 1 times its matching number. Aside from a few sporadic examples, the set of uniformities r for which Ryser's Conjecture is known to be tight is limited to those integers for which a projective plane of order r − 1 exists. We produce a new infinite family of r-uniform hypergraphs extremal to Ryser's Conjecture, which exists whenever a projective plane of order r − 2 exists. Our construction is flexible enough to produce a large number of non-isomorphic extremal hypergraphs. In particular, we define what we call the Ryser poset of extremal intersecting r-partite r-uniform hypergraphs and show that the number of maximal and minimal elements is exponential in r . This provides further evidence for the difficulty of Ryser's Conjecture.

In this paper we use the geometry of finite planes to set up a procedure for the construction of one-factorisations of the complete graph. Let π be a projective plane of order n − 1 with n even containing an oval Ω, and regard Ω as the vertex set of the complete graph K n . Then any one-factorisation of K n has a representation by a partition of the external points to Ω whose components are of size n 2 and meet every tangent to Ω in a unique point. Our goal is to construct such partitions from nice geometric configurations in the Desarguesian plane of order q with q = p h and p > 2 prime.

Let $G\cong \mathbb Z/m_1\mathbb Z\times\ldots\times \mathbb Z/m_r\mathbb Z$ be a finite abelian group with $m_1\mid\ldots\mid m_r=\exp(G)$. The Kemperman Structure Theorem characterizes all subsets $A,\,B\subseteq G$ satisfying $|A+B, Comment: Revised version, with results reworded to appear less technical

In this paper, we classify commutative weakly distance-regular digraphs of valency 3 with girth more than 2 and one type of arcs. Combining [8, Theorem 1.2] , [10, Theorem 1.3] and [11, Theorem 1] , commutative weakly distance-regular digraphs of valency 3 are completely determined.

Recently, G.E. Andrews and M. Merca considered specializations of the Rogers–Fine identity and obtained partition-theoretic interpretations of two truncated identities of Gauss solving a problem by V.J.W. Guo and J. Zeng. In this paper, we provide purely combinatorial proofs of these results.

We study two different one-parameter generalizations of Littlewood–Richardson coefficients, namely Hall polynomials and generalized inverse Kostka polynomials, and derive new combinatorial formulae for them. Our combinatorial expressions are closely related to puzzles, originally introduced by Knutson and Tao in their work on the equivariant cohomology of the Grassmannian.

Let $\mathcal{C}$ be a set of $m$ by $n$ matrices over $\mathbb{F}_q$ such that the rank of $A-B$ is at least $d$ for all distinct $A,B\in \mathcal{C}$. Suppose that $m\leqslant n$. If $\#\mathcal{C}= q^{n(m-d+1)}$, then $\mathcal{C}$ is a maximum rank distance (MRD for short) code. Until 2016, there were only two known constructions of MRD codes for arbitrary $1, Comment: One missing case (n=4) has been included in the appendix. Typos are corrected, Journal of Combinatorial Theory, Series A, 2018

The Kneser graph ${\rm KG}_{n,k}$ is a graph whose vertex set is the family of all $k$-subsets of $[n]$ and two vertices are adjacent if their corresponding subsets are disjoint. The classical Erd\H{o}s-Ko-Rado theorem determines the cardinality and structure of a maximum induced $K_2$-free subgraph in ${\rm KG}_{n,k}$. As a generalization of the Erd\H{o}s-Ko-Rado theorem, Erd\H{o}s proposed a conjecture about the maximum order of an induced $K_{s+1}$-free subgraph of ${\rm KG}_{n,k}$. As the best known result concerning this conjecture, Frankl [Journal of Combinatorial Theory, Series A, 2013], when $n\geq(2s+1)k-s$, gave an affirmative answer to this conjecture and also determined the structure of such a subgraph. In this paper, generalizing the Erd\H{o}s-Ko-Rado theorem and the Erd{\H o}s matching conjecture, we consider the problem of determining the structure of a maximum family $\mathcal{A}$ for which ${\rm KG}_{n,k}[\mathcal{A}]$ has no subgraph isomorphic to a given graph $G$. In this regard, we determine the size and the structure of such a family provided that $n$ is sufficiently large with respect to $G$ and $k$. Furthermore, for the case $G=K_{1,t}$, we present a Hilton-Milner type theorem regarding above-mentioned problem, which specializes to an improvement of a result by Gerbner et al. [SIAM Journal on Discrete Mathematics, 2012]., Comment: Minor changes

The group G ( m , 1 , n ) consists of n-by-n monomial matrices whose entries are mth roots of unity. It is generated by n complex reflections acting on C n . The reflecting hyperplanes give rise to a (hyperplane) arrangement G ⊂ C n . The internal zonotopal algebra of an arrangement is a finite dimensional algebra first studied by Holtz and Ron. Its dimension is the number of bases of the associated matroid with zero internal activity. In this paper we study the structure of the internal zonotopal algebra of the Gale dual of the reflection arrangement of G ( m , 1 , n ) , as a representation of this group. Our main result is a formula for the top degree component as an induced representation. We also provide results on representation stability, a connection to the Whitehouse representation in type A, and an analog of decreasing trees in type B.

Le-diagrams are combinatorial objects that parametrize cells of the totally nonnegative Grassmannian, called positroid cells, and each Le-diagram gives rise to a cluster algebra which is believed to be isomorphic to the coordinate ring of the corresponding positroid variety. We study quivers arising from these diagrams and show that they can be constructed from the well-behaved quivers associated to Grassmannians by deleting and merging certain vertices. Then, we prove that quivers coming from arbitrary Le-diagrams, and more generally reduced plabic graphs, admit a particular sequence of mutations called a green-to-red sequence., Comment: 16 pages, 11 figures

We study lines through the origin of finite-dimensional complex vector spaces that enjoy a doubly transitive automorphism group. In doing so, we make fundamental connections with both discrete geometry and algebraic combinatorics. In particular, we show that doubly transitive lines are necessarily optimal packings in complex projective space, and we introduce a fruitful generalization of regular abelian distance-regular antipodal covers of the complete graph.