I’ve recently got stuck on a theorem that seems to be true, but I am not sure if I am able to prove it:
$\large\forall_{x\in\mathbb{P}_k(\mathbb{N})}\exists_{\left\{ y_1,y_2\right\}\subset x \land y_1 \neq y_2}\; \varphi(y_1,y_2) \rightarrow \exists_{x\in \mathbb{P}_k(\mathbb{N})}\forall_{\left\{y_1,y_2\right\} \subset x \land y_1 \neq y_2}\;\varphi(y_1,y_2)$
Where $\varphi$ is any symmetric predicate, i.e. $\varphi(y_1,y_2) \iff \varphi(y_2,y_1)$, and $\mathbb{P}_k(\mathbb{X})$ is the set of all subsets of $\mathbb{X}$ of size $k$.
In simple words: for any symmetric relation on $\mathbb{N}$, if every subset of $\mathbb{N}$ of size k contains at least one pair of related elements, then in some subset of size k all pairs of elements are related.
This statement is true for $k = 2$ and for $k = 3$ and while $k = 2$ is easy, $k = 3$ was proved by me using graphs (already a bit harder). I believe the proper method for such a theorem would be a proof by induction, however I can’t make the inductive step.
Any thoughts? I really appreciate any help or hint. I also believe this to be quite an interesting theorem.
EDIT:
My proof was like this:
I proved it by deducing without loss of generality how the graph of these relations would behave. I used for this 4 pairs of vertices (each pair having an edge between them, no other edges at the beginning). These edges are given, if by any deductive reasoning we obtain a triangle, then the theorem is proved. Each step of the proof consists of selecting 3 vertices that aren’t connected by any edge and choosing 2 of them and connecting them (in case you can’t do it without the loss of generality, you have to follow all possible routes). At each step you avoid at all cost creating a triangle. I was eventually forced to connect two vertices and by it created a triangle. Should I present the whole proof here? If so do you recommend any tool for drawing graphs and posting it here?
Proof: Ramsey’s theorem may be easily used to prove this statement. Solved.
The premise of your theorem is stronger than you realise, so that your conjecture can be proven as a corollary of a stronger theorem, which I state in graph-theoretical terms:
It would be helpful to flesh out your statement that it follows from Ramsey’s Theorem (of which the above is little more than a logical rearrangement) to explain how.
The proof below of the above reformulation is more or less in the spirit of the proof of Ramsey’s theorem (as given in Wikipedia), but somewhat clumsier, due perhaps to the less symmetrical formulation.
A little terminology
Let us write
A stronger theorem
We assert that $$ \exists f : \mathbb N^2 \to \mathbb N : |G.V| > f(k,r) \wedge C(G,k,2) \Rightarrow C(G,r) $$
Proof from first principles
We proceed by induction on $k$ and, within $k$, on $r$. For $ k = 1 $, the theorem is vacuously true, as $ |V| > 2 \Rightarrow \neg C(G,1,2) $.
Now supposing the theorem proven for $k$ (in combination with all values of $r$), we prove it for $ k+1 $; we therefore assume $ C(G,k+1,2) $ and that $f(x,y)$ is defined for $ x \leqslant k $.
For $ r=2 $ trivially $ |V| > k \wedge C(G,k,2) \Rightarrow C(G,2) $.
Consider a vertex $x$ and its non-neighbours $ x \overline G $, among which we observe $ C(x \overline G, k, 2) $, whence, by induction: $$ |x \overline G | > f(k,r) \Rightarrow C(x \overline G ,r) $$
Hence, in a counterexample to $ C(G,r+1) $, we have: $$ \forall x \in V : | x \overline G | < f(k,r+1) $$
By the induction on $r$ we have an $r$-clique $R$; if a vertex in $ G-R $ is joined to all of $R$ we have a $(k+1)$-clique. Otherwise every point in $ G-R $ is not joined to at least one member of $R$, which limits the size of the complement: $$ |G-R| = |G| - r < r f(k,r+1) $$ i.e. $$ |G| < r ( 1 + f(k,r+1) ) $$
Hence in this case we may take $ f(k,r) = r ( 1 + f(k,r+1) ) $ and the theorem holds by induction for all $k$ and $r$.
Q.E.D
Proof using Ramsey’s theorem
Ramsey’s Theorem tells us that for $|G| > R(r,k)$, $G$ contains an $r$-clique or independent set of size $k$, or equivalently $ C(G,r) \lor C(\overline G, k) $ but the hypothesis $C(G, k, 2)$ is eqivalent to $ \neg C(\overline G, k) $ so that the theorem I formulated above is a logical rearrangement of Ramsey’s theorem.