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$.
222 questions
0
votes
0
answers
58
views
Co-boundary crossed homomorphism & "sign" preserving. Why 2-valued components is special?
Suppose $h_{g}: \mathbb{R}^n \to \mathbb{R}^{n-1}$ be a coboundary crossed homomorphism with action $g$ as a cyclic permutation of coordinates on $\mathbb{R}^n$ vectors. So, the acting group is a ...
- 11
0
votes
2
answers
99
views
Is there an uncountable extension of the Ramsey set $[\omega]^2$?
We say that a family ${\cal A}\subseteq {\cal P}(\omega)$ is Ramsey
if for every map $c:{\cal A}\to\{0,1\}$ there is an infinite set $X\subseteq \omega$
with the following properties:
${\cal A}\cap {\...
- 48.8k
8
votes
1
answer
255
views
Maximal Ramsey families
We say that a family $\mathcal R\subseteq \mathcal P(\omega)$ is Ramsey if
$\bigcup \mathcal R = \omega$, and
for every map $f:\mathcal R \to \{0,1\}$ there is an infinite set $X\subseteq \omega$
...
- 48.8k
-3
votes
1
answer
73
views
Non-Ramsey function $f:[\omega]^{<\omega}\to\{0,1\}$ [closed]
Let $\newcommand{\o}{\omega}\o$ be the set of non-negative integers, and for any set $X$, let $\newcommand{\oo}{[\o]^{<\o}}X^{<\o}$ denote the collection of all finite subsets of $X$.
What is an ...
- 48.8k
7
votes
2
answers
331
views
Does every subset of $\mathbb N$ with full natural density contain arbitrarily long geometric progressions?
We use the standard definition of natural density. We say a subset of $\mathbb N$ has full natural density if it has natural density $1$.
Question: Does every subset of the naturals with full natural ...
- 6,155
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
6
votes
0
answers
164
views
A pre-Ramsey set that is not Ramsey
$\newcommand{\N}{\mathbb{N}}$
Recall that given a $A \in [\N]^\omega$ and $a \in [A]^{<\omega}$, the Ellentuck neighbourhood is defined to be:
$$
[a,A] := \{B \in [\N]^\omega : a \sqsubseteq B \...
- 1,370
3
votes
2
answers
157
views
Modification of Lemma 0 in Hajnal's paper "Embedding finite graphs into graphs colored with infinitely many colors"
I am looking for a proof of the following lemma.
Let $E_0$ be the set of edges of an undirected graph with no loops with vertex set a cardinal $\kappa$. Let $E_1$ be the family of two-element subsets ...
- 1,644
17
votes
1
answer
1k
views
Can the Pythagorean Graph be finitely colored?
Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...
- 5,103
11
votes
0
answers
488
views
Are there 100 points that are part of every half-density part of the plane?
Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...
- 18.7k
4
votes
0
answers
224
views
A probabilistic proof of van der Waerden theorem
Is there an elementary proof of van der Waerden's theorem on arithmetic progressions using probabilistic methods?
- 32.1k
3
votes
2
answers
493
views
Why can we not find exact values for sizes of cap sets for $d>6$?
I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...
- 41
10
votes
1
answer
392
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 ...
- 2,286
4
votes
0
answers
113
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., ...
- 557
34
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(...
- 679
1
vote
2
answers
130
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$-...
- 3,499
1
vote
1
answer
200
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,\...
- 3,499
5
votes
1
answer
368
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 ...
- 383
9
votes
1
answer
247
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$...
- 48.8k
0
votes
0
answers
86
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
95
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 ...
- 851
4
votes
0
answers
157
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,499
2
votes
1
answer
224
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$), ...
- 1,561
4
votes
1
answer
190
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 ...
- 3,499
4
votes
1
answer
226
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 ...
- 505
8
votes
1
answer
392
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$ ...
- 3,499
2
votes
1
answer
152
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$, $\...
- 129
0
votes
1
answer
140
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/...
- 73
3
votes
0
answers
156
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,...
- 85
4
votes
0
answers
195
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 ...
- 189
11
votes
1
answer
328
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-...
- 7,125
11
votes
1
answer
395
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 ...
- 3,499
12
votes
0
answers
240
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 ...
- 7,125
3
votes
0
answers
176
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 $\...
- 37.7k
5
votes
0
answers
91
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 ...
- 51
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 ...
- 473
2
votes
1
answer
166
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 ...
- 21
9
votes
1
answer
513
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 ...
- 48.8k
1
vote
0
answers
93
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 ...
- 3,499
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 ...
- 4,862
0
votes
1
answer
78
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 "...
- 115
1
vote
0
answers
90
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+...
- 341
8
votes
0
answers
232
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 $...
- 32.5k
6
votes
1
answer
264
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 ...
- 1,370
6
votes
1
answer
328
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,370
1
vote
0
answers
52
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). ...
- 4,776
1
vote
0
answers
99
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:\...
- 4,776
3
votes
2
answers
273
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}...
- 227
7
votes
2
answers
595
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 ...
- 71
7
votes
0
answers
144
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 $...
- 1,005