What do you mean "the other two" ?

modularmarc, I am not sure either and was waiting for a response in case I was being stupid. I have sent a message to Valentin Vornicu since I have reason to believe he has been involved with the problem in some way.

Assuming it means to exist (at least) three that know each other, an overkill is to use the Caro-Wei theorem. Consider $G$ the $k$-regular graph on $n$ vertices made by the mathematicians. Then $\omega(G) = \alpha(\overline{G}) \geq \sum_{v \in V} \dfrac {1} {\deg_{\overline{G}} v + 1} = \dfrac {n} {(n-1)-k+1} = \dfrac {n} {n-k}$, so it is enough to have $\dfrac {n} {n-k} > 2$, i.e. $k > n/2$. Zarankiewicz theorem should yield the same bound. Counterexamples with $n=4$, $k=2$ and $n=6$, $k=3$ are easy to build, so $\lfloor n/2 \rfloor + 1$ is probably correct. Edited the floor expression.

mavropnevma wrote: Assuming it means to exist (at least) three that know each other, an overkill is to use the Caro-Wei theorem. Consider $G$ the $k$-regular graph on $n$ vertices made by the mathematicians. Then $\omega(G) = \alpha(\overline{G}) \geq \sum_{v \in V} \dfrac {1} {\deg_{\overline{G}} v + 1} = \dfrac {n} {(n-1)-k+1} = \dfrac {n} {n-k}$, so it is enough to have $\dfrac {n} {n-k} > 2$, i.e. $k > n/2$. Zarankiewicz theorem should yield the same bound. Counterexamples with $n=4$, $k=2$ and $n=6$, $k=3$ are easy to build, so $\lceil n/2 \rceil$ is probably correct. I have edited the problem statement, I agree with your idea. However I think the answer to the problem is $\left\lfloor \frac{n}{2} \right\rfloor +1$.

WakeUp wrote: mavropnevma wrote: Assuming it means to exist (at least) three that know each other, an overkill is to use the Caro-Wei theorem. Consider $G$ the $k$-regular graph on $n$ vertices made by the mathematicians. Then $\omega(G) = \alpha(\overline{G}) \geq \sum_{v \in V} \dfrac {1} {\deg_{\overline{G}} v + 1} = \dfrac {n} {(n-1)-k+1} = \dfrac {n} {n-k}$, so it is enough to have $\dfrac {n} {n-k} > 2$, i.e. $k > n/2$. Zarankiewicz theorem should yield the same bound. Counterexamples with $n=4$, $k=2$ and $n=6$, $k=3$ are easy to build, so $\lceil n/2 \rceil$ is probably correct. I have edited the problem statement, I agree with your idea. However I think the answer to the problem is $\left\lfloor \frac{n}{2} \right\rfloor +1$. @WakeUp: $\lceil n/2 \rceil = \left\lfloor \frac{n}{2} \right\rfloor +1$ @mavropneva: Could you post a non-overkill proof? Maybe something along the lines of this would work: Consider a complete graph of $n$ vertices $K_n$. Let each vertex represent a mathematician. For each pair of two points, color the edge connecting them red if the two mathematicians are friends, or blue if the two mathematicians are not friends. (use pigeonhole?)

Right. It needs be $\lfloor n/2 \rfloor + 1$, precisely when $n/2$ is an integer, since we need $k > n/2$. Let's try an elementary solution. Assume $n=2m$ is even; then $k>n/2$ means $k\geq m+1$. If no two of the friends of $A$ know each other, since there are at most $m-1$ other (including $A$), there are not enough for the friends of any of his friends. Assume then $n=2m+1$ is odd; then again $k>n/2$ means $k\geq m+1$. If no two of the friends of $A$ know each other, since there are at most $m$ other (including $A$), there are not enough for the friends of any of his friends. This even offers a counterexample for $n=2m$ and $k=m$. Take $A$, the $m$ he knows, and have each of them know all the other $m-1$. A simple verification shows everybody knows $m$ other, while no three know each other (simpler - this is a complete bipartite graph on two classes of $m$ vertices each). There can be no such counterexample for $n=2m+1$ and $k=m$ if $m$ is odd, since no such regular graph might exist (it has an odd number of odd degree vertices). If $m = 2\ell$ is even, the counterexample may be more difficult to build, or even not exist! Indeed, a pentagon is a model for $n=5$, $k=2$, but there exists no model for $n=9$, $k=4$.

WakeUp wrote: At a conference there are $n$ mathematicians. Each of them knows exactly $k$ fellow mathematicians. Find the smallest value of $k$ such that there are at least three mathematicians that all know each other.

So, can someone use pigeonhole ?

mavropnevma wrote: If $m = 2\ell$ is even, the counterexample may be more difficult to build, or even not exist! Indeed, a pentagon is a model for $n=5$, $k=2$, but there exists no model for $n=9$, $k=4$. Indeed, a counter example won't exist if $2\ell >2$. Suppose it did then take vertex $v_0$ which is adjacent to $2\ell$ vertices $S_1=\{v_1,...,v_{2\ell}\}$. Each of those vertices is adjacent to $2\ell-1$ vertices from $S_2=\{v_{2\ell+1},...,v_{4\ell}\}$. If $\ell>1$ then any two vertices in $S_2$ are adjacent to a common vertex in $S_1$, but there must be some edges among vertices in $S_2$ because they have to have degree $2\ell$, so we have a triangle.

WakeUp wrote: The exact wording of the problem was: At a conference there are $n$ mathematicians. Each of them knows exactly $k$ participants. Find the smallest value of $k$ such that there are at least three mathematicians that are acquainted with the other two. There is just a small omission (the word "each", added in green) that makes everything clear: ... such that there are at least three mathematicians that are acquainted each with the other two ...