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$.
213
questions
11
votes
0
answers
479
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 ...
4
votes
0
answers
193
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?
2
votes
2
answers
335
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$. ...
10
votes
1
answer
374
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 ...
4
votes
0
answers
95
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., ...
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(...
1
vote
2
answers
124
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$-...
1
vote
1
answer
161
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,\...
5
votes
1
answer
307
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 ...
8
votes
1
answer
238
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$...
0
votes
0
answers
80
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
94
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 ...
4
votes
0
answers
128
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 ...
2
votes
1
answer
205
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$), ...
4
votes
1
answer
148
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 ...
4
votes
1
answer
221
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 ...
5
votes
0
answers
163
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$ ...
2
votes
1
answer
146
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$, $\...
0
votes
1
answer
91
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/...
3
votes
0
answers
114
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,...
4
votes
0
answers
186
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 ...
11
votes
1
answer
296
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-...
10
votes
1
answer
316
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 ...
12
votes
0
answers
222
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
159
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
86
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
140
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
487
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 ...
1
vote
0
answers
85
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 ...
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 ...
0
votes
1
answer
75
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
83
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+...
8
votes
0
answers
223
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
261
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
310
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
49
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). ...
1
vote
0
answers
97
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
votes
2
answers
256
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
556
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
139
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
115
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
0
answers
863
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
116
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
89
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
2
answers
1k
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
1
answer
142
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
1
answer
179
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
146
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
1
answer
323
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 ...