A computer network is formed by connecting $2004$ computers by cables. A set $S$ of these computers is said to be independent if no pair of computers of $S$ is connected by a cable. Suppose that the number of cables used is the minimum number possible such that the size of any independent set is at most $50$. Let $c(L)$ be the number of cables connected to computer $L$. Show that for any distinct computers $A$ and $B$, $c(A)=c(B)$ if they are connected by a cable and $|c(A)-c(B)| \le 1$ otherwise. Also, find the number of cables used in the network.
Problem
Source: MOP 2005 Homework - Black Group #13
Tags: combinatorics unsolved, combinatorics
24.05.2014 07:12
Let us suppose $N$ is a network of 2004 computers, not containing Independent systems of size 51 or more which uses the minimum amount of cables to have no independent sets of size greater than 50. We shall prove there are no 3 computers $x,y,z$ such that $x$ is not connected $y$ but z is connected to both $x$ and $y$. We do this by contradiction. Suppose $x$ is not connected to $y$ but $z$ is connected to both $x$ and $y$. Case 1 $(c(z)> c(x) $ or $c(z)> c(y))$. We do the case when $c(z)> c(x)$, but the other case is almost the same. Remove all cables computer $z$ has (except the link with $c$) and then connect computer and then connect computer $z$ to all the computers $x$ is connected to. doing this we remove c(z)-1 cables and then add c(x)-1 cables. Notice this new network has less cables than $N$ and won't have an Independent system of size 51 or greater, since such a system can't contain both $z$ and $x$. A contradiction. case 2 $(c(z)\leq c(x)$ and $c(z)<\leqq(y))$. remove all connections $x$ and $y$ have (removing $c(x)+c(y)$ cables). Then connect $x$ and $y$ to all the connections $z$ has (adding $2(c(z)-2$) vertices, since z is no longer connected to $x$ and $y$) Then connect $x$ to $y$, $y$ to $z$ and $x$ to $z$ adding 4 cables. At the end you added 2c(z)-1 cables and removed c(x)+c(y) cables. So this new network has less cables than $N$ and does not have an independent set of size 51 or more (again, because an independent set can only contain 1 of x,y,z). A contradiction. This means that if we have that $x$ is connected to $z$ and that $z$ is connected to $y$ then $x$ must be connected to $y$ then $x$ is connected to $z$.(transitivity) we already know if $x$ is connected to $y$ then $y$ is connected to $x$. And we shall say $x$ is connected to $x$ making the relation "connected to" an equivalence relation. This means the 2014 vertices are divided into complete partitions. So the network is made up of separated clusters of computers (where all the computers in a cluster are pairwise connected). Clearly the network can have at most $50$ clusters since an independent set can contain at most one computer from each cluster. We shall prove it has exactly $50$ clusters. Assume the minimum amount of cables is achieved with less than $50$ clusters. Then take one of those cluster and remove all the cables from a computer. This computer will form a new cluster. This new network has less cables, 50 or less clusters and no independent set of size 51 or more. A contradiction. Now we shall prove the cluster have sizes of only 2 sizes, and these sizes have difference 1. Suppose there are two clusters with sizes $n$ and $n+k$ with $k\geq2$. Then remove all the cables from one of the computers of the big set (removing $n+k-1$ cables) and connect hat computer to all of the cables of the small cluster (adding n cables). So now we have $k-1$ cables less than before. Since $k\geq2$ we have strictly less cables than before and the same number of clusters (and therefore no independent set of size 51 or more). A contradiction. If two computers $A$ and $B$ are connected then they are in the same cluster and therefore $c(A)=c(B)$. If they are not connected they are in different clusters. we have $c(A)=c(B)$ if they are in same size clusters and $c(A)=c(B)\pm 1$ if they are in different size clusters, as required. So we have $2014$ computers, in $50$ clusters, and their sizes differ by 1. Then there are $46$ clusters of size $40$ and $4$ of size $41$. Since a cluster of size $k$ has exactly one cable per pair of computers in each cluster we conclude a cluster of size $k$ has $\binom{k}{2}=\frac{k\cdot k-1}{2}$. Therefore the network has $46\cdot 780+4\cdot 820=39160$