Unique Path Partitions: Characterization and Congruences

We give a complete classification of the unique path partitions and study congruence properties of the function which enumerates such partitions.     

Perfect Partitions of Convex Sets in the Plane

   Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Perfect Partitions of Convex Sets in the Plane

Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Parametrized Partitions of Products of Finite Sets*

For every infinite sequence of positive integers and every Borel partition c : ×[]{0, 1} there is H[] and a sequence of subsets of , with |H_i|=m_i for every i, such that c is constant on .* Research partially supported by CNRS-FONACIT Project PI 2000001471. This author thanks the University of Paris VII for hospitality.     

Diference Systems of Sets Based on Cosets Partitions

Diference systems of sets(DSS) are combinatorial confgurations that arise in connection with code synchronization. This paper proposes a new method to construct DSSs, which uses known DSSs to partition some of the cosets of Zνrelative to subgroup of order k, where ν = km is a composite number. As applications, we obtain some new optimal DSSs.     

Popularity of Sets Represented by the Partitions of n

Let us say that a partition of the positive integer n represents a, 0 a n, if there is a submultiset of the multiset of the parts whose sum is a. Erd os and Szalay have proved that almost all partitions of n represent all integers a, 0 a n. If is a finite set of positive integers, let us denote by p~(n, ) the number of partitions of n which represent all integers a, 0 a n, a , n – a but do not represent a for a . For instance, p~(n,) is the number of partitions of n which represent all integers between 0 and n; the result of Erd os and Szalay can be reformulated as p~(n,) p(n), where p(n) is the total number of partitions of n. The aim of this paper is the study of p~(n, ): we shall compare the values of p~(n, ) for small sets and we shall give a close formula for p~(n, ) when is the set of the first k integers.     

关于整数集分拆的一个猜测的证明

设n为正整数,记rn=m ax{正整数m:可将集合{1,2,…,m}分为n个子集,使得在每一子集中方程xy=z(x>1,y>1)均无解}.高楠和刘红艳(数学的实践与认识,2005,35(5):151—152)给出了rn的一个下界估计rn n9,并猜测对任意给定的正整数k,当n充分大时有rn nk.本文对此猜测给以肯定回答,并证明了如下更强的结论:对任意给定的正整数k 4,当n>3k时有rn n2k+1.     

Path Factors and Neighborhoods of Independent Sets in Graphs

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_≥k-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_≥k-factor covered graph if for any e∈E(G),G has a P_≥k-factor including e.Let β be a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ) a k-connected graph G of order n with n≥5k+2 has a P_≥3...     

Jagged Partitions

By jagged partitions we refer to an ordered collection of non-negative integers (n₁, n₂,..., n_m) with n_m≥ p for some positive integer p, further subject to some weakly decreasing conditions that prevent them for being genuine partitions. The case analyzed in greater detail here corresponds to p = 1 and the following conditions n_i≥ n_i+1−1 and n_i≥ n_i+2. A number of properties for the corresponding partition function are derived, including rather remarkable congruence relations. An interesting application of jagged partitions concerns the derivation of generating functions for enumerating partitions with special restrictions, a point that is illustrated with various examples. 2000 Mathematics Subject Classification: Primary—05A15, 05A17, 05A19     

Cylindric Partitions

A new object is introduced into the theory of partitions that generalizes plane partitions: cylindric partitions. We obtain the generating function for cylindric partitions of a given shape that satisfy certain row bounds as a sum of determinants of -binomial coefficients. In some special cases these determinants can be evaluated. Extending an idea of Burge (J. Combin. Theory Ser. A 63 (1993), 210-222), we count cylindric partitions in two different ways to obtain several known and new summation and transformation formulas for basic hypergeometric series for the affine root system . In particular, we provide new and elementary proofs for two basic hypergeometric summation formulas of Milne (Discrete Math. 99 (1992), 199-246).

     

Partitions of multisets

A multiset is a set with repeated elements. There are four distinct partition numbers to consider, unlike the classical set partition case which involves only Stirling numbers of the second kind. Using inclusion-exclusion, we obtain generating functions when each element appears exactly r = 1, 2 or 3 times. The case r = 1 is classical and r = 2 was studied by Comtet and Baróti using other methods. Our approach also leads to asymptotic formulae for the total number of partitions of multisets in which the repetition of elements is bounded. Another approach to multiset enumeration, using de Brujin's theorem for group reduced distributions, is described.     

Large Sets of Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs

In this paper, we determine the existence spectrums for large sets of Hamilton cycle and path (resp. directed Hamilton cycle and path) decompositions of ??K _{m, n} (resp. ${\lambda K^{*}_{m,n}}$ ).     

Jean-Louis Nicolas and the Partitions

A survey of Jean-Louis Nicolas’s papers on partitions is given.Dedicated to Jean-Louis Nicolas on the occasion of his 60th birthdayPartially supported by the Hungarian National Foundation for Scientific Research, Grant No. T 029759.2000 Mathematics Subject Classification: Primary—11P81     

Balanced Graph Partitions

We prove that the set of vertices V, |V| = rk, of a connected graph G can be split into r subsets of the same cardinality in such a way that the distance between any vertex of G and any subset of the partition is at most r.     

Lecture Hall Partitions

We prove a finite version of the well-known theorem that says that the number of partitions of an integer N into distinct parts is equal to the number of partitions of N into odd parts. Our version says that the number of lecture hall partitions of length n of N equals the number of partitions of N into small odd parts: 1,3,5, ldots, 2n-1 . We give two proofs: one via Bott's formula for the Poincaré series of the affine Coxeter group , and one direct proof.     

Gap-Free Set Partitions

A set partition is called “gap-free” if its block sizes form an interval. In other words, there is at least one block of each size between the smallest and largest block sizes. Let B(n) and G(n), respectively, denote the number of partitions and the number of gap-free partitions of the set [n]. We prove that