Determining a matroid polytope by non-Radon partitions

Intrinsic characterizations of the faces of a matroid polytope from various subcollections of circuits or the family of its non-Radon partitions are given. Furthermore, it is proved that the characterization from the family of non-Radon partitions is strong enough to give algorithms for determining the faces of every nonsingular permissible projective transformation of a convex polytope.     

Localizing combinatorial properties of partitions

The purpose of this paper is to develop a framework for the analysis of combinatorial properties of partitions. Our focus is on the relation between global properties of partitions and their localization to subpartitions. First, we study properties that are characterized by their local behavior. Second, we determine sufficient conditions for classes of partitions to have a member that has a given property. These conditions entail the possibility of being able to move from an arbitrary partition in the class to one that satisfies the given property by sequentially satisfying local variants of the property. We apply our approach to several properties of partitions that include consecutiveness, nestedness, order-consecutiveness, full nestedness and balancedness, and we demonstrate its usefulness in determining the existence of optimal partitions that satisfy such properties.     

A combinatorial perspective on the Radon convexity theorem

Matroid-theoretic methods are employed to compute the number of complementary subsets of points of a set S whose convex hulls intersect (a number Radon proved to be nonzero when S has an affine dependency). This number is shown to be an invariant only of the dependence structure of S. Strict bounds are given depending on the cardinality and dimension of S and the number is related to other matroid invariants.     

A geometric perspective on counting non-negative integer solutions and combinatorial identities

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.     

A note on hypercube partitions

Two methods of partitioning an n-dimensional hypercube are considered. In the first method, referred to as the Stirling partitioning, we define l-dimensional partitions (l-partitions) which are defined in the 2-dimensional case by x₁ < x₂, x₂ < x₁, and x₂ = x₁. We show that (n ? k)-partitions are enumerated by the numbers T_n^k = (n ? k)! S_n^n?k, where S_n^n?k is the Stirling number of the second kind. In the second method, referred to as the Eulerian partitioning, we define k-boundary n-partitions as unions of n-partitions with their (n ?1)-through(n ? k)-partition boundaries. In the 2-dimensional case the 0 and 1 boundary 2-partitions are x₁ < x₂, x₂ ? x₁. We show that k boundary n-partitions are enumerated by the Eulerian numbers E_n^k. We apply these results to several combinatorial identities.     

A theorem on the cores of partitions

If s and t are relatively prime positive integers we show that the s-core of a t-core partition is again a t-core partition. A similar result is proved for bar partitions under the additional assumption that s and t are both odd.     

Some combinatorial properties of hook lengths, contents, and parts of partitions

The main result of this paper is a generalization of a conjecture of Guoniu Han, originally inspired by an identity of Nekrasov and Okounkov. Our result states that if F is any symmetric function (say over ?) and if $$\Phi_n(F)=\frac{1}{n!}\sum_{\lambda\vdash n}f_\lambda^2F(h_u^2:u\in\lambda),$$ where h _u denotes the hook length of the square u of the partition λ of n and f _λ is the number of standard Young tableaux of shape λ, then Φ _n (F) is a polynomial function of n. A similar result is obtained when F(h _u ² :u∈λ) is replaced with a function that is symmetric separately in the contents c _u of λ and the shifted parts λ _i +n?i of λ.     

A poset structure on quasifibonacci partitions

In this paper, we study partitions of positive integers into distinct quasifibonacci numbers. A digraph and poset structure is constructed on the set of such partitions. Furthermore, we discuss the symmetric and recursive relations between these posets. Finally, we prove a strong generalization of Robbins' result on the coefficients of a quasifibonacci power series.     

A note on path kernels and partitions

The detour order of a graph G, denoted by τ(G), is the order of a longest path in G. A subset S of V(G) is called a P_n-kernel of G if τ(G[S])≤n−1 and every vertex v∈V(G)−S is adjacent to an end-vertex of a path of order n−1 in G[S]. A partition of the vertex set of G into two sets, A and B, such that τ(G[A])≤a and τ(G[B])≤b is called an (a,b)-partition of G. In this paper we show that any graph with girth g has a P_n+1-kernel for every . Furthermore, if τ(G)=a+b, 1≤a≤b, and G has girth greater than , then G has an (a,b)-partition.     

Counting partitions on the abacus

In 2003, Maróti showed that one could use the machinery of ℓ-cores and ℓ-quotients of partitions to establish lower bounds for p(n), the number of partitions of n. In this paper we explore these ideas in the case ℓ=2, using them to give a largely combinatorial proof of an effective upper bound on p(n), and to prove asymptotic formulae for the number of self-conjugate partitions, and the number of partitions with distinct parts. In a further application we give a combinatorial proof of an identity originally due to Gauss. Dedicated to the memory of Dr. Manfred Schocker (1970–2006)     

A note on the upper bound for disjoint convex partitions

Let n(k, l,m), k ≤ l ≤ m, be the smallest integer such that any finite planar point set which has at least n(k, l,m) points in general position, contains an empty convex k-hole, an empty convex l-hole and an empty convex m-hole, in which the three holes are pairwise disjoint. In this article, we prove that n(4, 4, 5) ≤ 16.     

A skein action of the symmetric group on noncrossing partitions

We introduce and study a new action of the symmetric group \({\mathfrak {S}}_n\) on the vector space spanned by noncrossing partitions of \(\{1, 2,\ldots , n\}\) in which the adjacent transpositions \((i, i+1) \in {\mathfrak {S}}_n\) act on noncrossing partitions by means of skein relations. We characterize the isomorphism type of the resulting module and use it to obtain new representation-theoretic proofs of cyclic sieving results due to Reiner–Stanton–White and Pechenik for the action of rotation on various classes of noncrossing partitions and the action of K-promotion on two-row rectangular increasing tableaux. Our skein relations generalize the Kauffman bracket (or Ptolemy relation) and can be used to resolve any set partition as a linear combination of noncrossing partitions in a \({\mathfrak {S}}_n\)-equivariant way.     

A combinatorial proof of a combinatorial theorem

Acta Mathematica Hungarica -     

A polynomial dual of partitions

Let P(x) = Σ_i=0ⁿa_ixⁱ be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where a_i of these points have degree i for 0≤i≤n. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G₁ × … × G_k having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical.     

A note on Pall partitions over finite fields

A Pall partition for a quadratic space V is a collection of disjoint (except for {0}) maximal totally isotropic subspaces whose union contains all of the isotropic vectors in V. In this paper it is shown that no non-degenerate quadratic space of dimension 4k+1, k?1, over a finite field of odd characteristic can have a Pall partition. The method of proof consists of assuming such a partition exists and showing by various counting arguments that this leads to the existence of an impossible array of ordered pairs.