In a school, there are 2021 students, each having exactly $k$ friends. There aren't three students such that all three are friends with each other. What is the maximum possible value of $k$?
Problem
Source: Turkey National Mathematical Olympiad 2021 P6
Tags: combinatorics, combinatorics proposed, graph theory
yofro
07.01.2022 02:03
The answer is $808$. Here is proof that $k\le 808$, see the $4$th post in this thread for a construction. Consider the obvious graph representation. We want to find the maximum $k$ if a triangle-free graph $G$ on $2021$ vertices is $k$-regular. Replace $2021$ with an arbitrary odd number $n$. Lemma: $G$ cannot be bipartite Proof: Suppose otherwise, that $G$ is split into two bipartitions $X$ and $Y$. But $$\sum_{v\in X}d(v)=\sum_{v\in Y}d(v)\implies k|X|=k|Y|\implies |X|=|Y|$$Which is impossible since $n$ is odd.
Suppose there are three neighbors $v_1, v_2, v_3$, where $v_2$ is in between $v_1$ and $v_3$ in $C$. Let $d_1$ be the distance between $v_1$ and $v_2$ and $d_2$ be the distance between $v_2$ and $v_3$. Then the cycle $v\to v_1\to v_2$ has parity $d_1\pmod{2}$, the cycle $v\to v_2\to v_3$ has parity $d_2\pmod{2}$. The cycle $v\to v_3\to v_1$ (around the other side of the cycle, not containing $v_2$) has parity $d_1+d_2+1\pmod{2}$ (because the cycle has odd length). These cannot all be odd, so one of them would be odd. Since the vertices cannot be adjacent because we would then have a triangle, this contradicts the minimality of our chosen odd cycle. You may think that this argues that $v$ cannot just have two neighbors $v_1$ and $v_3$ because we could just ignore $v_2$, but this is not the case because both the cycles $v\to v_1\to v_3$ and $v\to v_3\to v_1$ would not be of smaller length than $C$ (while one could be odd).
. Then $$\sum_{v\in C}d(v)\le 2(n-r)+2r=2n\implies kr\le 2n$$But since $r\ge 5$ (no triangles), $k\le \frac{2n}{5}$. When $n=2021$, we have $k\le 808$.
oolite
10.01.2022 23:26
Would be nice to see a construction with maximum $k$, whatever that limit might be. Here's a construction for $k=688$. Let $R=\{-15,-13,\ldots,13,15\}$, of size $16$. Note that\[ a+b+c\ne 0\pmod{47}\quad\forall a,b,c\in R \]Label each of the $2021$ vertices with a distinct pair of integers $(q,r)$ such that $0\le q\le 42$ and $0\le r\le 46$. Form a graph $G$ by connecting $(q_1,r_1)$ to $(q_2,r_2)$ iff $r_1-r_2\in R$. Clearly, every vertex has degree $43\times\left|R\right|=688$. $G$ is triangle-free. Otherwise, we could find vertices $(q_1,r_1), (q_2,r_2)$ and $(q_3,r_3)$ such that\begin{align*} a&=r_2-r_3\in R\\ b&=r_3-r_1\in R\\ c&=r_1-r_2\in R,\end{align*}and therefore $a+b+c=0\quad\ldots$ contradiction.
mehmetakifyildiz
12.01.2022 02:01
See the attachment for the construction with $k=808$: - circle with the number $r$ represents an independent set of size $r$ - straight lines represent all the possible edges between consecutive bags - dashed line represents all the possible edges minus a perfect matching
Attachments:
