On colored set partitions of type B n

Generalizing Reiner’s notion of set partitions of type B _n , we define colored B _n -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B _n -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B _n -partition. We find an asymptotic expression of the total number of colored B _n -partitions up to an error of O(n ^?1/2log^7/2 n], and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored B _n -partitions.     

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.     

Pattern Avoidance in Ordered Set Partitions

In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n?1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type result that exhibits existence of such growth rates.     

Universal cycles of -partitions of an -set

In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles. Universal cycles have been investigated for permutations, partitions, k-partitions and k-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n−1-partitions of an n-set when n is odd and conjectured that when n is even, they do not exist. Herein we prove Hurlbert’s conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for n≤13 and give a lower bound on the total number for all n. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.     

On lines, joints, and incidences in three dimensions

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) [9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R³ and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R³. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) [9].     

Lexicographical separation in Rn

We prove a new separation theorem for any two subsets of Rⁿ with disjoint convex hulls, by linear operators, or isomorphisms, or isometries, in the sense of the lexicographical order of Rⁿ (or, equivalently, by “generalized half spaces”). Also, we prove that if one of the sets is the nonpositive orthant, then the isometry can be taken lexicographically nonnegative, or the isomorphism nonnegative (in the usual order). We give some applications.     

A gallai-type problem

Two disjoint sets in R^m are said to be n-incident if every flat spanned by n distinct points of one set contains a point of the other. We obtain bounds for the dimension of the flat spanned by the union of n-incident sets and consider a related problem.     

A characterization of Poissonian domains

We give a characterization of Possonian domains inR ⁿ , i.e., those domains for which every bounded harmonic function is the harmonic extension of some function inL ^∞ of harmonic measure. We deduce several properties of such domains, including some results of Mountford and Port. In two dimensions we give an additional characterization in terms of the logarithmic capacity of the boundary. We also give a necessary and sufficient condition for the harmonic measures on two disjoint planar domains to be mutually singular.     

Partitions and the grand canonical ensemble

Two disconnected remarks about partitions. First, a pedagogical remark connecting pure mathematics with statistical physics. The grand canonical ensemble of statistical mechanics is applied to the counting of partitions. This picture borrowed from physics gives a simple approximation to the exact calculation of the partition function by Hardy and Ramanujan. Second, an exact formula is guessed for the function N _S (m,n) defined in a recent paper by Andrews, Garvan, and Liang. The formula was subsequently proved by Garvan. We hope that it may lead to a better understanding of the beautiful new congruence properties of partitions discovered by Andrews.     

Multidimensional analog of the two-dimensional perron effect of sign change of characteristic exponents for infinitely differentiable differential systems

We obtain a general n-dimensional analog of the two-dimensional (partial) Perron effect of sign change of all arbitrarily prescribed negative characteristic exponents of an n-dimensional differential system of the linear approximation with infinitely differentiable bounded coefficients to the positive sign for the characteristic exponents of all nontrivial solutions of a nonlinear n-dimensional differential system with infinitely differentiable perturbations of arbitrary order m > 1 of smallness in a neighborhood of the origin and growth outside it. These positive exponents take n values distributed over n arbitrarily prescribed disjoint intervals and are realized on solutions issuing from nested subspaces R ¹ ? R ² ? ... ? R ⁿ .     

Translation planes constructed by multiple hyper-regulus replacement

New classes of mutually disjoint hyper-reguli of order q ⁿ , for n > 2, are determined, which are not André hyper-reguli if n > 3. If n is odd, each hyper-regulus permits at least two replacements and if q is odd and (n, q?1) = 1, there are (q?1)/2 mutually disjoint hyper-reguli each of which may be replaced at least two ways. Each of the possible 2^(q-1)/2 translation planes constructed is not André or generalized André. There are also new constructions of mixed subgeometry partitions.     

Partitions weighted by the parity of the crank

The ‘crank’ is a partition statistic which originally arose to give combinatorial interpretations for Ramanujan's famous partition congruences. In this paper, we establish an asymptotic formula and a family of Ramanujan type congruences satisfied by the number of partitions of n with even crank Me(n) minus the number of partitions of n with odd crank Mo(n). We also discuss the combinatorial implications of q-series identities involving Me(n)−Mo(n). Finally, we determine the exact values of Me(n)−Mo(n) in the case of partitions into distinct parts. These values are at most two, and zero for infinitely many n.     

Partitioning Sets of Triples into Small Planes

We study partitions of the set of all ₃ ^v triples chosen from a v-set intopairwise disjoint planes with three points per line. Our partitions may contain copies of PG(2,2) only (Fano partitions) or copies of AG(2, 3) only (affine partitions)or copies of some planes of each type (mixed partitions).We find necessary conditions for Fano or affine partitions to exist. Such partitions are already known in severalcases: Fano partitions for v = 8 and affine partitions for v = 9 or 10. We constructsuch partitions for several sporadic orders, namely, Fano partitions for v = 14, 16, 22, 23, 28, andan affine partition for v = 18. Using these as starter partitions, we prove that Fano partitionsexist for v = 7 ⁿ + 1, 13 ⁿ + 1,27 ⁿ + 1, and affine partitions for v = 8 ⁿ + 1,9 ⁿ + 1, 17 ⁿ + 1. In particular, both Fano and affine partitionsexist for v = 3⁶ⁿ + 1. Using properties of 3-wise balanced designs, weextend these results to show that affine partitions also exist for v = 3²ⁿ .Similarly, mixed partitions are shown to exist for v = 8 ⁿ ,9 ⁿ , 11 ⁿ + 1.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

A note on maximally repeated sub-patterns of a point set

We answer a question raised by Brass on the number of maximally repeated sub-patterns in a set of n points in R^d. We show that this number, which was conjectured to be polynomial, is in fact Θ(2^n/2) in the worst case, regardless of the dimension d.     

Comparative error bound theory for three location models: continuous demand versus discrete demand

We develop a unified error bound theory to compare a given p-median, p-center or covering location model with continuously distributed demand points in R ⁿ to a corresponding given original model of the same type having a finite collection of demand points in R ⁿ . We give ways to construct either a continuous or finite demand point model from the other model and also control the error bound. Our work uses Voronoi tilings extensively, and is related to earlier error bound theory for aggregating finitely many demand points.     

Partitioning the lattice points in Rn

A (linear) lattice point path is the intersection of a connected subset of a straight line in euclidean n-space Rⁿ with the lattice points Zⁿ ? Rⁿ, where Z denotes the integers. Given a subset X ? Zⁿ, a typical problem considered in this paper is the determination of the largest integer k (it turns out that k ? 2n ?1) with the property that given any partition of X into two parts, then at least one of the parts contains as a subset a lattice point path of k points. Also considered are similar questions which arise by placing restrictions on the type of partitions allowed, or by restricting attention to those lattice point paths which are obtainable from lines having preassigned (integral) direction numbers.     

BV-Ellipticity and Lower Semicontinuity of Surface Energy of Caccioppoli Partitions of ℝ n

We give a new proof that BV-ellipticity is sufficient for lower semicontinuity of surface energy of Caccioppoli partitions of ? ⁿ , for any n≥2, with respect to convergence in volume. BV-ellipticity, introduced by L. Ambrosio and A. Braides two decades ago, is the only condition known to be necessary and sufficient for lower semicontinuity in the context of Caccioppoli partitions of ? ⁿ ; it is analogous, for this setting, to C.B. Morrey’s quasi-convexity. We also show, for the first time, that BV-ellipticity suffices for lower semicontinuity with respect to weaker notions of convergence involving the weak and flat topologies on integral currents.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.