# Questions tagged [ramsey-theory]

Branch of combinatorics with the philosophy that 'total disorder is impossible'. For example, Ramsey's theorem asserts that for each $n$, every sufficiently large graph either contains a clique of size $n$ or a stable set of size $n$.

210
questions

10
votes

1
answer

341
views

### Two dimensional perfect sets

Consider the following family of sets
$$ \begin{align*}
\mathcal{F} = \{X\subseteq [0,1]\times [0,1] \mid \ &X \text{ is closed and }\\& \forall x \in \pi_0 (X) (\{y \in [0,1] \mid (x,y) \in ...

4
votes

0
answers

92
views

### What properties do graphs avoiding large regular subgraphs have?

Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...

33
votes

1
answer

2k
views

### Two-colouring the two-sphere

Suppose that $S^2$ is the unit sphere in $\mathbb{R}^3$.
Is there a function $f \colon S^2 \to \{0,1\}$ so that, for any orthonormal basis $(u,v,z)$, exactly one of the values $f(u)$, $f(v)$, and $f(...

2
votes

0
answers

60
views

### Constants for diagonal hypergraph Ramsey Theorem

For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$, such that for every $r$-...

2
votes

0
answers

96
views

### Instance of polynomial van der Waerden without good bounds

Let $P\subset \Bbb{Z}[X]$ be a finite set of polynomials with constant-term zero. Then, polynomial vdW says:
For eacg finite $r$, there exists some $N=N(P,r)$, such that every $r$-coloring $C:\{1,\...

5
votes

1
answer

280
views

### Primitive recursive bounds for multidimensional polynomial vdW / HJ

In Shelah's paper 679, he proves primitive recursive bounds for the polynomial Hales-Jewett theorem and thus for the polynomial van der Waerden theorem.
How about for the multidimensional polynomial ...

8
votes

1
answer

230
views

### Non-Ramsey functions $c:[\omega]^\omega\to\{0,1\}$ and the Axiom of Choice

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$, and let $c:[\omega]^\omega\to\{0,1\}$ be a function. We say that $a\in [\omega]^\omega$ is monochromatic with respect to $c$...

0
votes

0
answers

79
views

### Real world application of large sets like syndetic sets, central sets

Large sets in $\mathbb{N}$ have strong combinatorial structures. For example, it is known that central sets in $\mathbb{N}$ contain arbitrarily long arithmetic progressions. It also contains solutions ...

1
vote

0
answers

94
views

### A two-colouring of a complete graph over the set of incompressible strings

A two-coloring is done over the (infinite) set all incompressible strings (in some chosen alphabet); such that, an edge between two strings is blue if and only if, the strings are of equal lengths and ...

5
votes

0
answers

122
views

### Multidimensional van der Waerden, bounds for squares

Given $r$, let $f(r)$ be the smallest $N$ such that for any $r$-coloring $C:\{1,\dots,N\}^2 \to \{1,\dots,r\}$, there exists $x,y,d\neq 0$ such that $C((x,y)) = C((x+d,y))= C((x,y+d))=C((x+d,y+d))$.
I ...

3
votes

1
answer

188
views

### Infinite constructions in additive combinatorics

A huge part of the investigation in the area of additive combinatorics asks for the answer of the following question: given an arithmetic pattern (for instance, $x+y=2z$, or $x+y=z+t$, or $x+y=z$), ...

4
votes

1
answer

135
views

### Independent sets in graphs with girth $\ge g$

A well known off-diagonal Ramsey result says that every $C_3$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(\sqrt{N\log N})$.
It is a conjecture of Erdos that every $C_4$-free ...

4
votes

1
answer

216
views

### Ramsey-like property with order condition

I wonder if there are regular cardinals $\lambda$ and $\kappa$ such that $\kappa < \lambda \leq 2^\kappa$ and such that, consistently, the following holds:
Let $c: [\lambda]^2 \to \kappa$ be such ...

5
votes

0
answers

152
views

### What is this Ramsey problem

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...

2
votes

1
answer

133
views

### Explicitly known graph families where the product of the size of biggest independent set and biggest clique is "small"

Are there explicit constructions of graph families with the following property:
$G_n$ is the graph on $n$ vertices in the family, $\omega(G_n)$ is the size of the biggest clique in the graph $G_n$, $\...

0
votes

1
answer

85
views

### Left syndeticity and right syndeticity in nilpotent group

$\DeclareMathOperator\Pf{\mathcal{P}_\mathrm{f}}$Question: Does there exist any reference regarding the study of left and right syndeticity in nilpotent group? More specifically, did anyone introduce/...

3
votes

0
answers

97
views

### Closure of the inverse image under the projection map

Let $S$ be a subsemigroup of a semitopological semigroup $(T,+)$, let $e$ be an idempotent in $T\setminus S$ such that $e\in cl_T(S)$, let $\mathcal{E}$ be a subsemigroup of $S\times S$ such that $(e,...

4
votes

0
answers

180
views

### Happy ending problem - why not a proof by induction? (cont)

After sharing ideas on this post, I have been thinking for some time on the problem, and I think that a possible way to prove the Erdös-Szekeres conjecture could be structured as follows:
Consider ...

11
votes

1
answer

283
views

### Higher-dimensional Sierpiński partitions

Given a well-ordering of $\mathbb{R}$, there is a natural way to define an associated partition of pairs of real numbers into two pieces: one assigns the value $0$ to a pair $r<s$ if the well-...

9
votes

1
answer

279
views

### Dense triangle-free graphs and their independent sets

Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...

12
votes

0
answers

211
views

### Does $2^{\aleph_0}\rightarrow [\aleph_1]^2_3$ require that the continuum is weakly inaccessible?

A classic result of Sierpiński shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^2_2$, that is, there is a coloring of pairs of real numbers using two colors such that both colors appear on any ...

2
votes

0
answers

157
views

### Ramsey's infinite principle and the axiom of choice

Frank Plumpton Ramsey, best known for giving his name to Ramsey Theory, presented the following theorem in On a Problem of Formal Logic, that was submitted in 1928 and published posthumously.
Let $\...

5
votes

0
answers

85
views

### Lower bound for nonconventional ergodic averages in finite fields

Let $p$ be a sufficiently large prime number and $f\colon\mathbb{F}_{p}\to\mathbb{R}_{\geq 0}$ be a function bounded by 1 such that the average of $f$ over the finite field $\mathbb{F}_{p}$ is at ...

33
votes

1
answer

2k
views

### Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

I'm trying to figure out the question in the title for a project that I'm working on.
My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...

1
vote

1
answer

121
views

### $n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

The coloring game is a game played between Alice and Bob.
There exists a grid of size $n \times n$, where $n$ is a strictly positive integer.
Each cell of the grid can be colored with a color that ...

9
votes

1
answer

481
views

### Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$?

For any set $X$ and cardinal $\mu \neq \emptyset$, we denote by $[X]^\mu$ the collection of subsets of cardinality $\mu$. If $\kappa, \mu \neq \emptyset$ are cardinals and $f: [X]^\mu\to \kappa$ is a ...

2
votes

0
answers

82
views

### Monotone rainbow sequence in the grid

Let $[N]:=\{1,\dots,N\}$. For a sequence $(x_1,y_1),\dots,(x_k,y_k)\in [N]^2$ of points in the grid, we say the sequence is increasing if $x_1<\dots<x_k$ and $y_1<\dots<y_k$. Similarly we ...

17
votes

2
answers

2k
views

### A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem

Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...

0
votes

1
answer

75
views

### References for properties which are invariant under partition of $\mathbb{Z}$ by a finite number of sets

A well known result in Ramsey theory is: If the set of positive integers is partitioned into a finite number of sets, then at least one of these sets will contain a solution to $x+y=z$
By "...

1
vote

0
answers

83
views

### Proving $R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+n_2+\cdots+n_k \choose n_1,n_2,\cdots,n_k}$

The following statement is a well-known lemma of Ramsey number.
$$R(m+1,n+1) \leq {m+n \choose m}$$
Now, I want to prove the improvement of the above statement:
$$R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+...

8
votes

0
answers

218
views

### On the structure of maximal Ramsey colorings

For positive integers $a_1,\dots,a_n$, recall that the multicolor Ramsey number $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $...

6
votes

1
answer

261
views

### Are these two definitions of $\mathcal{U}$-Ramsey set equivalent?

Let $\mathcal{U}$ be an ultrafilter over $\omega$, and let $\mathcal{X} \subseteq [\omega]^\omega$. In two separate texts, there are two possible interpretations of a $\mathcal{U}$-Ramsey set, as ...

6
votes

1
answer

296
views

### Ramsey ultrafilters on partial order

$\newcommand{\U}{\mathcal{U}}$
$\newcommand{\P}{\mathbb{P}}$
$\newcommand{\Q}{\mathbb{Q}}$
$\newcommand{\F}{\mathcal{F}}$
Recall the following equivalent definitions of a Ramsey ultrafilter over $\...

1
vote

0
answers

48
views

### Group graphs and Ramsey Theory. Sub-question 2

This note is a continuation of Group graphs and Ramsey theory. Sub-question 1.
Let $\ X\ $ be a group, and let $\ c:\binom X2\to C\ $ be a two-coloring ($r\ $ and $\ g\ $ are the two colors). ...

1
vote

0
answers

97
views

### Group graphs and Ramsey theory. Sub-question 1

Question: Find/compute relations between the classical Ramsey numbers and their variations (described below) -- exact or asymptotic.
A graph is a set $\ X\ $ together with a (coloring) function
$\ c:\...

3
votes

2
answers

250
views

### Ramsey-Turán density function is well defined

Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...

7
votes

2
answers

538
views

### A 2-page paper on a lower bound of Ramsey number

I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...

7
votes

0
answers

136
views

### Convex pigeonhole principle in Banach spaces

In this question, all Banach spaces will be infinite-dimensional and separable, and all subspaces will be infinite-dimensional and closed.
Say that a subset of the unit sphere $S_X$ of a Banach space $...

0
votes

0
answers

112
views

### Original Paper for "Bipartite Ramsey Theory" by Hattingh, Johannes H, 1998

I'm trying to find the original paper "Bipartite Ramsey Theory" by Hattingh, Johannes H., Util. Math. 53 (1998), 217–230. However, I couldn't find it online except Mathsci.
Does anyone ...

2
votes

0
answers

829
views

### Happy ending problem – Why not a proof by induction?

I have been thinking for a while on the happy ending problem, looking for approaches to attack the Erdős–Szekeres conjecture: the smallest number of points for which any general position arrangement ...

3
votes

1
answer

114
views

### Roelcke precompactness and Ramsey property

A survey by Nguyen Van Thé (2014) has Conjecture 1,
which is that
"every closed oligomorphic
subgroup of $S_∞$ should have a metrizable universal minimal flow with a generic
orbit." Later, ...

4
votes

1
answer

89
views

### Ramsey style theorem with unbounded colors

Question: Let $\varepsilon>0$ and $N\in\omega$ be sufficiently large (depending on $\varepsilon$).
Let $h:\subseteq N\rightarrow N$ be such that $h(B)\notin B$ for all $B\subsetneq N$.
Must there ...

4
votes

2
answers

1k
views

### The number of monochromatic triangles

It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...

2
votes

1
answer

141
views

### Well approximating sets

Given a real number $x \in (0, 1)$, we denote by $0.x_1x_2\ldots$ its binary expansion, where we always choose the expansion that ends in an infinite number of $1$’s whenever a choice has to be made.
...

3
votes

1
answer

177
views

### A question on Borel equivalence relations

Suppose that $\mathsf E$ is a countable Borel equivalence relation on the reals, and $\mathsf B$ is a finer equivalence of order 2, so that each $\mathsf E$-class consists of precisely two $\mathsf B$-...

2
votes

1
answer

134
views

### Equal subset-sums of bounded vectors

Let $S\subseteq \{0,\ldots,n\}^d$ be a set of $d$-dimensional vectors of with bounded, natural, coordinates.
We are given that
$$v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$$
where $v_1,\ldots,v_t,u_1,\ldots,...

2
votes

1
answer

305
views

### Best known upper bound for the Ramsey function $R(k,x)$

The Ramsey function $R(k,x)$ is defined as the minimal integer $n$ such that any graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $x$. Miklós Ajtai, János ...

5
votes

0
answers

197
views

### Ramsey Numbers for Integers

Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...

6
votes

1
answer

174
views

### Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three colors?

Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color ...

2
votes

1
answer

143
views

### The extension of the substitution map of the semigroup of variable words to its Stone–Čech compactification is a homomorphism

Reading the proof of the Hales-Jewett theorem the author defines $W_L$ as the set
of finite words over some alphabet $L$, $W_{L_v}$ as the set of variable-words
over $L$, i.e. finite words over $L \...