0
votes
1answer
80 views

Homework question about Ramsey numbers

Consider a group of nine people. We know that at least one person, say Adam, knows an even number of people and does not know an even number of people. Show that either Adam and two other people all ...
0
votes
1answer
58 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
0
votes
2answers
43 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
74 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
3answers
73 views

Why is this binomial coefficient bounded thus?

Source: Miklos Bona, A Walk Through Combinatorics. $$ \forall k\geq 2,\binom{2k-2}{k-1}\leq4^{k-1}.$$ The RHS is the upper bound of the Ramsey number $R(k,k)$. How can I prove the inequality ...
0
votes
1answer
184 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 ...
7
votes
2answers
136 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
2
votes
1answer
68 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
2
votes
0answers
84 views

Van der Waerden type numbers (for geometric progressions)

Van der Waerden theorem is true also for geometric progressions. Is there anything interesting in van der Waerden type numbers $ W'(r,k) $ derived from this version? ($ W'(r,k) $ is such that if the ...
2
votes
0answers
40 views

How to prove some properties of partitions of finite subsets of N? [duplicate]

Possible Duplicate: Any partition of {1,2,..,9} must contain a 3-Term Arithmetic Progression The problem is as such: Prove that there is not a partition of $N_9 = \{1, 2, 3, 4, 5, 6, 7, ...
12
votes
1answer
317 views

Monochromatic squares in a colored plane

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
3
votes
1answer
2k views

Show that among 20 people there are either four mutual friends or four mutual enemies

Use the fact that among a group of 10 people, where any two people are either friends or enemies, there are either three mutual friends or four mutual enemies, and there are either three mutual ...