Let $n\ge 3$ be a positive integer. There are $n^3$ users on a social media network called Everyone Likes Meeting Online (ELMO), and some pairs of these users are buddies. A set of at least three ELMO users forms an ELMOClub if and only if all pairs of members of the set are buddies. It is known that among every $n$ users, some three form an ELMOclub. Prove that there is an ELMOclub with five members. Luke Robitaille
Problem
Source: ELMO 2022 P5
Tags: combinatorics, graph theory, ELMO 2022
24.06.2022 06:25
Given a simple graph with $n^3$ vertices. We know among every $n$ users, there is a $K_3$. Prove the graph contains a $K_5$. The bound is actually quite weak. In fact, it should hold for $\frac{n^3}{6}(1+o(1))$ vertices, but I don't prove this claim. Lemma: Let $G=(V,E)$ where $|V|\ge n^2$ and among any $n$ vertices, there exists a $K_3$. Then there is a $K_4$ in $G$. Proof: We induct on $n$. Fix a vertex $v$, and let $N(v)$ be the set of vertices adjacent to $v$. If $|N(v)|\ge n$, then there exists a $K_3$ in $N(v)$. Merge this $K_3$ with $v$ gives the desired $K_4$. Otherwise, there are at least $n^2-n$ vertices outside $v$ and $N(v)$. Pick $n-1$ of these vertices and $v$, and the $K_3$ must lie within the $n-1$ vertices. Therefore, the graph $G\backslash v\sqcup N(v)$ has $(n-1)n$ vertices, and there is a $K_3$ among any $n-1$ vertices. Now we induct on $n$ to solve the problem. If $|N(v)|\ge n^2$, then there exists a $K_4$ in $N(v)$. Merge this $K_4$ with $v$ gives the desired $K_5$. Otherwise, there are at least $n^3-n^2$ vertices outside $v$ and $N(v)$. Pick $n-1$ of these vertices and $v$, and the $K_3$ must lie within the $n-1$ vertices. Therefore, the graph $G\backslash v\sqcup N(v)$ has $(n-1)n^2$ vertices, and there is a $K_3$ among any $n-1$ vertices. This completes the induction.
24.06.2022 06:44
Here is an approach that doesn't prove the existence of $K_4$ in the middle. Use induction on $n$, where the base case $n=3$ is trivial. If any $(n-1)$-element set has a 3-clique, then we obviously can induct down. Otherwise, consider a set $S$ of $n-1$ vertices that doesn't contain a 3-clique. Consider a vertex $v\notin S$ and look at $S\cup\{v\}$. We see that $v$ must be adjacent to at least two adjacent vertices in $S$. There are $n^3-n+1$ such vertices but $\tfrac{(n-1)(n-2)}{2}$ pairs. Thus, by pigeonhole, at least $n$ vertices in $G\setminus S$ are adjacent to the same two adjacent vertices $x,y\in S$. These $n$ vertices must form a 3-clique, so combining that 3-clique with $x,y$ gives a 5-clique.
24.06.2022 07:00
Well basically induction and PHP, quite nice. I will instead prove the contrapositive statement: If there isn’t a $K_5$ in $G$, then there are $n$ vertices which don’t form a triangle. I will induct on $n$, the base case is trivial. Assume it’s true for $n$ and consider a graph $G$ with $(n + 1)^3$ vertices which doesn’t contain a $K_5$. Suppose FTSoC that any set of $n + 1$ vertices contains a triangle (*). Take a random subgraph with $n^3$ vertices (which again doesn’t contain a $K_5$) and apply the Induction Hypothesis to it. We obtain that we have $n$ vertices in $G$ which don’t form a triangle, but adding any other vertex to them makes a triangle; let the induced subgraph of those $n$ vertices be $M$ . There are $n^3 + 3n^2 + 2n + 1$ other vertices, and to each of them we will assign the edge from $M$ , with which it makes a triangle. If there are $e \leq \frac {n(n-1)}{2}$ edges in $M$ , then due to PHP, some edge $r$ has been assigned to at least $(n^3+3n^2+2n+1)/e>n+1$ vertices due to the mentioned above bound of $e$. Take those $n + 1$ vertices and apply the hypothesis (*) to obtain that there is a triangle in their induced subgraph. Note that this triangle has all its vertices connected to both ends of $r$ due to the choice of $r$, so this is a $K_5$, contradiction.
24.06.2022 07:17
Even if we take an arbitrary vertex $n^2 $, it is not difficult to prove that $ K_4 $ is found in it. Similarly, $ K_5 $ is found between $ n ^ 3 $ vertex.
24.06.2022 07:19
Same as Mark Bcc's. https://drive.google.com/file/d/1BpTMfyai7RfxOHPjEHXa7hSO0whxqWKS/view?usp=sharing
24.06.2022 07:45
CLAIM 1::Among , every $n^2$ users , there is an ELMOclub with $4$ members Assume not , Let we have $n^2$ users such that the graph defined by then has no $K_4$ subgraph.Then for any vertex $v$ , $d(v)<n$ , otherwise we'll get a K4.Let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^2-n$ vertices out of these $n^2$ such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^2-2n$ vertices such that none of them are adjacent to $v_2$.Since $n^2 =n \times n$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .This contradicts the question statement.Thus CLAIM proved. CLAIM 2::There is an ELMOclub with $5$ members Assume not .Then , by similar arguments , $d(v)<n^2$.Now , let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^3-n62$ vertices such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^3-2n^2$ vertices such that none of them are adjacent to $v_2$.Since $n^3 =n \times n^2$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .Again , contra.hence proved.
24.06.2022 08:51
Rephrase to graph theory, there are $n^3$ vertices, among any $n$ of them, there's a triangle and we need to show that there is a $K_5$. Claim: With the same condition, among any $n^2$ vertices, there is a $K_4$ Consider only the subgraph containing these vertices. If some vertex, say $v$ has degree $\ge n$, then among those there will be a triangle and so there is a $K_4$. If not, then there exist at least $n^2 - n > (n-1)^2$ vertices not connected to $v$. In those vertices, there are $(n-1)^2$ vertices and among any $n-1$ of them, there is a triangle (to show this, pick those $n-1$ as well as vertex $v$ but since $v$ isnt connected to any of them, the triangle will be among those $n-1$) so we may induct down and since the base case of $n = 3$ is true (in this case every three vertices form a triangle so its a clique), the claim follows. Now for the problem, we repeat the exact same argument. If there is a vertex, say $v$ of degree at least $n^2$, then by the claim we can find a $K_4$ in it and hence a $K_5$ including $v$. If not, then there are $n^3 - n^2 > (n-1)^3$ vertices at least not connected to $v$. And since among any $n-1$ of them, there must be a triangle (by the same reasoning as above), we can induct down and since $n = 3$ is true, the problem follows.
24.06.2022 12:23
Assume the contrary, and consider the obvious graph interpretation. Then, there is no $5$-cliques, and for every $n$ vertices three of them forms a clique. Take the largest set $S$ of $k$ vertices containing no $3$-cliques. Then $k < n$. For two adjacent vertices $a, b$, we say that a vertex $v$ is a $\textit{common buddy}$ of $a,b$ if both are adjacent to $v$. We know that every vertex $v \not\in S$ must be a common buddy of some pair of adjacent vertices $a, b \in S$, otherwise adding $v$ into $S$ creates a larger set still with no $3$-cliques. On the other hand, for any pair of adjacent $a,b \in S$, if it has more than $k$ common buddies, then three of them, say $v_1, v_2, v_3$, must form a $3$-clique. But then $a, b, v_1, v_2, v_3$ are all pairwise adjacent, a contradiction. Hence, $a, b$ must have at most $k$ common buddies. But these two imply the number of vertices not in $S$ is at most $k\binom{k}{2} < n\binom{n}{2} = \frac{n^3 - n^2}{2}$, and we know there are exactly $n^3 - k > n^3 - n$ vertices. This easily gives a contradiction.
24.06.2022 16:10
Here is a proof that uses the fact that $3+(3-1)=5$. View the problem as a graph in the obvious way. Let $m$ be the largest positive integer such that there exists a set of $m$ users without a triangle, so $m<n$. Let $S$ be such a set with $m$ vertices. By the maximality of $m$, adding any vertex to $S$ forms a triangle, so the following statement is true: For any $v \not \in S$, there exist $u,w \in S$ such that $u,v,w$ form a triangle. Given this, we can pair all $n^3-m$ vertices not in $S$ with an edge in $S$ (corresponding to $\overline{uw}$). By expectation, some edge $e=\overline{xy}$ in $S$ has at least $$\frac{n^3-m}{\binom{m}{2}}>\frac{n^3-m}{m^2/2}>\frac{n^3-n}{n^2/2}=2\left(n-\frac{1}{n}\right)>n$$vertices paired with it (here we can see that the bound is quite loose, and we can even make it looser with Turan's to replace $m^2/2$ with $m^2/4$). Thus, consider $n$ of the vertices paired with $e$. There exists some triangle with vertices $\{a,b,c\}$ within these $n$ vertices, whence $\{a,b,c,x,y\}$ clearly form a $K_5$. $\blacksquare$
07.07.2022 20:12
The key lemma is a weaker version of St. Petersburg 2011.
03.09.2022 20:26
I hope this works. Let $G$ be the simple graph where the vertices correspond two ELMOusers and the edges to pairs of ELMObuddies. We induct on $n.$ For $n=3,$ the conditions becomes: every $3$ vertices forms a $K_3;$ therefore the entire graph is a clique and we are done. Now assume the result holds for $n-1 \ge 3.$ If among any $n-1$ vertices there exist a $K_3,$ then we can induct down. Otherwise, consider a set $S$ of $n-1$ vertices such that the induced graph $G'$ on $S$ is triangle-free. Now let $i$ be any other vertex that is not in $S;$ then by hypothesis the induced graph on $S\cup \{i\}$ must contain a $K_3$ and it follows that there must be an edge on $G'$ such that $i$ connects to the two endpoints of these edge (beacause we are assuming $G'$ has not a triangle.) From the last paragraph, it follows that all the $n^3 - (n-1)$ vertices that are not in $S$ must connect to some edge in $G'$ (i.e. must connect to the two endpoints of that edge.) Therefore, it suffies to show that there exists three vertices not in $S$ forming a $K_3$ and such that they connect to the same edge in $G'.$ Indeed, by Turan's Theorem $G'$ has at most ${(n-1)^2}{/}{4}$ edges and hence one edge must connect to $n$ different vertices (this follows from Pigeonhole Principle since ${{(n-1)}^3}{/}{4} < n^3 - (n-1)$) hence by problems condition there must be a $K_3$ among these $n$ vertices. So done.
25.12.2022 00:49
Here's a brute force solution with extremal arguments. Translate the problem to graphs. Out of all possible sets of $n$ vertices consider the one with the least number of triangles. Call that $S$. We know $S$ contains for sure a triangle. Now take the vertice in $S$ present in the biggest number of triangles in $S$. Let that vertice be $P$ and that number be $k$. Obviously, $k\ge 1$ . Remove $P$ from $S$. Now adding any new point from the rest $n^3-n$ into $S/P$ should yield at least $k$ new triangles. Otherwise, we would get a smaller total number of triangles in the new $S$. Thus, at least $(n^3-n)\cdot k$ triangles occur with exactly one side in $S/P$ and a vertice outside of $S$. Hence, since we only have $\binom{n-1}{2}$ sides, one side is present in at least $\dfrac{(n^3-n)\cdot k}{\binom{n-1}{2}}=\dfrac{2n(n+1)k}{n-2} > n$ triangles. Let that side be $ab$ and the corresponding points of the $n$ triangles be $Q={P_{1},..,P_{n}}$. By the condition we can find a triangle in $Q$. Let that be $P_{i1}P_{i2}P_{i3}$. Then, $a,b,P_{i1},P_{i2},P_{i3}$ is the answer.
25.12.2022 01:31
Let $G$ be the social network and $G'$ be a induced subgraph of maximal size without a triangle. Obviously $|G'| < n$. Note that for every vertex $v \in G \backslash G'$, it forms a triangle with some other two vertices $s, t \in G'$, else adding $v$ to $G'$ preserves the no triangle property and thus violates maximality. Each vertex in $G\backslash G'$ with size $n^3 - |G'|$ can be assigned one of $\tbinom{G'}{2}$ edges to form a triangle with. Therefore, there is some edge which forms a triangle with at least\[\left\lceil \frac{n^3 - |G'|}{\binom{G'}{2}} \right\rceil \geq \left \lceil\frac{n^3 - n}{\binom{n}{2}}\right\rceil \geq 2n+2\]vertices in $G \backslash G'$. However, $2n + 2 > n > |G'|$ so for some edge $e \in G'$, we have a set with size $> |G'|$ that all form triangles with $e$. Yet, since this set has greater size than $G'$, we know that this set itself contains a triangle $a, b, c$, so simply choosing the five vertices $a, b, c$ and the endpoints of $e$ yields a $K_5$, done.
25.12.2022 06:24
Stumper-scanning supplied subsequent solution. Sage suggestion: specific-seeming statement? Seek SUPER statements! SUPER Statement. Select $S \ge s \ge 2$, $\mathbf s \ge 1$, stick-&-stone sketch: $S^{\mathbf s}$ stones strong. Suppose selecting $S$ stones serves $s$ stones sustaining sticks supremely. Suddenly, see: $s + \mathbf s - 1$ stones sustaining sticks supremely! Solution. Scorn $\mathbf s = 1$: shallow statement! Stipulate $\mathbf s \ge 2$. Seek stone $\$$ sustaining $S^{\mathbf s - 1}$ supporting stones. Solution splits: Suppose seeking $\$$ successful. Simulate SUPER statement (substituting $\mathbf s - 1$), supplying $S^{\mathbf s - 1}$ stones supporting $\$$: secure $s + \mathbf s - 2$ stones sustaining sticks supremely. Suggest $\$$: sum $s + \mathbf s - 1$ stones, sustaining sticks supremely. Suppose stone $\$$ solely superstition: stones support sub-$S^{\mathbf s - 1}$ sticks. Select stones successively, shunning shared sticks. Simple statistics: sometime, $\left\lceil \frac{S^{\mathbf s}}{1 + (S^{\mathbf s - 1} - 1)} \right\rceil = S$ stones selected. SUPER statement suggests $S$ stones sustain some sticks: shoot! (Swear screening sucks...) Sacrificing statement strength, specifying $s = \mathbf s = 3$, supplies sought solution.
25.12.2022 07:38
Let's give a big hand to CantonMathGuy on the prolific vocabulary of words starting with s! *Clap Clap Clap* (and the new solution) Here is the argument in a more readable language. Tip: When the statement is specific, seek generalizations and strengthen it. Strengthened argument: Let $n\ge t\ge 2, s\ge 1$. In a graph with $n^s$ vertices, if among any $n$ vertices, there is a $K_t$, then the graph with $n^s$ vertices contain a $K_{s+t-1}$ We induct on $s$. The base case, $s=1$, is true by definition. Henceforth assume $s\ge 2$. Case 1: There exists a vertex adjacent to at least $n^{s-1}$ neighbours. Among the $n^{s-1}$ neighbours, there is a $K_{s+t-2}$ by inductive hypothesis among the neighbours. Adding the vertex yields the $K_{s+t-1}$ Case 2: No vertex is adjacent to at least $n^{s-1}$ neighbours. I claim there exists an anticlique of size $n$. Take a random permutation of the vertices $v_1, \cdots, v_M$, and generate the anticlique this way: start a running counter $j=1$. Let $C$ be our current vertex set. If no vertex in $C$ is adjacent to $v_j$, then insert $v_j$ to $C$. Increment $j$ by 1. Let $1_v$ be an indicator for whether a vertex is in $C$. If it comes before its $\deg(v)$ neighbours, then it is in $C$, so $\mathbb{E}[1_v] \ge \frac{1}{\deg v+1}$. Then $\mathbb{E}[C] = \sum_v \mathbb{E}[1_v] \ge \sum_v \frac{1}{\deg(v)+1} \ge \frac{n^s}{n^{s-1}}=n$ Thus there exists an anticlique of size $\lceil \mathbb{E}[C] \rceil = n$. Contradiction!
18.02.2023 07:14
SPHS1234 wrote: CLAIM 1::Among , every $n^2$ users , there is an ELMOclub with $4$ members Assume not , Let we have $n^2$ users such that the graph defined by then has no $K_4$ subgraph.Then for any vertex $v$ , $d(v)<n$ , otherwise we'll get a K4.Let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^2-n$ vertices out of these $n^2$ such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^2-2n$ vertices such that none of them are adjacent to $v_2$.Since $n^2 =n \times n$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .This contradicts the question statement.Thus CLAIM proved. CLAIM 2::There is an ELMOclub with $5$ members Assume not .Then , by similar arguments , $d(v)<n^2$.Now , let $v_1$ be a vertex .Then there is a set $A_1$ of atleast $n^3-n62$ vertices such that none of then are adjacent to $v_1$.Let $v_2 \in A_1$ .Then there is a subset $A_2$ of $A_1$ of atleast $n^3-2n^2$ vertices such that none of them are adjacent to $v_2$.Since $n^3 =n \times n^2$ , in this way we get a set of $n$ vertices $\{v_1,v_2 ,\cdots v_n\}$ such that none of them are adjacent .Again , contra.hence proved. It can be strongly improved as the number of vertexes only connected to one point in the subset is limited!
06.01.2024 11:00
Consider the obvious graph theoretic interpretation. We use induction on $n$ , with the base case $n=3$ being trivial. Assume that the statement is true for $n-1$. If all sets of $n-1$ vertices have a triangle in it we are done by the induction hypothesis. Assume henceforth that this is not true and let $\mathcal{S}$ be a set of $n-1$ vertices that don't contain a triangle. Consider a vertex $v \notin \mathcal{S}$. Notice that $v$ must be adjacent to two adjacent vertices in $\mathcal{S}$. There are $n^3-n+1$ vertices not in $\mathcal{S}$ and at most $\frac{(n-1)(n-2)}{2}$ possible pairs of adjacent vertices in $\mathcal{S}$ so, it follows by the pigeonhole principle that there is a set $T$ of $\frac{2(n^3-n+1)}{(n-1)(n-2)} \geq n$ vertices such that each vertex is adjacent to the same pair of adjacent vertices $(v_1, v_2)$ in $\mathcal{S}$. Recall that since $|T| \geq n$ there exists a triangle in $T$. Adding $v_1, v_2$ to this triangle obviously forms a 5-clique which is what we wanted to prove. $\blacksquare$
11.01.2025 17:59
Probably same as the ones above, We use the induction on $n$ . The small cases we can verify by casework, For higher cases assume the contrary , Consider the obvious graph theory reprsenation. Pick any $A_{1},....,A_{(n-1)^3}$ vertices first , clearly there should exist a way to pick $n-1$ vertices from this such that if we pair them with $A_{(n-1)^3+1}$ then all the triangles in those $n$ vertices contain $A_{(n-1)^3+1}$ . Pick those vertices say $V_{1},....,V_{n-1}$, clearly for any vertex $V_i$ outside this there exists two $V_{j},V_{k}$ in those $n-1$ ones connected by a edge such that $V_{i},V_{j},V_{k}$ form a triangle. There are a total of $n^3-n+1$ ways to choose $V_i$ and a max of $\binom{n-1}{2}$ ways to pick $V_{j},V_{k}$ , So one choice of $V_{j},V_{k}$ repeats atleast $2\frac{n^3-n+1}{(n-1)(n)}$ times thats $ \geq n$ for all large $n$ Pick those $n$ ones say $B_{1},B_{2},....,B_{n}$ say the common pair for them is $V_{j},V_{k}$ Pick the triangle formed amongst $B$i's and pick $V_{j}$ and $V_{k}$ and u have a 5 clique