The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
278 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 ...
3
votes
0answers
104 views

Bound on how many 2-colored graphs have maxredclique $i$, maxblueclique $j$

Fix $i,j$. I want a bound $F(i,j)$ on the following: $\sum_{n=1}^\infty$ (the number of 2-colorings of the edges of $K_n$ such that the MAX RED clique is size exactly ...
4
votes
2answers
601 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 ...
3
votes
1answer
449 views

Permutations of Grid Colorings

Hello all, This question arises out of a Ramsey-theoretic study related (but tangential) to this question on CSTheory: Grid $k$-coloring without monochromatic rectangles. Background: In general, we ...
7
votes
2answers
651 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 ...
2
votes
3answers
626 views

Arithmetic progressions of length 3 in subset of Z_n of size n^d

Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0< d <1$). Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$. [The ...
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 ...
4
votes
1answer
628 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? ...
17
votes
3answers
561 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 ...
13
votes
3answers
745 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 ...
1
vote
0answers
235 views

Any 2-coloring of the scope of equilateral triangle must create a monochromatic rectangular triangle ?

Hello All, I'm trying to prove something that we know that is correct but can't find how to do it or any example to show how to solve it. Any 2-coloring of the scope of equilateral triangle must ...
11
votes
2answers
616 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 ...
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 ...
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 ...
2
votes
2answers
1k views

Proofs of Lower Bounds for Ramsey Numbers?

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...
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)$, ...
18
votes
2answers
771 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$ ...
2
votes
1answer
380 views

Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear? It seems to be a natural problem to ask. but I could not find any reference. Thanks.
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 ...
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 ...
3
votes
2answers
626 views

Where can I find a catalog of known Ramsey numbers?

Is there an online catalog available of Ramsey numbers, preferably one that for unknown values documents the known upper/lower bounds?
16
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) ...
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 ...
8
votes
2answers
986 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}$. ...
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
1answer
339 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
2answers
702 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 ...
13
votes
4answers
838 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 ...
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 ...