10
votes
2answers
463 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 ...
3
votes
1answer
592 views

Big binary tree as an induced subgraph

I believe this is true: Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line ...
2
votes
1answer
181 views

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
4
votes
2answers
120 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 ...
7
votes
2answers
416 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 ...
1
vote
1answer
95 views

Distribution of Induced Subgraphs of Extremal Ramsey Graphs

Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to \{r, b\}$ be an edge 2-coloring such that there is no monochromatic ...
-1
votes
1answer
178 views

What is a Ramsey Graph? [closed]

Can anyone explain me what is a Ramsey Graph with a simple example? What are its properties?
8
votes
3answers
826 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 ...
5
votes
1answer
390 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,Ⅲ. ...
2
votes
1answer
173 views

A Ramsey-like lower bound?

Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there ...
1
vote
1answer
379 views

Combinatorial optimization and graph coloring

I am considering the following problem: (i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily. (ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow ...
2
votes
0answers
232 views

Slightly improving bounds on two-color Ramsey numbers by globally pruning edges and counting connected vertices in instances of two-colored complete graphs

The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms ...
1
vote
2answers
372 views

Quasi-Ramsey Graphs

A graph with number of vertices less than R(n,n)-1, is called quasi-Ramsey of case n, if it has no complete graph Kn in itself or its complementary graph, and if added another vertex, no matter how it ...
13
votes
3answers
724 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 ...
20
votes
1answer
1k 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
314 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
1answer
376 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.
3
votes
2answers
498 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?
8
votes
2answers
891 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
1answer
313 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
640 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 ...
8
votes
5answers
941 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 ...