1
vote
0answers
20 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
2
votes
1answer
38 views

Proving an 'obvious' Ramsey upperbound

Here I want to prove the following: $$R(s_{1},s_{2},\ldots ,s_{k}) < R(s_{1}+1,s_{2},\ldots ,s_{k})$$ For $s_{1},\ldots ,s_{k} \in \mathbb{N}$, $s_{i}\geq 2$. (Or can it hold with equality in some ...
0
votes
1answer
21 views

What does $N(q_1, q_2, … , q_s ; r)$ mean in van Lint's stating of Ramsey's Theorem?

I've started reading van Lint and Wilson's A Course in Combinatorics and on Theorem 3.3 (Ramsey's Theorem) they use the notation $N(q_1, q_2, ... , q_s ; r)$ without an explanation prior to it. Can ...
0
votes
1answer
23 views

T/F prove for modified Ramsey's theorem

By Ramsey's theorem we know that: $\forall k \in \mathbb N : \exists N \in \mathbb N$ that an arbitrary graph $G$ on a set of vertices $\{1,2,...,N\}$ contains $k$ vertices, which represent either a ...
0
votes
2answers
42 views

Coloring of $K_{17}$

For any 3-coloring of $K_{17}$ I have to show there exists either a red, blue or green triangle. To start, can I use proof by contradiction with color red, blue, green? So $(0,0,136)$ means all 136 ...
0
votes
1answer
71 views

Two coloring questions and ramsays number

What is the smallest $n$ such that every 2-coloring of edges of $K_n$ contains a red or blue 4-cycle (not $K_4$)? I am given that $R(4,4) \le 18$ and $R(3,5) \le 14$ Any help is greatly appreciated!
1
vote
1answer
42 views

Uncountable monochromatic set

Maybe you can help me with that. I was asking myself if you take an uncountable set $S$ and let $S^{(2)}$ be 2-coloured, must there exist an uncountable monochromatic set in $S$?
1
vote
1answer
39 views

Special Ramsey number $r(G)$

With $r(G)$ I refer to the smallest $n$ such that every blue-red colouring of the edges of $K_n$ contains a monochromatic copy of the grpah $G$ (this exists because $r(G)\le R(|G|)$). Now let $I_k$ ...
0
votes
1answer
16 views

Using Ramsey theory to show some properties of subgraph of a directed graph

Let $r > 1$ be an integer. Prove that there is an integer $n_0$ such that for every integer $n\geq n_0$ and every directed graph $G = (\{1,...,n\}, E)$ without loops, $G$ has an induced ...
0
votes
1answer
106 views

Ramsey Number for Star graphs

For two graphs $H_1$ and H2, the Ramsey number $r(H_1, H_2)$ is the minimum number r so that in any red-blue coloring of the edges of the complete graph Kr on r vertices there is necessarily either a ...
0
votes
1answer
174 views

Consider all colorings of the edges of K6 such that every edge is either colored red or blue…

Consider all colorings of the edges of K6 such that every edge is either colored red or blue. Prove or disprove: there always exist at least two monochromatic triangles in any 2-coloring of the edges ...
1
vote
1answer
45 views

Graph Ramsey Theory for Multiple Copies of Graphs

I had the following question from Graph Ramsey theory. Show that if $m \geq 2$, then $$ R((m+1)K _{3},K _{3})\geq R(mK _{3},K _{3}) + 3. $$ Thanks.
3
votes
3answers
225 views

Does “Big Data” Have a Ramsey Theory Problem?

I'm erring on the side of conservatism asking here rather than MO, as it is possible this is a complex question. "Big Data" is the Silicon Valley term for the issues surrounding the huge amounts of ...
2
votes
1answer
172 views

Six people at a party and its graph theory representation

I'm confused by this classic graph theory problem: Suppose there are six people at a party. Prove that it is always possible to find either three people who all know each other, or three people none ...
1
vote
1answer
67 views

$K_6$ contains at least two monochromatic $K_3$ graphs.

Let $K_n$ be a complete $n$ graph with a color set $c$ with $c=\{\text{Red}, \text{Blue}\}$. Every edge of the complete $n$ graph is colored either $\text{Red}$ or $\text{Blue}$. Since $R(3, 3)=6$, ...
0
votes
0answers
29 views

Practical use of Ramsey numbers [duplicate]

I am fascinated by the Ramsey number, but I was wondering, what are practical uses of the Ramsey number? Except for the party problem, I can not come up with something where it is useful for. Do you ...
2
votes
0answers
19 views

Questions on $R(K_l + \overline{K_t}, T_s) \le l(s-1)+t$

Following C. C. Rousseau and J. Sheehan "A class of ramsey problems involving trees" Journal of London Math. Soc. $1978$, I have some dudes about their proof for $R(K_l + \overline{K_t}, T_s) \le ...
2
votes
1answer
57 views

The Ramsey number $r(t,t,q)$ with $q\geq t$

Let q and t be positive integers with $q\geq t$. Determine the Ramsey number $r_t(t,t,q)$. This is from the book Introductory Combinatorics by Brualdi, and in the back it says the answer is q without ...
2
votes
2answers
137 views

What is a Ramsey Graph?

What is a ramsey graph and What is its relation to RamseyTheorem? In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
1
vote
1answer
82 views

Ramsey and Random Graph

By considering the random graph G(n,p), show that $$R(4,k)>\left ( \dfrac{k}{3\log k} \right )^{3/2} $$ Improve this bound as much as you can.
1
vote
1answer
192 views

A Problem about friends and strangers using Ramsey's Theory

Question: Consider a group of 8 people, each pair of which are either friends or enemies. Show that if some person in the group has at least 6 friends, then there are 4 people who are mutual friends ...
10
votes
2answers
275 views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
2
votes
1answer
205 views

Ramsey Number Inequality

I want to prove that: $$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$ where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ ...
2
votes
1answer
176 views

Ramsey Number proof

I am trying to prove: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$ I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding. edit: $R$ is the Ramsey ...
0
votes
1answer
88 views

Edge coloring graph vertices probability

How to show the following: Let $R(k,t)$ denote the Ramsey function, that is the minimal number $n$ so that if the edges of a complete graph $K_n$ on $n$ vertices are each colored red or blue, then ...
3
votes
1answer
333 views

Graph theory dinner party problem

In a party of 6 people is it true that there exists four people either all do or all do not knowing each Other? I know it's false, and have the solution but not quite sure where to begin with the ...
0
votes
1answer
183 views

Graph theory mutual acquaintance and mutual strangers problem

Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two. There is a solution in the ...
2
votes
0answers
53 views

Van der Waerden number

The Van der Waerden number $w(l,k)$ is the least $n$ such that for every $k$-coloring of $[n]$ has a monochromatic $l$-term arithmetic progression. Prove that $w(l,k)>(lk^{l-1})^{1/2}$ Give some ...
4
votes
2answers
138 views

Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number). I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example ...
4
votes
1answer
118 views

Ramsey number for paths

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that ...
5
votes
3answers
591 views

Good way to learn Ramsey Theory

What are some good books on Ramsey theory? I have Van Lints book on Combinatorics: is this enough preparation to start reading about Ramsey theory? I want a book that includes important results and ...
3
votes
1answer
212 views

Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
3
votes
1answer
91 views

Any forest on 5 or more vertices contains an independent set of size 3.

I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
1
vote
1answer
456 views

Monochromatic triangle and edge colouring

$r(k) := R(\underbrace{3,3,...,3}_k)$ (I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show ...
0
votes
1answer
417 views

Complete graph edge colouring in two colours: lower bound for number of monochromatic triangles

Say $K_n$ is a complete graph. Show that any coloring of edges of $K_n$ with $n \ge 6$ in two colors contains at least $$\frac1{20}\binom{n}3$$ monochromatic triangles. Any ideas on how to use Ramsey ...
2
votes
0answers
75 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...
2
votes
1answer
79 views

2012-gon- subsets of vertices.

Can we prove or disprove this? For a sufficiently large $n$, every set of at least $ n$ points in the plane with no three collinear has a subset that form the vertices of a convex $2012$-gon. Gerry ...
0
votes
2answers
90 views

Complete graph-coloring

Can we prove or disprove the following statement? For any graph $H$ and any coloring $c$ of its edges with two colors, there exists $n$ such that every $2$-coloring of the edges of the complete graph ...
1
vote
2answers
770 views

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only ...
1
vote
2answers
164 views

Ramsey theory - colouring of edges

I'm trying to understand a proof: $R(3,3) = 6$ proof: Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is ...
1
vote
1answer
99 views

Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated. Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue ...
0
votes
3answers
545 views

Party problem / Ramsey's theorem R(3,3)

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not ...
5
votes
1answer
515 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
7
votes
1answer
498 views

Showing that $K_7$ contains at least 4 monochromatic triangles

A problem in my book is: Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic ...
3
votes
2answers
367 views

Lower bound for monochromatic triangles in $K_n$

Say $K_n$ is a complete graph of $n$ nodes, and every edge is either blue or red. I'm trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic ...
3
votes
1answer
427 views

How to prove this relation between Ramsey Numbers: $R(s, t) ≤ R(s, t-1) + R(s-1, t)$ for $s,t>2$

I am trying to prove that $$R(s, t) ≤ R(s, t-1) + R(s-1, t) $$ for $s,t>2$, where $R(s,t)$ is the Ramsey number of $(s,t)$, and I'd be really grateful for a hint that gets me started.
4
votes
1answer
351 views

Ramsey number for books

Given a triangular book $B_n$ I am trying to prove that $r(B_n,B_n)\le 4n+2$ where $r(B_n,B_n)$ is defined as the least positive number such that any graph $G$ on $r(B_n,B_n)$ vertices either has a ...
5
votes
1answer
276 views

An upper bound for a graph Ramsey number

I am trying to prove the following result, given as an exercise in my book: $r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$. Here $r(G,H)$ denotes the Ramsey number for the ...
6
votes
2answers
235 views

Prove that $r(k,k) + k \leq r(k + 1, k + 1) $

Prove that $r(k,k) + k \leq r(k + 1, k + 1)$, where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes. There are ...
4
votes
1answer
126 views

Edge coloring a graph to find a monochromatic $K_{2,n}$

I am trying to prove or disprove the following statement: Let $n>1$ be a positive integer. Then there exists a graph $G$ of size 4n-1 such that if the edges of $G$ are colored red or blue, no ...