Skip to main content
http -> https
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?

I'm aware of two examples: Szemerédi's theoremSzemerédi's theorem and density Hales-Jewett theoremdensity Hales-Jewett theorem.

Let me try to formalize what I mean by "density Ramsey theorems". I'm interested in statements of the following type: for every $k \in \mathbb{N}, \alpha > 0$ there exists $n_0 = n_0(k, \alpha)$ such that if we have a collection of $n \geq n_0$ objects, then whatever $\alpha n$ objects we take there are $k$ among them that form a "nice" structure. Collections and niceness are problem-specific of course: in case of Szemerédi's theorem they are $\lbrace 1, 2, \ldots, n\rbrace$ and arithmetic progressions, for Hales-Jewett — $[k]^d$ and combinatorial lines, respectively. I'm particularly interested in theorems where the dependence $n_0 = n_0(k, \alpha)$ can be made explicit.

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?

I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem.

Let me try to formalize what I mean by "density Ramsey theorems". I'm interested in statements of the following type: for every $k \in \mathbb{N}, \alpha > 0$ there exists $n_0 = n_0(k, \alpha)$ such that if we have a collection of $n \geq n_0$ objects, then whatever $\alpha n$ objects we take there are $k$ among them that form a "nice" structure. Collections and niceness are problem-specific of course: in case of Szemerédi's theorem they are $\lbrace 1, 2, \ldots, n\rbrace$ and arithmetic progressions, for Hales-Jewett — $[k]^d$ and combinatorial lines, respectively. I'm particularly interested in theorems where the dependence $n_0 = n_0(k, \alpha)$ can be made explicit.

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?

I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem.

Let me try to formalize what I mean by "density Ramsey theorems". I'm interested in statements of the following type: for every $k \in \mathbb{N}, \alpha > 0$ there exists $n_0 = n_0(k, \alpha)$ such that if we have a collection of $n \geq n_0$ objects, then whatever $\alpha n$ objects we take there are $k$ among them that form a "nice" structure. Collections and niceness are problem-specific of course: in case of Szemerédi's theorem they are $\lbrace 1, 2, \ldots, n\rbrace$ and arithmetic progressions, for Hales-Jewett — $[k]^d$ and combinatorial lines, respectively. I'm particularly interested in theorems where the dependence $n_0 = n_0(k, \alpha)$ can be made explicit.

tag
Link
Charles
  • 9.1k
  • 1
  • 38
  • 76
Post Made Community Wiki by ilyaraz
Source Link
ilyaraz
  • 1.8k
  • 3
  • 15
  • 25

Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?

I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem.

Let me try to formalize what I mean by "density Ramsey theorems". I'm interested in statements of the following type: for every $k \in \mathbb{N}, \alpha > 0$ there exists $n_0 = n_0(k, \alpha)$ such that if we have a collection of $n \geq n_0$ objects, then whatever $\alpha n$ objects we take there are $k$ among them that form a "nice" structure. Collections and niceness are problem-specific of course: in case of Szemerédi's theorem they are $\lbrace 1, 2, \ldots, n\rbrace$ and arithmetic progressions, for Hales-Jewett — $[k]^d$ and combinatorial lines, respectively. I'm particularly interested in theorems where the dependence $n_0 = n_0(k, \alpha)$ can be made explicit.