Sequentially congruent partitions and partitions into squares

The Ramanujan Journal - In recent work, M. Schneider and the first author studied a curious class of integer partitions called “sequentiallyc congruent” partitions: the mth part is...     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.     

Gaussian partitions

Let V=V(n,q) denote the finite vector space of dimension n over the finite field with q elements. A subspace partition of V is a collection Π of subspaces of V such that each 1-dimensional subspace of V is in exactly one subspace of Π. In a recent paper, we proved some strong connections between the lattice of the subspace partitions of V and the lattice of the set partitions of n={1,…,n}. We now define a Gaussian partition of [n] _q =(q ⁿ −1)/(q−1) to be a nonincreasing sequence of positive integers formed by ordering all elements of some multiset {dim(W):W∈Π}, where Π is a subspace partition of V. The Gaussian partition function gp(n,q) is then the number of all Gaussian partitions of [n] _q , and is naturally analogous to the classical partition function p(n). In this paper, we initiate the study of gp(n,q) by exhibiting all Gaussian partitions for small n. In particular, we determine gp(n,q) as a polynomial in q for n≤5, and find a lower bound for gp(6,q).     

Balanced partitions

A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. We begin by establishing a less well-known companion result, which states that both of these quantities are equal to the number of partitions of n into even parts along with exactly one triangular part. We then introduce the characteristic of a partition, which is determined in a simple way by the placement of odd parts within the list of all parts. This leads to a refinement of the aforementioned result in the form of a new type of partition identity involving characteristic, distinct parts, even parts, and triangular numbers. Our primary purpose is to present a bijective proof of the central instance of this new type of identity, which concerns balanced partitions—partitions in which odd parts occupy as many even as odd positions within the list of all parts. The bijection is accomplished by means of a construction that converts balanced partitions of 2n into unrestricted partitions of n via a pairing of the squares in the Young tableau.     

Dominance method for plane partitions III-flagged skew plane partitions

This paper investigates the enumerative problems of flagged skew plane partitions in which each row (column) has an upper and a lower bounds on the entries. By means of dominance technique, a direct and elementary derivation for their generating functions is presented which may be more accessible to readers.     

Multidimensional Farey partitions

The linear action of SL(n, ?₊) induces lattice partitions on the (n − 1)-dimensional simplex †n−1. The notion of Farey partition raises naturally from a matricial interpretation of the arithmetical Farey sequence of order r. Such sequence is unique and, consequently, the Farey partition of order r on A 1 is unique. In higher dimension no generalized Farey partition is unique. Nevertheless in dimension 3 the number of triangles in the various generalized Farey partitions is always the same which fails to be true in dimension n > 3. Concerning Diophantine approximations, it turns out that the vertices of an n-dimensional Farey partition of order r are the radial projections of the lattice points in ?₊ⁿ ∩ [0, r]ⁿ whose coordinates are relatively prime. Moreover, we obtain sequences of multidimensional Farey partitions which converge pointwisely.     

Baer subgeometry partitions

For any odd integern 3 and prime powerq, it is known thatPG(n–1, q²) can be partitioned into pairwise disjoint subgeometries isomorphic toPG(n–1, q) by taking point orbits under an appropriate subgroup of a Singer cycle ofPG(n–1, q²). In this paper, we construct Baer subgeometry partitions of these spaces which do not arise in the classical manner. We further illustrate some of the connections between Baer subgeometry partitions and several other areas of combinatorial interest, most notably projective sets and flagtransitive translation planes.     

On graphical partitions

An integer partition {₁,₂,..., _v } is said to be graphical if there exists a graph with degree sequence _i . We give some results corcerning the problem of deciding whether or not almost all partitions of even integer are non-graphical. We also give asymptotic estimates for the number of partitions with given rank.     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

Nonobtuse tetrahedral partitions

We show how to generate refinements of tetrahedral partitions, where no obtuse angles appear. Such partitions play an important role in deriving discrete maximum principles and maximum norm error estimates for the finite element method. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 327–334, 2000     

Weighted cylindric partitions

Journal of Algebraic Combinatorics - Recently Corteel and Welsh outlined a technique for finding new sum-product identities by using functional relations between generating functions for cylindric...     

Acyclic dominating partitions

Given a graph G=(V, E), let ${\mathcal{P}}$ be a partition of V. We say that ${\mathcal{P}}$ is dominating if, for each part P of ${\mathcal{P}}$, the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that ${\mathcal{P}}$ is acyclic if for any parts P, P′ of ${\mathcal{P}}$, the bipartite subgraph G[P, P′] consisting of the edges between P and P′ in ${\mathcal{P}}$ contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3)=2, which establishes a conjecture of P. Boiron, É. Sopena, and L. Vignal, DIMACS/DIMATIA Conference “Contemporary Trends in Discrete Mathematics”, 1997, pp. 1–10. For general d, we prove the upper bound ad(d)=O(dlnd) and a lower bound of ad(d)=Ω(d). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292–311, 2010     

Recursion over partitions

The paper demonstrates how to apply a recursion on the fundamental concept of number. We propose a generalization of the partitions of a positive integer n, by defining new combinatorial objects, namely sub-partitions. A recursive formula is suggested, designated to solve the associated enumeration problem. It is highlighted that sub-partitions provide a good language to study rooted phylogenetic trees.     

Double perfect partitions

MacMahon [Combinatory Analysis, vols. I and II, Cambridge University Press, Cambridge, 1915, 1916 (reprinted, Chelsea, 1960)] introduced a perfect partition of positive integer n, which is a partition such that every positive integer less than or equal to n can be uniquely represented by the sum of its parts. We generalize perfect partition and find a relation with ordered factorizations.     

On random partitions

Let S be a finite set with n labeled elements. One of the partitions of S is selected at random each of them has the same probability. Harper determined the expected number of subsets in the random partition. Haigh studied the probability that the random partition has (at least one) subset of a given size. The present paper considers the expected number of subsets in a given size. Average and maximum are also determined. Results are generalized for the case if the number of subsets in the partition is also fixed.     

Parity results for 13-regular partitions and broken 6-diamond partitions

Let \(b_{13}(n)\) denote the number of partitions of n such that no parts are divisible by 13. In this paper, we shall prove several infinite families of congruence relations modulo 2 for \(b_{13}(n)\). In addition, we will give an elementary proof of the parity result on broken 6-diamond partitions, which was established by Radu and Sellers. We also find a new congruence relation modulo 2 for the number of broken 6-diamond partitions of n.     

Results on Bent Functions

In this paper, we present three results on bent functions: a construction, a restriction, and a characterization. Starting with a single bent function, in a simple but very effective way, the construction produces a large number of new bent functions in the same number of variables. The restriction imposes new conditions on the directional derivatives of bent functions. Certain non-existence results that were previously obtained through computer search follow easily from these conditions. The characterization describes bent functions as certain solutions of a system of quadratic equations. Interesting new properties of bent functions are obtained using the characterization.