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
7
votes
0answers
109 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
0answers
62 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
1answer
598 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
1answer
62 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
1answer
82 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
2answers
224 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
1answer
136 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
1answer
140 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
1answer
74 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
1answer
168 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 ...
3
votes
0answers
179 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
1answer
106 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
1answer
116 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 \...
6
votes
0answers
124 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
2answers
94 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
0answers
81 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 ...
0
votes
0answers
38 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
1answer
71 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
1answer
100 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^{\...
3
votes
1answer
206 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 ...
45
votes
8answers
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
1answer
110 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 ...
6
votes
1answer
120 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
1answer
123 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{...
0
votes
1answer
93 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
1answer
161 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 ...
-7
votes
1answer
410 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
0answers
197 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|.\,$ ...
0
votes
0answers
51 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
1answer
93 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 \...
2
votes
0answers
265 views

Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?

As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$. According to the Dynamic Survey of Ramsey Numbers at ...
20
votes
1answer
554 views

If $S_\mathbb N$ is partitioned into finitely many pieces, must one piece contain a "skew copy" of every countable group?

Suppose $G$ and $H$ are groups. $C \subseteq H$ is called a skew copy of $G$ in $H$ if $C = hK$ for some $h \in H$ and some subgroup $K$ of $H$ with $K \cong G$. Question 1: Suppose the infinite ...
1
vote
0answers
150 views

Winning strategies for a game on the natural numbers

Define $$F=\{(l_n, k_n)_{n=1}^t: t,l_n, k_n \in \mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}.$$ Suppose that I have a collection $G\subset F$, which is a set of ''good'' sequences. ...
2
votes
0answers
164 views

An analytic game and Ramsey's theorem

Let $$P=\{(l_n, m_n)_{n=1}^t: l_n, m_n,t\in\mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}$$ and suppose that $T$ is some subset of $P$. Suppose that $T$ also has the following properties: ...
0
votes
1answer
186 views

Games and Ramsey's theorem

Here, we identify subsets of $\mathbb{N}$ with sequences obtained by listing the members of the set in strictly increasing order. Suppose that we have some set $\mathcal{F}$ of sets (sequences) of the ...
3
votes
0answers
178 views

Consistency of a tighter bound than given by Erdős–Rado in a special case

Let $0 < n, \ell$ be natural numbers with $n < \ell$. We will define a function $F_{n\ell}(\kappa)$ on infinite cardinals indexed by $n$ and $\ell$. To compute $F_{n\ell}(\kappa)$ let $A$ be a ...
2
votes
0answers
97 views

Coloring triples in trees

Definitions Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...
5
votes
0answers
67 views

Consequences of Ramsey-numbers of hypergraphs

We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent ...
1
vote
0answers
105 views

Is the Upper Banach density always zero with respect to some sequence of Finite subset

The following question came to me while reading the paper 'Density in Arbitrary Semigroups' by Hindman and Strauss. Question: Given an infinite subset $A$ of $\mathbb{N}$ such that $A^c$ is also ...
8
votes
0answers
212 views

Metrically Ramsey ultrafilters

On Thuesday I was in Kyiv and discussed with Igor Protasov the system of MathOverflow and its power in answering mathematical problems. After this discussion Igor Protasov suggested to ask on MO the ...
1
vote
0answers
147 views

Induction on the number of edges $(-1)^wI(G)\leq (-1)^w\sum_{i=0}^w(-1)^ig_i.$

I need help with this theorem about graph theory. In Some Graph Theoretic Results Associated with Ramsey's Theorem of Graver and Yackel find this proposition 5. Proposition 5: Let $G$ be a graph with ...
6
votes
1answer
223 views

Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?

Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...
4
votes
1answer
150 views

Partition Calculus and Ramsey theory question

These topics are outside of my area of research, so I am not quite sure where in the literature to find the answers. In what follows, if $X$ is partially ordered and $n$ is a natural number, let $[[...
10
votes
1answer
423 views

Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
4
votes
0answers
137 views

The set of homogeneous solutions of a clopen contains an hyperarithmetical set

In the context of Galvin-Prikry generalization of Ramsey's theorem, I read in a couple of papers ([1],[2]) that Solovay [3] proved that if $P$ is a clopen of $[\mathbb{N}]^{\mathbb{N}}$ then the set ...
8
votes
1answer
332 views

A combinatorial property of uncountable groups, II

Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that 1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and 2) for any function $\...
6
votes
1answer
224 views

A combinatorial property of uncountable groups

Let $A,B$ be two uncountable sets in a group $G$ such that for any elements $x,y\in G$ the intersection $xA\cap yB$ is finite. Let $\Phi:G\to 2^G$ be a function assigning to each element $x\in G$ some ...
7
votes
0answers
555 views

$R(3,6) = 18$, especially proving that $R(3,6)>17$

I'm studying the Ramsey numbers, especially $R(3,6) = 18$ I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
1
vote
1answer
60 views

monochromatic induced subgraph in a complete 3-partite graph

$H=(V_1\cup V_2 \cup V_3, E)$ is a complete $3$ partite graph such that $|V_1|=|V_2|=|V_3|=n$ . Color the edges with three colors. My question is: Is it possible to find sets $V_1' \subset V_1, V_2' ...
1
vote
0answers
71 views

Equivalent condition for Poincare polynomial

I have found a statement in the introduction of the paper 'Sets of Recurrence and Generalized Polynomials' by Bergelson & Haland, which is Result: Given a polynomial $p \in \mathbb{R}[x]$ such ...