All Questions
Tagged with infinite-combinatorics ramsey-theory
18 questions
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
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
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
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
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
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
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
2
votes
1
answer
147
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 \...
- 59
6
votes
2
answers
117
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\}$ ...
- 48.8k
2
votes
1
answer
117
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 \...
- 764
6
votes
1
answer
284
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|$ ...
- 1,203
8
votes
1
answer
360
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 $\...
- 41.8k
6
votes
1
answer
246
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 ...
- 41.8k
20
votes
1
answer
1k
views
On Erdös–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 $\neg \mathit{CH}$ in Erdös and Kakutani - On non-denumerable graphs (...
3
votes
2
answers
672
views
Partition calculus question
For $m,n,k < \omega$, consider the equation
$X \to (\omega \times k)^{m}_{n}$
What is the smallest $X$ known to satisfy it?
Baumgartner-Hajnal theorem gives a satisfactory answer for $m=2$, but ...
- 341