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.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

The cardinals below

The results of this paper concern the effective cardinal structure of the subsets of [ω₁]^<ω₁, the set of all countable subsets of ω₁. The main results include dichotomy theorems and theorems which show that the effective cardinal structure is complicated.     

Swimming below icebergs

You are swimming close to an iceberg with a convex lower surface. You calculate at what slope you have to swim down so that, whatever the direction in which you swim, you can be sure that you will not collide with the iceberg. This limiting slope is intimately related to the existence of subtangents to the iceberg that satisfy various conditions. These considerations lead to generalizations of Rockafellar's Maximal Monotonicity Theorem, of which we give acomplete new proof. We also discuss related open problems on maximal monotonicity and subdifferentials, and generalizations of recent results on the existence of subtangents separating the epigraphs of proper convex lower semicontinuous functions from nonempty bounded closed convex sets, with some control over their slopes.     

Swimming below icebergs

You are swimming close to an iceberg with a convex lower surface. You calculate at what slope you have to swim down so that, whatever the direction in which you swim, you can be sure that you will not collide with the iceberg. This limiting slope is intimately related to the existence of subtangents to the iceberg that satisfy various conditions. These considerations lead to generalizations of Rockafellar's Maximal Monotonicity Theorem, of which we give acomplete new proof. We also discuss related open problems on maximal monotonicity and subdifferentials, and generalizations of recent results on the existence of subtangents separating the epigraphs of proper convex lower semicontinuous functions from nonempty bounded closed convex sets, with some control over their slopes.     

The partition problem

In this paper we describe several forms of thek-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.Partial Support from NSF Grants DMS 8606188 and ECS 8800281 is gratefully acknowledged.     

Submodular partition functions

Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger’s theorem, and thus generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.     

A partition identity

Let n₁+n₂+?+n_m=n where the n_i's are integers (possibly negative or greater than n). Let p=(k₁,…,k_m), where k₁+k₂+?+k_m=k, be a partition of the nonnegative integer k into m nonnegative integers and let P denote the set of all such partitions. For m?2, we prove the combinatorial identity

$\text{∑}\text{p∈P}\text{∏}\text{i=1}\text{m}\text{n}{}_{\mathrm{i}}\text{+1?k}{}_{\mathrm{i}}\text{k}{}_{\mathrm{i}}\text{=}\text{∑}\text{i?0}\text{j+m?2}\text{m?2}\text{n+1?k?2}{}_{\mathrm{j}}\text{k?2}{}_{\mathrm{j}}$

which implies the surprising result that the left side of the above equation depends on n but not on the n_i's.     

Countable partition ordinals

The structure of ordinals of the form ω^ωβ for countable β is studied. The main result is:

Theorem 1. Ifβ<ω₁is the sum of one or two indecomposable ordinals, then

ω^ωβ→(ω^ωβ,3)².     

Dynamic partition trees

In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log² n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n ^· k ) where=log₂((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM).