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$.

Filter by
Sorted by
Tagged with
5 votes
0 answers
131 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 ...
8 votes
0 answers
165 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-...
6 votes
0 answers
152 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 ...
  • 1,641
11 votes
0 answers
175 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
125 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
69 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
77 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
447 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
77 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 ...
  • 1,641
16 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 ...
  • 4,492
0 votes
1 answer
68 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
78 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+...
  • 331
7 votes
0 answers
202 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
246 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
269 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
37 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). ...
  • 3,814
1 vote
0 answers
89 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,814
3 votes
2 answers
228 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
491 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
125 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
87 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 ...
  • 139
2 votes
0 answers
770 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
99 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
86 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 ...
  • 909
4 votes
2 answers
694 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\...
  • 8,771
2 votes
1 answer
140 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. ...
  • 1,674
3 votes
1 answer
160 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
106 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,...
  • 203
2 votes
1 answer
197 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 ...
  • 376
4 votes
0 answers
182 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. ...
5 votes
1 answer
143 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 ...
  • 1,536
2 votes
1 answer
132 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 \...
  • 59
7 votes
0 answers
145 views

Primitive recursive bounds for the the Gallai-Witt theorem

Let me first recall some facts: By the work of Gowers, the Van der Waerden numbers belong to class $\mathcal{E}^3$ of the Grzegorczyk hierarchy By the work of Shelah, the Hales-Jewett numbers belong ...
5 votes
2 answers
102 views

Density of Ramsey subsets of $\omega$

For any set $X$ let $[X]^2=\{\{x,y\}:x\neq y \in X\}$. The starting point of this question is the following statement that follows from a more general theorem by Ramsey: If $\pi:[\omega]^2\to\{0,1\}$ ...
1 vote
0 answers
92 views

A generalization of Hales-Jewett theorem

Hales-Jewett theorem ($HJ(\alpha,k,n)$) states that for every coloring $f:\alpha^N\rightarrow k$ where $N$ is sufficiently large, there is an $n$-dimensional combinatorial subspace of $\alpha^N$ that ...
  • 909
0 votes
0 answers
40 views

Quantitative Ramsey theorem - asymmetric and multicolors

Let $q\geq 1$ and $H_1,\dots, H_q$ be graphs. By Ramsey theorem, it is well-known that there exists $n_0$ such that the following holds. If $n\geq n_0$ and the edges of $K_n$ are colored with $q$ ...
2 votes
1 answer
85 views

Computation of cyclic van der Waerden numbers

Van der Waerden's theorem gives us a finite number $W(k,r)$ defined as the smallest positive integer $N$ such that for any $n\geq N$, any $r$-coloring of $[n]=\{1,\dots,n\}$ admits a monochromatic $k$-...
3 votes
1 answer
128 views

Independence number of $C_4$-free graphs

It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$. This bound cannot be improved over $\Theta(n^{\...
  • 8,566
6 votes
1 answer
338 views

Ramsey's number R(4,4) with arithmetic progressions

Can 17 positive integers in arithmetic progression be found such that that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively ...
47 votes
8 answers
3k views

Ron L. Graham’s lesser known significant contributions

Ron L. Graham is sadly no longer with us. He was very prolific and his work spanned many areas of mathematics including graph theory, computational geometry, Ramsey theory, and quasi-randomness. His ...
5 votes
1 answer
138 views

Lower bound for diagonal Ramsey numbers —- reference request

Using the first moment method, in 1947 Erd\H{o}s gave a lower bound on the diagonal Ramsey numbers $R(k,k)$: $$ R(k,k) \geq (1+o(1))\frac{k}{e\sqrt{2}} 2^{k/2}. $$ In 1975 Spenser used the Lov\’asz ...
  • 1,092
6 votes
1 answer
128 views

Ramsey theory in infinite-dimensional projective spaces

Let $\mathbb{F}_q$ be a finite field and $k$ be a positive integer. If we colour each point of the infinite-dimensional projective space $\mathbb{F}_q \mathbb{P}^{\infty}$ with one of $k$ colours, can ...
2 votes
1 answer
128 views

Additivity of the upper Banach density

The following notion of upper Banach density was defined (Definition 2.1(c)) by Hindman and Strauss in their paper 'Density in arbitrary semigroups': Definition: Let $S$ be a semigroup, let $\mathcal{...
  • 25
0 votes
1 answer
100 views

Ramsey graph for C4 graph

Does there exist a ramsey graph of C4 such that an induced subgraph has a monochromatic C4, no matter how the edges are colored?
7 votes
1 answer
167 views

3 term van der Waerden with large step size

Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$". For which $n$ is $P(n)$ true? It's easy to see that $P(2)$ is ...
user avatar
-7 votes
1 answer
454 views

Is Green-Tao's theorem a consequence of Van der Waerden theorem?

Wanting to learn a bit about Ramsey's theory, I read the corresponding article on Wikipedia and stumbled upon this: "Le théorème de van der Waerden[2] : pour tous entiers c et n, il existe un entier[...
5 votes
0 answers
204 views

Ramsey-Kuratowski numbers

A simple graph is an ordered pair of sets $\,\Gamma:=(V\,E)\,$ such that $\,E\subseteq\binom V2.\ $ Kuratowski graph of the first kind is $\,K_n:=\left(V\,\,\binom V2\right),\,$ where $\,n:=|V|.\,$ ...
  • 3,814
0 votes
0 answers
52 views

Counting progressions for Ramsey-type number

I'm currently learning about Ramsey theory and how to use the probabilistic method to find lower bounds. Currently I'm looking at a family, which I'll call $H$, that is composed of the following ...
2 votes
1 answer
100 views

Ramsey type properties of $F_\sigma$ ideals

Let $I \subseteq 2^\omega$ be any $F_\sigma$ ideal containing every finite sets : $\forall X \in I\ \forall Y \subseteq X\ \text{ we have } Y \in I$ $\forall k\ \forall X_1,\dots,X_k \in I\ X_1 \cup \...