Skip to main content

Questions tagged [ramsey-theory]

Use for questions in Ramsey Theory, i.e. regarding how large a structure must be before it is guaranteed to have a certain property. Please be especially careful not to ask open questions in this tag.

Filter by
Sorted by
Tagged with
1 vote
1 answer
93 views

What does $[S]^k$ mean if $S$ is a set?

I am trying to understand a statement of Ramsey's theorem quoted by Karen R. Johannson in "Variations on a theorem by van der Waerden". She states, For every $k, m, r \in \mathbb{Z}^+$ there ...
mathy_mathema's user avatar
2 votes
1 answer
71 views

How many ways are there to $2$-Color an $N$ by $N$ Grid such that there is at least one $3$ by $3$ Square?

Given an $N$ by $N$ grid, how many ways are there to $2$-color the grid such that there is at least one $3$ by $3$ grid with all its four corners having the same color? Initially I had this expression ...
mathy_mathema's user avatar
0 votes
0 answers
29 views

Whether we can use the dual Ramsey theorem to prove the finite Ramsey theorem?

The dual Ramsey theorem was firstly proved by Graham and Rothschild in 1971, it said that for the natural number $d$,$k$,$l\in\omega$, there exists a natural number $m$ such that for each $d$-...
DJFrank's user avatar
3 votes
2 answers
98 views

Maximum number of colors for embedding all colored perfect matchings in the complete graph

For given $n>1$ I'm looking for the maximum number $k$ of colors such that there exists a $k$-coloring of the edges of the complete graph on $2n$ vertices with the property that a copy of every ...
Matija's user avatar
  • 3,568
1 vote
1 answer
62 views

Existence of Identically-2-colored Equidistant Points on the Integers

I was wondering if every 2-coloring of the integer set would result in some number of equidistant (equally-spaced) points. I proved that there will always be 3 equally-spaced points of the same color, ...
mathy_mathema's user avatar
0 votes
0 answers
24 views

Bound on the number of monochromatic $K_i$ in a $K_k$ free colored graph

I have a question that I need help with. Suppose you have some integers $k,q$ and $N$ and a fixed q-coloring on the edges of $K_N$ such that it contains no monochromatic $K_k$. Is there a nice way to ...
Immanuel Q's user avatar
3 votes
1 answer
47 views

Across all additive bases $A$ of $\mathbb{N}\setminus\{1\}$ of order $2$, what is the maximum possible value of the $n-$th term of $A?$

Across all additive bases $A\subset \mathbb{N}$ of $\mathbb{N}\setminus\{1\}$ of order $2$, what is the maximum possible value of the $n-$th term of $A?$ For example, across all additive bases of $\...
Adam Rubinson's user avatar
0 votes
1 answer
31 views

Question on permutations of a rectangular array.

Consider an $m\times n$ array $A$; that is, $A=\{(s,t)\mid 1\leq s\leq m,\,1\leq t\leq n\}$. Let $f$ be a permutation of $A$. Is it necessarily true that there exist a set $$ B=\{ (1,x_1),(2,x_2),...,(...
Emil Sinclair's user avatar
1 vote
1 answer
144 views

Need help understanding some proof examples

I tried asking r/learnmath twice and got no replies unfortunately, so I'm going to repost it here: These are example proofs from Proofs by Jay Cummings, so I'm not sure if I need to 'show work' ...
wyboo's user avatar
  • 45
1 vote
0 answers
25 views

Upper bound $R_k(s)$

Let $R_k(s)$ be the k-color Ramsey number (i.e., R_3(s)=R(s,s,s) and so on). I want to show that $R_k(s)\leq k^{ks}$. My idea was to use induction on $s$ (for every $k$ fixed). Assuming it is true for ...
user123456's user avatar
2 votes
1 answer
85 views

Existence of a monochromatic $C_{2k + 1}$ implies the existence of a monochromatic $C_{2k}$.

Theorem: Consider a 2-coloring of the edges of the complete graph $K_n$, and let $k \geq 3$. Prove that if there is a monochromatic $C_{2k + 1}$, then there is a monochromatic $C_{2k}$. Attempt: ...
Alaattin Kırtışoğlu's user avatar
0 votes
1 answer
68 views

Prove number of single color triangles in complete graph

Problem: Let $K_n$ be a complete graph with $n$ nodes. Let $n \ge 6$. Prove that if we color this graph with two colors, then there will be at least: ${n\choose 3} / {6\choose 3}$ single color ...
popcorn's user avatar
  • 311
2 votes
1 answer
78 views

An upperbound for $R(3,p)$

For $p\geq 3$, $R(3,p)\leq \frac{p^2+3}{2}$ I tried making use of the following result. For $k,l\geq 2$, $R(k,l)\leq {{k+l-2} \choose {k-1}}$. I got upper bound $\frac{p^2+p}{2}$. Is there a result ...
andimon's user avatar
  • 33
0 votes
0 answers
37 views

natural induction with floor function and factorial

I am solving the following intermediate question to a problem about Ramsey Theorem. Let $r_n=R(p_1,\ldots,p_n)$ with $p_i=3$ for each $i \in [n]$. Given that $r_2=R(3,3)=6$ use $r_n \leq n (r_{n-1}-1)+...
andimon's user avatar
  • 33
2 votes
1 answer
148 views

Red-blue coloring of the complete graph $K_n$​ such that there are more red edges than blue edges, and there is no red triangle.

Let us prove that for every $n>1$ there exists a $2$-coloring of a complete graph $K_n$ red and blue, where there are more red edges than blue and there is no monochromatic red triangle, where all ...
Norbi's user avatar
  • 69
2 votes
0 answers
84 views

When is the sum of reciprocals of positive integers convergent?

I'm looking for sufficient conditions on an infinite $\Lambda\subseteq\mathbb{Z}_+$ so that $$\sum_{n\in\Lambda}\frac{1}{n}<\infty.$$ I know that the contraposition of this question is given by ...
Miles Gould's user avatar
1 vote
0 answers
67 views

Proof that for three coloring there exists $x + y = 2z$.

It’s an extension of Schur’ Theorem. I need to proof that there exist $N$ such that for any coloring of first $N$ natural numbers in three colors there will be three one colored numbers $x, y, z$ such ...
Daniil's user avatar
  • 93
2 votes
0 answers
43 views

Finding the maximal graphs to find the Ramsey number $R(P_4,C_7)$

For my introduction to combinatorics class, we are being asked to compute the Ramsey number for $R(P_4,C_7)$ where $R(P_4,C_7)=k$ is the minimum number of vertices needed such that the 2-coloring of $...
DoubleV's user avatar
  • 491
0 votes
0 answers
51 views

Spherical Cap containing Independent points in Erdös-Bollobás Graph.

This is in reference to the paper On a Ramsey-Turán Type Problem On Page 3, the authors claim that the maximum number of independent points in the constructed graph is atmost equal to the area of the ...
total dependent random choice's user avatar
5 votes
1 answer
94 views

Monochromatic square in colored plane

Square Theorem. Color every point in the real plane using a finite amount of colors. Show there exists a square whose vertices are monochromatic. I am aware this question is a duplicate, however, the ...
Alma Arjuna's user avatar
  • 3,801
1 vote
1 answer
240 views

What is a better bound on Ramsey numbers?

We have: $$R(\underbrace{3,\ldots,3}_{n\ 3's})=m\implies R(\underbrace{3,\ldots,3}_{n+1\ 3's})\leq(n+1)m-n+1$$ And: $$R(l,l)=m\implies R(l+1,l+1)\geq m+\left\lceil\frac{m-l}{l-1}\right\rceil$$ Can we ...
Roddy MacPhee's user avatar
0 votes
1 answer
103 views

Conjecture: Ramsey Number R(m,n)=(2m-1)*p(2m-6+n,m)+{1,m,m+1}, for 3<=m<=n

Today(2023-11-22), I have a conjecture on Ramsey numbers. Fence Conjecture(栅栏猜想): Ramsey Number R(m,n)=(2m-1)*p(2m-6+n,m)+{1,m,m+1}, for 3<=m<=n. Here p(n,k) denotes both the number of ...
a boy's user avatar
  • 841
1 vote
1 answer
46 views

Is it possible to get multiple bounds from the Ramsey-like recursion $f(t) \leq f(t-1)^2$?

The motivation for this question comes from recursions found in Ramsey theory. The Ramsey number $R(s,t)$ is equal to the minimum $n$ such that for any red-blue coloring of the edges of some $K_n$, ...
CoArp's user avatar
  • 417
1 vote
1 answer
82 views

Which big-Omega meaning re Ramsey number r(4, t)?

In https://arxiv.org/pdf/2306.04007.pdf, Mattheus and Verstraete prove that the Ramsey number $r(4,t) = \Omega(t^3/\log^4 t)$ as $t \rightarrow \infty$. Which of the two incompatible definitions of $\...
murray's user avatar
  • 778
1 vote
1 answer
55 views

Super Ramsey's Theorem

The following is the infinite version of Ramsey's Theorem Ramsey's Theorem Given positive integers $r$ and $n$, if the subsets with $n$ elements of the infinite set $X$ are colored, each with one of $...
Alma Arjuna's user avatar
  • 3,801
0 votes
0 answers
64 views

K7 Has 4 Monochromatic Triangles

James Van Lint and RM Wilson's book A Course in Combinatorics poses the following problem: Let the edges of $K_7$ be colored red and blue. Show that there are at least four subgraphs $K_3$ >with ...
Yonas Oberlin's user avatar
0 votes
0 answers
18 views

Does this type of sequence apply to ramsey theory [duplicate]

say we have a sequence $x_1,x_2,x_3...$ with y terms, and one rule that for $i\ge1$ and $n\ge0$ $$x_i,x_{i+1}...x_{i+n}\ne x_{i+n+1},x_{i+n+2}...x_{i+2n+1}$$ so for some example, when $y=1$, would be ...
Michael Toth's user avatar
1 vote
0 answers
95 views

Van der Waerden's theorem through Ramsey's Theorem

Van der Waerden's Theorem Given positive integers $r$ and $k$, there is some number $N$ such that if the integers $\{1, 2, \dots, N\}$ are colored, each with one of $r$ different colors, then there ...
Alma Arjuna's user avatar
  • 3,801
2 votes
1 answer
104 views

Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$ For given integers $d>0$, $k>1$ ...
Matija's user avatar
  • 3,568
1 vote
1 answer
174 views

Do large sets have this specific type of self-similarity?

Suppose $(a_n)_{n\in\mathbb{N}}$ is a strictly increasing sequence of positive integers such that $\displaystyle\sum_{n\in\mathbb{N}} \frac{1}{a_n}$ diverges, i.e. $(a_n)_{n\in\mathbb{N}}$ is "...
Adam Rubinson's user avatar
2 votes
1 answer
128 views

For every large set $A\subset \mathbb{N},$ there is a concave subsequence of $A$ of length $k$ for every $k\in\mathbb{N}$.

Proposition: Suppose $A\subset \mathbb{N}$ is a large set in the sense that $$ \sum_{n\in A} \frac{1}{n} = \infty.$$ Then there exists $a_1 < a_2 < \ldots < a_k,\ $ (not necessarily ...
Adam Rubinson's user avatar
3 votes
0 answers
107 views

$n$-in-arithmetic-progression: a maker-breaker game

Consider a 2-player game where the players take turns claiming an integer from $1$ to $n$. The same integer cannot be claimed twice. Player 1 wins if the set of integers he claims contains an ...
Michał Zapała's user avatar
0 votes
0 answers
22 views

Is there a number $n_0$ s.t. every graph with $n \geq n_0$ contains a $\lfloor n/2\rfloor $ clique or independent set.

Cheers I came across the following: True or False question: Is there a number $n_0$ s.t. every graph with $n \geq n_0$ contains a $\lfloor n/2\rfloor $ clique or $\lfloor n/2\rfloor $-independent set? ...
average_discrete_math_enjoyer's user avatar
1 vote
1 answer
42 views

Upper bounds for $ES(n)$ from the first proof of Erdos and Székeres (1935)

I'm studying the proof of Erdos and Székeres, from 1935. Both proofs are quite clear to me, specially the second (geometric) one, as its bounds on $ES(n)$. However, I can not see which bounds were ...
Anyway142's user avatar
  • 456
2 votes
0 answers
67 views

Does there exist a maximal subset of arithmetic progressions of length $k,$ such that any additional numbers will result in an A.P. of length $k+2?$

Fix $k\in\mathbb{N}.$ Definition: A set $A\subset\mathbb{N}$ (with $\vert A \vert = \infty$) is maximal of length $k$ if it contains at least one arithmetic progression of length $k,$ and, if $x\not\...
Adam Rubinson's user avatar
2 votes
1 answer
96 views

Every set of size $2^n-1$ has a subset of size $2^{n-1}$ that sums to a multiple of $n$

Is the following statement true? If so, how can it be proved? Every set of $2^n-1$ positive integers, $n\in\{1,2,\dots\}$, has a subset of size $2^{n-1}$ that sums to a multiple of $n$. An attempt ...
Evan Aad's user avatar
  • 11.4k
5 votes
1 answer
230 views

Ultrafilter proof of the infinite Ramsey Theorem

The Infinite Ramsey Theorem ($\mathsf{RT}$) is the statement For any $r,p\in\mathbb{N}^{+}$ and any infinite set $A$, any $r$-coloring $c$ of $[A]^{p}$ has an infinite homogeneous subset. Where $[r] ...
John's user avatar
  • 4,362
4 votes
1 answer
113 views

Basic Ramsey arrow notation property

I’m having difficulties proving the following: „Let $a, b, c, d$ and $d^{\prime}$ be cardinals with $d^{\prime}\le d$. Then $a\to(b)_c^d$ implies $a\to(b)_c^{d^\prime}$.“ Here’s what I know: We can ...
ILUD0R's user avatar
  • 75
4 votes
1 answer
216 views

Modern exposition of Ramsey's famous paper "On a problem of formal logic"

I am interested in Ramsey's original motivation for proving the Ramsey theorem (on finding some set for which the coloring on its subsets are constant, for any given coloring of subsets). This link ...
D.R.'s user avatar
  • 8,711
4 votes
1 answer
140 views

Coloring arithmetic progression

I've been looking at some old notes from the course Probabilistic Combinatorics and I saw the following question: Prove that there exists a constant $N$ and a red/blue coloring of $\mathbb{Z}$ ...
DIexp's user avatar
  • 150
1 vote
1 answer
76 views

Finite Ramsey Theorem via many-sorted logic compactness + infinite Ramsey theorem

Here you will find the relevant definitions, statements of Ramsey's theorems, and how propositional compactness + infinite Ramsey Theorem ($\mathrm{IRT}$) can be used to prove the finite Ramsey ...
John's user avatar
  • 4,362
1 vote
1 answer
154 views

Finite Ramsey theorem via first-order compactness + infinite Ramsey theorem

The relevant definitions regarding notation, and the statements of Ramsey's theorems, can be found at the beginning of this question. There, I asked, and later provided an answer (mostly correct, as ...
John's user avatar
  • 4,362
5 votes
2 answers
302 views

Finite Ramsey theorem via propositional compactness + infinite Ramsey theorem

Consider the following statements: Finite Ramsey Theorem ($\mathrm{FRT}$): For any $k,r,p\in\mathbb{N}^{+}$, there exists $N\in\mathbb{N}$ such that every function $c:[N]^{p}\rightarrow [r]$ has a ...
John's user avatar
  • 4,362
0 votes
2 answers
217 views

Is there true randomness?

In a paper titled "Quantum Randomness: From Practice to Theory and Back", Cristian S. Calude concludes that there is no true randomness in numbers: "The “magic” of the quantum ...
Willpergg's user avatar
3 votes
0 answers
73 views

Why does $\mathsf{WKL}_{0}$ not prove Ramsey's Theorem for singletons?

Consider the satement $\mathsf{RT}^{p}$ (Infinite Ramsey's Theorem for exponent $p\in\mathbb{N}$): For any $r\in\mathbb{N}$, and for any function $c:[\mathbb{N}]^{p}\rightarrow [r]$, there exists an ...
John's user avatar
  • 4,362
5 votes
1 answer
201 views

What are the proof-theoretic strengths of Ramsey's theorems?

The proof-theoretic strength of a theory is measured by the $\mathsf{\Pi}_{1}^{1}$-ordinal of the theory (indeed, there are other ordinal analyses, like the $\Pi_{2}^{0}$-ordinal of the theory). ...
John's user avatar
  • 4,362
7 votes
2 answers
277 views

Given increasing sequence of numbers, what is guaranteed min length the longest subseq. s.t. differences of terms are either decreasing or increasing?

It would be better if I could fit "differences of consecutive terms" in the title, but I ran out of space. Anyway, here is a more precise version of my question: Given $n,$ for any given ...
Adam Rubinson's user avatar
2 votes
1 answer
61 views

Reference request: infinitary Ramsey theory

I was reading about the (various) infinite versions of Ramsey's theorem, and stumbled across a text containing a proof of the Bolzano-Weierstrass Theorem using it: Unfortunately, I forgot where I ...
Roy Sht's user avatar
  • 1,339
5 votes
1 answer
152 views

Edges of each colour for Ramsey Graphs

Consider a 2-coloring of the edges of a complete graph $K_{n}$. Assume it doesn't exhibit a monochromatic subgraph of $m$ vertices thus demonstrating that the Ramsey number $R(m,m)$ is greater than $n$...
tex94's user avatar
  • 83
0 votes
1 answer
103 views

Variant of Erdos-Szekeres theorem

I'm having trouble proving the following theorem: For all $n \in \mathbb{N},$ $\exists$ $N \in \mathbb{N}$ such that any set of $N$ points in the plane will contain either a convex $n$-gon or $n$ ...
jackyooo's user avatar
  • 149

1
2 3 4 5
14