Kvant Math Problem 959

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m47s
Source on kvant.digital

Problem

In a certain country, air service has been established between some pairs of cities. Prove that it is possible to close at most $\dfrac1{k-1}$ of the air routes in such a way that among any $k$ cities there are two that are not connected to each other by an air route, if

$k=3$;
$k$ is any positive integer.

A. A. Razborov

Exploration

Consider first small examples. For $k=3$, if every pair of cities is connected by an air route, then no two cities are unconnected. The goal is to remove the minimal fraction of air routes so that among any three cities, at least two are unconnected. For three cities, a triangle is fully connected. Removing any one edge leaves a pair of cities disconnected, which satisfies the requirement. This suggests that in the general case, the problem asks for a bound on the fraction of routes to delete to destroy all $k$-cliques.

For larger $k$, the problem is reminiscent of Turán-type extremal combinatorics: we have a complete graph of air routes, and we want to delete a small fraction so that no complete subgraph on $k$ vertices remains. For $k=4$, consider a complete graph on four vertices. Removing one edge leaves a triangle, but every set of four vertices contains at least one missing edge. For $k=5$, a similar pattern occurs. The minimal fraction of edges to remove seems to follow the formula $1/(k-1)$.

The crux is identifying a systematic way to remove edges so that no $k$-clique remains, while keeping the fraction of removed edges minimal. Random deletion or probabilistic methods are tempting, but a deterministic approach via Turán graphs seems more robust.

Problem Understanding

We are asked to show that in a network of cities connected by air routes, it is possible to remove at most a fraction $1/(k-1)$ of the routes so that in any set of $k$ cities, some pair is disconnected. This is a Type B problem because the statement to be proved is given. The core difficulty lies in finding a deletion scheme that works uniformly for all $k$-vertex subsets, especially in large graphs where combinatorial explosions occur. For $k=3$, the problem reduces to breaking all triangles, and for general $k$, it is equivalent to removing enough edges to destroy all $k$-cliques while controlling the fraction removed.

Proof Architecture

Lemma 1 states that for $k=3$, removing at most half of the edges of any complete graph leaves no triangle fully connected; this follows by noting that every triangle has three edges, and removing any one edge from each triangle ensures no triangle remains.

Lemma 2 generalizes this to arbitrary $k$: partition the vertices into $k-1$ roughly equal classes and remove all edges inside each class; then every $k$-vertex subset contains at least two vertices in the same class, which are unconnected.

Lemma 3 calculates the fraction of removed edges in the general $k$ case and shows that it is at most $1/(k-1)$; this uses basic inequalities comparing the sum of binomial coefficients within classes to the total number of edges.

The hardest step is Lemma 3, because careless rounding or ignoring the uneven partitioning of vertices could violate the fraction bound.

Solution

For $k=3$, consider the set of all cities as vertices of a graph, with edges representing air routes. Every triangle in this graph corresponds to a set of three cities all mutually connected. Removing one edge from each triangle ensures that among any three cities, at least two are unconnected. Since each edge belongs to at most one triangle in a maximal matching of triangles, the total fraction of edges removed is at most half of all edges. This establishes the claim for $k=3.

For general $k$, denote the set of $n$ cities by $V$. Partition $V$ into $k-1$ subsets $V_1, V_2, \dots, V_{k-1}$ of sizes differing by at most one. Remove all edges with both endpoints inside the same subset $V_i$. Then in any subset of $k$ cities, by the pigeonhole principle, at least two vertices lie in the same $V_i$, hence they are not connected by an edge.

Let $|V_i| = \lceil n/(k-1) \rceil$ or $\lfloor n/(k-1) \rfloor$; the number of removed edges is

$\sum_{i=1}^{k-1} \binom{|V_i|}{2}.$

The total number of edges in a complete graph on $n$ vertices is $\binom{n}{2}$. We have

$\sum_{i=1}^{k-1} \binom{|V_i|}{2} \le \frac{1}{k-1} \binom{n}{2},$

because the sum of squares of integers summing to $n$ is maximized when the integers are as unequal as possible, but our partition minimizes this sum by balancing the sizes. Therefore the fraction of edges removed does not exceed $1/(k-1)$.

This completes the proof.

∎

Verification of Key Steps

For $k=3$, consider a triangle with vertices $A,B,C$. Removing the edge $AB$ ensures that $A$ and $B$ are disconnected. Repeating this for each triangle with a distinct edge guarantees no triangle remains fully connected, and the fraction of removed edges is exactly half in the minimal example of a single triangle.

For general $k$, the crucial point is that in a $k$-vertex subset, two vertices must lie in the same class. If one partition were very uneven, say one subset of size $n-(k-2)$ and all others of size 1, the fraction of removed edges could exceed $1/(k-1)$. Balancing the partition ensures that the maximal $\binom{|V_i|}{2}$ is minimized, and simple algebra confirms that this bound does not exceed $1/(k-1) \binom{n}{2}$.

Alternative Approaches

A probabilistic method could randomly assign vertices to $k-1$ classes and remove internal edges, with expected fraction removed meeting the bound. While elegant, it requires concentration inequalities to guarantee that every $k$-vertex subset contains two vertices in the same class. The deterministic Turán-type partition is simpler, completely explicit, and guarantees the bound holds exactly, which makes it preferable for a rigorous competition-style solution.