A communications network consisting of some terminals is called a $3$-connector if among any three terminals, some two of them can directly communicate with each other. A communications network contains a windmill with $n$ blades if there exist $n$ pairs of terminals $\{x_{1},y_{1}\},\{x_{2},y_{2}\},\ldots,\{x_{n},y_{n}\}$ such that each $x_{i}$ can directly communicate with the corresponding $y_{i}$ and there is a hub terminal that can directly communicate with each of the $2n$ terminals $x_{1}, y_{1},\ldots,x_{n}, y_{n}$ . Determine the minimum value of $f (n)$, in terms of $n$, such that a $3$ -connector with $f (n)$ terminals always contains a windmill with $n$ blades.
Problem
Source: USA TST 2006, Problem 1
Tags: graph theory, combinatorics unsolved, combinatorics
10.09.2007 19:20
Let the communication network be a graph. Let $ n=1$. Because a cycle of length $ 5$ is a 3-connector, but doesn't contain a triangle, $ f(n)>5$. We show that $ f(1)=6$. Take a graph with $ 6$ vertices. Take a vertex $ A$. It is clear that there either exist at least $ 3$ neighbours of $ A$, or at least $ 3$ nodes not being joined to $ A$. In the first case, some two of these neighbours have to be joined by an edge, forming a triangle together with $ A$. In the second case, the set comprising $ A$ and any two of them can have at most one edge - the one between the two of them. So all three non-neighbours of $ A$ then form a triangle. For $ n>1$ we show that $ f(n)=4n+1$. Firstly we show that $ f(n)>4n$. Let $ K_{m}$ denote the complete graph with $ m$ vertices. Then a graph consisting of two disjoint not connected $ K_{2n}$'s obviously is a 3-connector and since it hasn't a connected subgraph with more than $ 2n$ vertices, while a windmill is a connected graph and has $ 2n+1$ vertices; we have $ f(n)>4n$. Now take a $ 3$-connector with $ 4n+1$ vertices. Take a vertex $ A$. Let $ V_{A}$ the set of its neighbours and $ NV_{A}$ the set of nodes not connected to $ A$. Take $ X,Y\in NV_{A}$. Because neither $ AX$ nor $ AY$ exists, $ XY$ must exist. $ X,Y$ were arbitrarily chosen, thus $ NV_{A}$ is actually a complete graph. If $ |NV_{A}|\ge2n+1$, then $ NV_{A}$ obviously contains a windmill with $ n$ blades and we are done. Suppose $ |NV_{A}|\le2n$. Then $ |V_{A}|\ge2n$. Take nodes $ V_{2n-2}, V_{2n-1},V_{2n}$. Some two of them are connected by edge. By an eventual rearrangement of the indices, we can suppose that there is an edge between $ V_{2n-1}$ and $ V_{2n}$. We are left with $ 2n-2$ neighbours of $ A$. Repeat the process. If $ |V_{A}|>2n$ then after 'creating' $ n-1$ edges we'll be left with some 3 vertices $ V_{0}, V_{1},V_{2}$. Some two of them are connected by an edge, say $ V_{1}$ and $ V_{2}$. We obtained a windmill with central node $ A$ and blades $ \{V_{1},V_{2}\},$...$ ,\{V_{2n-1},V_{2n}\}$. Done. We're left with the case $ |V_{A}|=2n$ and thus $ |NV_{A}|=2n$. As in the previous case we build $ n-1$ edges: $ V_{2n-1}V_{2n}$, ... ,$ V_{3}V_{4}$. We are left with $ V_{1}$ and $ V_{2}$. If they're connected then we have a windmill. Suppose they're not. Remember that $ NV_{A}$ is a complete graph with $ 2n$ vertices. Now take the $ 2n$ sets $ X_{i}=\{V_{1},V_{2},NV_{i}\}$. Clearly one (or both) of the edges $ V_{1}NV_{i}$ and $ V_{2}NV_{i}$ must exist. Thus, WLOG, $ V_{1}$ has $ n\ge2$ neighbours in the set $ NV_{A}$. Let two of them be $ NV_{1}$ and $ NV_{2}$. Then we have a windmill centered at $ NV_{1}$ with blades: $ \{V_{1},NV_{2}\}$ and other $ n-1$: $ \{NV_{3},NV_{4}\},\ldots\{NV_{2n-1},NV_{2n}\}$. It's also clear why the case $ n=1$ has been treated separately.
19.04.2020 09:46
edit: this bad Consider the complement of the graph. It is triangle free and hence can be split into a bipartite graph with no edges in group $A$ and $B$ for some sets $A$ and $B$ whose union is the entire graph. Now, we claim the answer is $4n+1$. In a graph with $4n+1$ vertices, either $A$ or $B$ has size at least $2n+1$, and then the entire set $A$ or entire set $B$ can be taken as a windmill. In a graph with $k \leq 4n$ vertices, take $A$ and $B$ as complete graphs with vertices split as evenly as possible.
11.07.2022 01:11
We claim that the minima are $6$ and $4x+1$ when $x=1$ and $x\ge 2$, respectively. $~$ Let's take care of the case $x=1$ first. If there are $5$ terminals, then a simple $C_5$ would be a $3$-connector and would have no windmill with $1$ blade, otherwise known as a triangle. For $k\le 5$ we can delete terminals, and the network stays $3$-connector and clearly no triangle arise. Now, assume there are at least $6$ terminals. Then, $R(3,3)=6$ along with every three points having at least one edge implies that there is a triangle. $~$ Now, suppose $x>1$ and there were $4n$ terminals. Then, simply make two $K_{2n}$s. As before, for less than $4n$ terminals just delete terminals from the original $4n$ terminal construction. If there were $4n+1$ terminals, pick any terminal $T$. There must either be $2n+1$ terminals such that none can communicate with $T$, or $2n$ such that all can communicate with $T.$ $~$ Suppose it is that $2n+1$ terminals cannot communicate with $T$ then the $2n+1$ terminals form a $K_{2n+1}$ which one can derive an $n$-windmill from. $~$ Suppose it is that at least $2n$ terminals can communicate with $T.$ Then, if there exists a matching of size $n$ among those terminals, we are done. Consider any three terminals, two of them must be able to communicate. Disregard these and apply the same with the remaining until we have created $n-1$ pairs of distinct terminals, where the two terminals in each pair can communicate. $~$ If we are left with at least $3$ terminals, we are done, so suppose we are left with $2$ terminals, say, $A,B$. Note that the terminals that cannot communicate with $T$ forms a $K_{2n}$, and for each terminal which cannot communicate with $T$, it must be able to communicate with $A$ or $B.$ By pigeonhole, one of $A$ or $B$ has at least two neighbors in the terminals that cannot communicate with $T.$ From here we derive an $n$-windmill so we're done.