The tag has no wiki summary.

learn more… | top users | synonyms

30
votes
4answers
2k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
25
votes
0answers
613 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
22
votes
5answers
5k views

Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
20
votes
1answer
2k views

Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
19
votes
1answer
3k views

Reconstructing the argument that yields Graham's number

Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern ...
18
votes
2answers
761 views

Ramsey multiplicity

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ ...
17
votes
3answers
560 views

Ergodic limits along subsets of $\mathbb{N}.$

Let say that an infinite subsets $A$ of $\mathbb{N}$ is "nice w.r.to ergodic limits", if it can replace $\mathbb{N}$ in the individual ergodic theorem, that is, if it is such that the following ...
15
votes
10answers
3k views

Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...
13
votes
4answers
830 views

Splitting pythagorean triples

Can one partition the set of positive integers into finitely many pythagorean-triple-free subsets? If so, what is the smallest number of such subsets? Taking a wild guess, I would be least surprised ...
13
votes
3answers
739 views

Differences of near diagonal Ramsey numbers.

I am a graduate student trying to get involved in Ramsey theory. My question comes from: Erdős on graphs: his legacy of unsolved problems By Fan R. K. Chung, Paul Erdős, Ronald L. Graham p.14 of ...
12
votes
6answers
16k views

Magnitude of Graham's Number?

I recently stumbled across this number, and then (foolishly, most likely) decided to try to describe it in a blog post http://frothygirlz.com/2010/01/14/big-numbers-part-2/ Q - Are there any ...
12
votes
2answers
2k views

Noncombinatorial proofs of Ramsey's Theorem?

I know of 2(.5) proofs of Ramsey's theorem, which states (in its simplest form) that for all $k, l\in \mathbb{N}$ there exists an integer $R(k, l)$ with the following property: for any $n>R(k, l)$, ...
11
votes
2answers
683 views

Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result: if $\mu$ is ...
11
votes
2answers
608 views

monochromatic cycle-free colouring of the complete graph on R?

Hi So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 ...
11
votes
3answers
366 views

Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
10
votes
2answers
512 views

Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$, there exists some graph $G$ whose every embedding into $\mathbb{R}^3$ (or into $\mathbb{S}^3$) contains a cycle that realizes $K$? I know the ...
10
votes
2answers
518 views

Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is: For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...
10
votes
3answers
773 views

Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there? I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem. ...
9
votes
2answers
369 views

From very many sets of fixed measure in a probability space, can we select many that have a positive intersection?

I assume the following Lemma is either well known or, more probably, a Corollary of a much stronger well known Theorem, and I would be grateful for a reference: For all $\delta\in (0,1)$ and all ...
9
votes
1answer
383 views

Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$. Is it possible that there ...
8
votes
2answers
976 views

Ramsey Theory, monochromatic subgraphs

If we have the complete countably infinite bipartite graph $K_{\omega,\omega}$ and we colour the edges with just two colours. Should we expect to get a monochromatic copy of $K_{\omega,\omega}$. ...
8
votes
3answers
918 views

A General Framework for Ramsey Theory ?

There are few results in modern mathematics that I find so deep and full of philosophical implications as Ramsey's theorem. I am aware (at some basic level) that it has generated a plethora of ...
8
votes
5answers
1k views

Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number R(k). Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...
7
votes
3answers
787 views

Is this Ramsey-type problem an open problem?

A blog claims that the following Ramsey-type (or van der Waerden type) problem is open: If the natural numbers are colored with finitely many colors, must there exist x and y (not both 2) such that ...
7
votes
3answers
321 views

Extracting countable chains from linear orders

There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$ (by ...
7
votes
3answers
851 views

A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...
7
votes
2answers
461 views

Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's book Subsystems of second order ...
7
votes
2answers
646 views

Asymptotics for Ramsey Theory

Ramsey Theory says that every sufficently large (but finite) complete graph having $d-$coloured edges contains a monochromatic complete subgraph with $k$ vertices. One could ask for asymptotics: Let ...
7
votes
2answers
496 views

Combining van der Waerden's theorem with Ramsey's theorem

Consider positive integers $c$, $k$, and $s$. Does there exist some $N = N(c,k,s)$ such that the following holds? Take any $c$-coloring of the $k$-tuples of integers in $[1,N]$. Then there is an ...
6
votes
2answers
110 views

Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$. ...
6
votes
1answer
277 views

3x3 submatrix with only $0$ or $1$ entries

I decided to cross-post the question here from math.stackexchange.com because I got no answer from there. It is a quick question on bipartite Ramsey numbers (I'm not an expert on the subject, so ...
6
votes
0answers
155 views

A generalization of SOCA

Roughly speaking, SOCA (Semi Open Coloring Axiom) says that for an open coloring of the unordered pairs over an uncountable separable metric space you can always find an uncountable homogeneous subset ...
6
votes
0answers
81 views

Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity. See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$. Is there an ...
5
votes
5answers
1k views

Bound on cardinality of a union

Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection ...
5
votes
2answers
689 views

Infinite Ramsey theorem with infinitely many colours

Clearly, it is possible to colour the edges of an infinite complete graph so that it does not contain any infinite monochromatic complete subgraph. Now what about the following? Let $G$ be the ...
5
votes
2answers
512 views

The Problem about 2-coloring finite plane

Suppose we color a $X \times X$ finite plane by red and blue arbitrarily. How large does X need to be to guarantee a monochromatic combinatorial square $k \times k$ 1 0 1 0 1 1 1 1 1 1 1 1 1 ...
5
votes
2answers
252 views

Bounds on a partition theorem with ambivalent colors

I've been running into the following type of partition problem. Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n ...
5
votes
1answer
336 views

Non trivial colouring of the edges of an infinite complete graph

Can you build a probabilistic scheme for colouring each edge (independently of all other edges) of the complete graph G on the positive integers such that the probability that G contains an infinite ...
5
votes
1answer
386 views

Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite $F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that, for all but finitely many $s\in S$, $$ ...
5
votes
1answer
450 views

small Ramsey number and Brooks' Theorem

I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. ...
5
votes
1answer
170 views

Sparse ramsey theory

It is known that for any graph H and all $k∈N$, there exists a graph $G$ such that any $k$-coloring of the edges of $G$ yields a monochromatic copy of H and ω(G)=ω(H) (the two graphs have the same ...
5
votes
1answer
749 views

Graham-Rothschild via Hales-Jewett

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild ...
5
votes
0answers
192 views

Van der Waerden like theorem

I am trying to develop bounds for the function B(k) where B(k) is defined as the least such positive integer so that whenever the set $\{1,2,\cdots B(k)\}$ is partitioned into two parts at least one ...
4
votes
2answers
171 views

Is There a Graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free

Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nesetril and Rodl proved that for a graph $G$, there exists a graph $F\to G$ with ...
4
votes
2answers
598 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 ...
4
votes
1answer
621 views

Best lower bound for off-diagonal Ramsey numbers

What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? ...
4
votes
1answer
207 views

Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate. Is the Van der Waerden's function itself elementary in the sense of Kalmar?
4
votes
1answer
181 views

Large bicliques in r-partite graphs containing no independent sets having one vertex from each class

Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a ...
4
votes
1answer
319 views

Ramsey pairs of classes graphs

Motivation Call a set $H$ of vertices of a graph $G$ homogeneous if it is either independent or complete. Every perfect graph of size $n$ has a homogeneous subset of size $\sqrt n$. Noga Alon has ...
4
votes
0answers
149 views

Weak Arithmetic Progressions

I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression. Formally I call a k-sequence $x_1< x_2 \cdots< x_k$ a weak arithmetic progression ...