Open covers and partition relations

An open cover of a topological space is said to be an -cover if there is for each finite subset of the space a member of the cover which contains the finite set, but the space itself is not a member of the cover. We prove theorems which imply that a set of real numbers has Rothberger's property if, and only if, for each positive integer , for each -cover of , and for each function from the two-element subsets of , there is a subset of such that is constant on , and each element of belongs to infinitely many elements of (Theorem 1). A similar characterization is given of Menger's property for sets of real numbers (Theorem 6).

     

Many partition relations below density

We force 2 ^λ to be large, and for many pairs in the interval (λ, 2 ^λ ) a strong version of the polarized partition relations holds. We apply this to problems in general topology. For example, consistently, every 2 ^λ is the successor of a singular and for every Hausdorff regular space X, hd(X) ≤ s(X)⁺³, hL(X) ≤ s(X)⁺³ and better when s(X) is regular, via a halfgraph partition relations. For the case s(X) = ℵ ₀ we get hd(X), hL(X) ≤ N ₂.     

New results on finite polarized partition relations

Let c = c(m,n,j,k) be the largest integer such that every matrix with m rows and n columns whose entries belong to a set of cardinal c has a constant submatrix with j rows and k columns. Some results in the case j = 2 are given.     

Parameterized partition relations on the real numbers

We consider several kinds of partition relations on the set of real numbers and its powers, as well as their parameterizations with the set of all infinite sets of natural numbers, and show that they hold in some models of set theory. The proofs use generic absoluteness, that is, absoluteness under the required forcing extensions. We show that Solovay models are absolute under those forcing extensions, which yields, for instance, that in these models for every well ordered partition of there is a sequence of perfect sets whose product lies in one piece of the partition. Moreover, for every finite partition of there is and a sequence of perfect sets such that the product lies in one piece of the partition, where is the set of all infinite subsets of X. The proofs yield the same results for Borel partitions in ZFC, and for more complex partitions in any model satisfying a certain degree of generic absoluteness. This work was supported by the research projects MTM 2005-01025 of the Spanish Ministry of Science and Education and 2005SGR-00738 of the Generalitat de Catalunya. A substantial part of the work was carried out while the second-named author was ICREA Visiting Professor at the Centre de Recerca Matemàtica in Bellaterra (Barcelona), and also during the first-named author’s stays at the Instituto Venezolano de Investigaciones Científicas and the California Institute of Technology. The authors gratefully acknowledge the support provided by these institutions.     

On consistency relations for polynomial splines on a uniform partition

In this paper we present linear dependence relations connecting spline values, derivative values and integral values of the spline. These relations are useful when spline interpolants or histospline projections of a function are considered.This work was supported in part by the Ministère de l'Éducation du Québec and by the Department of the National Defence of Canada.     

A canonical partition theorem for equivalence relations on Zt

A canonical version of the multidimensional version of van der Waerden's theorem on arithmetic progressions is proved.     

Paradeterminants and partition polynomials

We study Bell polynomials by using functions of triangular matrices (parapermanents and paradeterminants). Some combinatorial identities and relationships between these functions and the Stirling numbers of the first and second kinds are established. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 11, pp. 1457–1469, November, 2008.     

Join congruence relations and closure relations

In this paper we show that, given a complete lattice , the following three lattices are the same: (1) the lattice of closure relations on , (2) the lattice of meet-closed subsets of , and (3) the lattice of complete join congruence relations on .     

Instanton partition functions and M-theory

We discuss instanton partition functions in various spacetime dimensions. These partition functions capture some information about the spectrum of the supersymmetric gauge theories and their low-energy dynamics. Some of these theories can be defined microscopically only through string theory. Remarkably, they even know about the M-theory. Our conjectures include the identities between the generalization of the MacMahon formula and the character of M-theory, compactified down to 0 + 1 dimension. This article is based on the 5th Takagi Lectures that the author delivered at the University of Tokyo on October 4 and 5, 2008.     

Semi-pointed partition posets and species

We define semi-pointed partition posets, which are a generalization of partition posets, and show that they are Cohen–Macaulay. We then use multichains to compute the dimension and the character for the action of the symmetric groups on their homology. We finally study the associated incidence Hopf algebra, which is similar to the Faà di Bruno Hopf algebra.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).