Partition regularity

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

Given a set

X

{\displaystyle X}

, a collection of subsets

S

⊂

P

(

X

)

{\displaystyle \mathbb {S} \subset {\mathcal {P}}(X)}

is called partition regular if every set A in the collection has the property that, no matter how A is partitioned into finitely many subsets, at least one of the subsets will also belong to the collection. That is,

for any

A

∈

S

{\displaystyle A\in \mathbb {S} }

, and any finite partition

A

=

C

1

∪

C

2

∪

⋯

∪

C

n

{\displaystyle A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}}

, there exists an i ≤ n such that

C

i

{\displaystyle C_{i}}

belongs to

S

{\displaystyle \mathbb {S} }

. Ramsey theory is sometimes characterized as the study of which collections

S

{\displaystyle \mathbb {S} }

are partition regular.

Examples

The collection of all infinite subsets of an infinite set X is a prototypical example. In this case partition regularity asserts that every finite partition of an infinite set has an infinite cell (i.e. the infinite pigeonhole principle.)

Sets with positive upper density in

N

{\displaystyle \mathbb {N} }

: the upper density

d

¯

(

A

)

{\displaystyle {\overline {d}}(A)}

of

A

⊂

N

{\displaystyle A\subset \mathbb {N} }

is defined as

d

¯

(

A

)

=

lim sup

n

→

∞

|

{

1

,

2

,

…

,

n

}

∩

A

|

n

.

{\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.}

(Szemerédi's theorem)

For any ultrafilter

U

{\displaystyle \mathbb {U} }

on a set

X

{\displaystyle X}

,

U

{\displaystyle \mathbb {U} }

is partition regular: for any

A

∈

U

{\displaystyle A\in \mathbb {U} }

, if

A

=

C

1

⊔

⋯

⊔

C

n

{\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}}

, then exactly one

C

i

∈

U

{\displaystyle C_{i}\in \mathbb {U} }

.

Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation

T

{\displaystyle T}

of the probability space (Ω, β, μ) and

A

∈

β

{\displaystyle A\in \beta }

of positive measure there is a nonzero

n

∈

R

{\displaystyle n\in R}

so that

μ

(

A

∩

T

n

A

)

>

0

{\displaystyle \mu (A\cap T^{n}A)>0}

.

Call a subset of natural numbers a.p.-rich if it contains arbitrarily long arithmetic progressions.