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

154 questions
Filter by
Sorted by
Tagged with
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 ...
87 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 ...
102 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 ...
116 views

211 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 ...
501 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 ...
145 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. ...
154 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: ...
173 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 ...
170 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 ...
121 views

### Kastanas' game and completely Ramsey sets [closed]

Recently I was reading the article ''On the Ramsey property for sets of reals'' of Ilias Kastanas (https://www.jstor.org/stable/2273667?seq=1#metadata_info_tab_contents), in this article the author ...
94 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)$ ...
61 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 ...
101 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 ...
209 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 ...
108 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 ...
120 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|$ ...
137 views

222 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 ...
397 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 ...
56 views

98 views

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...
882 views

### Almost monochromatic point sets

There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...
196 views

### A funny kind of Ramsey number

A shorter version of this question was posted on Math Stack Exchange. Let $V$ be a nonempty set. $(V,S)$ is a graph if $S\subseteq\binom V2,$ a triple system if $S\subseteq\binom V3,$ a quadruple ...
72 views

### Appearance of “Fat Spiders” in Graphs

When investigating the properties of least detours of edges in complete, weighted graphs, I noticed an interesting phenomenon in the visualization of graphs where the nodes correspond to points in the ...
244 views

### A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...
681 views

### List Ramsey numbers?

The diagonal Ramsey number $R(n,n)$ is the least number $m$ for which the following holds: in any edge-colouring of the complete graph $K_m$ in which each edge is coloured blue or red, there is a ...
1k views

### Ramsey Number R(3,3,4)

How much is known about the Ramsey number R(3,3,4)? There is a trivial upper bound of 34, but are any tighter bounds known?
729 views

### On Erdos-Kakutani like Equivalents of the Failure of Continuum Hypothesis

Among all mysterious equivalents of the Continuum Hypothesis and its negation, there is an algebraic combinatorial equivalent of the $\neg CH$ by Erdos and Kakutani (MR0008136) as follows: Definition. ...
191 views

### Colouring Positive Integers

Does anyone know any reference or proof for the following problem? Let $m$ and $n$ be positive integers, $m,n \geq 2$. Each positive integer is coloured in one of $m$ different colours. Is it ...
107 views

### Set version of ramsey type problem

For two sets of numbers $A,B$, write $A<B$ iff $\max A<\min B$. For a sequence of integers $a_0,\cdots,a_{n-1}>0$, let $Prop(a_0,\cdots,a_{n-1})$ denote the following proposition: Given $n$ ...
325 views

### Ramsey type theorem

Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$. Is the following true? For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
606 views

### Ramsey's theorem for the first uncountable ordinal

Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
174 views

### How many sums vs products are there?

Motivated by applications of Ramsey theory, Schur's theorem states that for any partition of the positive integers into a finite number of parts, one of the parts contains three integers $x, y, z$ ...
I have researched a problem for about 2 years, and I want to know if there exists any previous results (I can't seem to find any). The problem goes: What is the largest subset of a $2k$-dimensional ...
Let $G$ be a minimal $2$-colour Ramsey-graph for $H$. Must there exist a minimal $3$-colour Ramsey-graph $F$ for $H$ with $G\subset F$? I am wondering if anything is known about this, particularly ...