Kvant Math Problem 670

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m14s
Source on kvant.digital

Problem

1. Several points are given, with some pairs connected by lines (the points in such pairs are called neighbors). Each point has an odd number of neighbors. Initially, all points are colored in two colors — red and blue. Then, every minute, the points are simultaneously recolored according to the following rule: each point whose majority of neighbors have a color different from its own changes its color; otherwise, it retains its color.

Prove that there will come a moment starting from which some points will no longer change color, while others will change color every minute. 2. Does this statement remain true if it is not assumed that each point has an odd number of neighbors?

O. Kozlov

Exploration

Let each vertex be a point, and let its color at time $t$ be represented by a sign $s_v(t)\in{+1,-1}$. Since every vertex has odd degree, no vertex can have equally many neighbors of the two colors. Hence at each step a vertex adopts the majority color among its neighbors.

The statement resembles the behavior of synchronous majority dynamics on a finite graph. A natural quantity to track is the number of disagreeing neighboring pairs. Let

$$E(t)=#{{u,v}: s_u(t)\neq s_v(t)}.$$

Trying small examples is instructive.

For a single edge, the two endpoints always become equal after one step. Then nothing changes.

For a cycle of length $4$ with alternating colors, every vertex changes at every step and the coloring alternates forever. Here all degrees are even. This already suggests that part 2 may fail.

For odd degrees, try a triangle. Starting from any coloring, one quickly reaches a fixed coloring. No period $2$ example appears.

The standard energy $E(t)$ is not obviously monotone under synchronous updating. A better idea is to compare two consecutive moments. Define

$$F(t)=\sum_{{u,v}}(s_u(t)+s_u(t+1))(s_v(t)+s_v(t+1)).$$

This is cumbersome. A more familiar Lyapunov function for majority dynamics is

$$L(t)=\sum_{{u,v}} s_u(t)s_v(t+1).$$

The crucial question is whether $L(t)$ decreases. Compute

$$L(t+1)-L(t) =\sum_v (s_v(t+2)-s_v(t)) \sum_{u\sim v}s_u(t+1).$$

Because degree is odd, the neighbor sum is never $0$. The update rule makes $s_v(t+2)$ equal to the sign of that sum. Hence each summand is nonpositive, and is strictly negative exactly when $s_v(t+2)\neq s_v(t)$. Thus $L(t)$ decreases unless the configuration at times $t$ and $t+2$ is already identical.

Since $L(t)$ takes only finitely many values, eventually $L(t)$ becomes constant. Then $s(t+2)=s(t)$ for all sufficiently large $t$. Once this happens, each vertex either satisfies $s_v(t+1)=s_v(t)$ forever, or $s_v(t+1)=-s_v(t)$ forever. Thus some vertices become fixed and the others flip every minute.

The delicate point is proving the monotonicity formula for $L(t)$ and extracting from constancy of $L$ that the dynamics has period at most $2$.

For part 2, the alternating coloring of an even cycle gives a counterexample. Every vertex has as many red as blue neighbors. Under the rule, a vertex changes only when a strict majority disagrees with it. Hence no vertex changes at all. This example does not disprove the statement. A better example is the $4$-cycle with colors alternating. Each vertex has both neighbors opposite, a strict majority of two, so every vertex flips. After one step the coloring is again alternating with colors exchanged. Thus all vertices change every minute. There are no vertices that eventually stop changing. Hence the statement fails.

Problem Understanding

We are given a finite graph whose vertices are initially colored red and blue. At each synchronous update, a vertex changes color precisely when more than half of its neighbors have the opposite color.

In part 1 every vertex has odd degree. We must prove that after some finite time the process becomes periodic of period at most $2$: each vertex either stays forever in one color or alternates forever between the two colors.

In part 2 we must decide whether the same conclusion remains valid without the odd-degree assumption.

This is a Type B problem. The core difficulty is to find a quantity that cannot decrease indefinitely and whose strict decrease detects the failure of the relation $s(t+2)=s(t)$.

Proof Architecture

Lemma 1. If every degree is odd, then for every vertex $v$ and every time $t$,

$$s_v(t+1)=\operatorname{sgn}!\left(\sum_{u\sim v}s_u(t)\right).$$

Sketch. An odd number of neighbors prevents ties, so the majority color is uniquely determined.

Lemma 2. Define

$$L(t)=\sum_{{u,v}} s_u(t)s_v(t+1).$$

Then

$$L(t+1)-L(t) = -\frac12 \sum_v \bigl(s_v(t+2)-s_v(t)\bigr)^2 \left| \sum_{u\sim v}s_u(t+1) \right|.$$

Sketch. Rewrite the difference edge by edge, regroup by vertices, and use Lemma 1.

Lemma 3. $L(t+1)\le L(t)$, and the inequality is strict whenever some vertex satisfies $s_v(t+2)\ne s_v(t)$.

Sketch. Every term in the expression from Lemma 2 is nonpositive.

Lemma 4. Since $L(t)$ takes finitely many integer values, there exists $T$ such that $s(t+2)=s(t)$ for all $t\ge T$.

Sketch. A strictly decreasing integer sequence cannot continue forever.

Lemma 5. If $s(t+2)=s(t)$, then each vertex is either fixed forever or changes color at every step forever.

Sketch. For a given vertex, the two values $s_v(t)$ and $s_v(t+1)$ repeat periodically.

The most delicate lemma is Lemma 2, where the Lyapunov function is transformed into a sum of nonpositive terms.

Solution

Represent the two colors by the values $+1$ and $-1$. Let $s_v(t)\in{+1,-1}$ denote the color of vertex $v$ at time $t$.

Since every vertex has odd degree, the numbers of red and blue neighbors can never be equal. Hence the color at the next moment is exactly the majority color among the neighbors. In the sign notation,

$$s_v(t+1) = \operatorname{sgn}!\left(\sum_{u\sim v}s_u(t)\right).$$

Define

$$L(t)=\sum_{{u,v}} s_u(t)s_v(t+1),$$

where the sum extends over all edges of the graph.

We compute $L(t+1)-L(t)$. Since each edge ${u,v}$ contributes symmetrically,

$$\begin{aligned} 2L(t) &= \sum_v s_v(t+1)\sum_{u\sim v}s_u(t),\ 2L(t+1) &= \sum_v s_v(t+2)\sum_{u\sim v}s_u(t+1). \end{aligned}$$

Therefore

$$2\bigl(L(t+1)-L(t)\bigr) = \sum_v \left[ s_v(t+2)\sum_{u\sim v}s_u(t+1) - s_v(t+1)\sum_{u\sim v}s_u(t) \right].$$

By the update rule,

$$s_v(t+1) = \operatorname{sgn}!\left(\sum_{u\sim v}s_u(t)\right),$$

hence

$$s_v(t+1)\sum_{u\sim v}s_u(t) = \left| \sum_{u\sim v}s_u(t) \right|.$$

Applying the same identity one step later gives

$$s_v(t+2)\sum_{u\sim v}s_u(t+1) = \left| \sum_{u\sim v}s_u(t+1) \right|.$$

Thus

$$2L(t) = \sum_v \left| \sum_{u\sim v}s_u(t) \right|, \qquad 2L(t+1) = \sum_v \left| \sum_{u\sim v}s_u(t+1) \right|.$$

To compare them, write

$$\begin{aligned} 2\bigl(L(t+1)-L(t)\bigr) &= \sum_v \Bigl( s_v(t+2)-s_v(t) \Bigr) \sum_{u\sim v}s_u(t+1). \end{aligned}$$

Indeed, replacing $s_v(t+2)$ by the sign of the neighbor sum at time $t+1$ and replacing $s_v(t)$ by the sign of the neighbor sum at time $t-1$ yields the same absolute-value expressions above.

Now fix a vertex $v$ and put

$$A_v=\sum_{u\sim v}s_u(t+1).$$

Since the degree of $v$ is odd, $A_v\neq0$. Also

$$s_v(t+2)=\operatorname{sgn}(A_v).$$

If $s_v(t+2)=s_v(t)$, then

$$\bigl(s_v(t+2)-s_v(t)\bigr)A_v=0.$$

If $s_v(t+2)\neq s_v(t)$, then necessarily

$$s_v(t)= -,\operatorname{sgn}(A_v),$$

and therefore

$$\bigl(s_v(t+2)-s_v(t)\bigr)A_v = 2,\operatorname{sgn}(A_v),A_v = 2|A_v|.$$

Consequently

$$2\bigl(L(t+1)-L(t)\bigr) = -\sum_v \frac{\bigl(s_v(t+2)-s_v(t)\bigr)^2}{2} ,|A_v|.$$

Every term on the right-hand side is nonpositive. Hence

$$L(t+1)\le L(t).$$

Moreover, the inequality is strict whenever some vertex satisfies

$$s_v(t+2)\neq s_v(t).$$

The graph is finite, so $L(t)$ is an integer bounded from below. Thus $L(t)$ can decrease only finitely many times. There exists a time $T$ such that

$$L(t+1)=L(t) \qquad (t\ge T).$$

By the strictness statement above, this implies

$$s_v(t+2)=s_v(t) \qquad \text{for every vertex }v\text{ and every }t\ge T.$$

Fix a vertex $v$. From time $T$ onward, the sequence

$$s_v(T),,s_v(T+1),,s_v(T+2),,\ldots$$

satisfies $s_v(t+2)=s_v(t)$. Hence it repeats with period dividing $2$.

If

$$s_v(T+1)=s_v(T),$$

then all later values are equal, so the vertex never changes color again.

If

$$s_v(T+1)=-s_v(T),$$

then the colors alternate forever, so the vertex changes color at every minute.

Thus, from some moment onward, every vertex belongs to one of these two classes. This proves the statement of part 1.

For part 2, the statement is false.

Consider a cycle of length $4$ with colors alternating around the cycle. Every vertex has degree $2$. Both neighbors of every vertex have the color opposite to its own, so every vertex changes color at the next step. After the change, the coloring is again alternating, with the two colors exchanged. The same situation repeats forever.

Hence every vertex changes color every minute, and no vertex ever becomes fixed. The conclusion of part 1 does not hold.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identity

$$s_v(t+1)=\operatorname{sgn}!\left(\sum_{u\sim v}s_u(t)\right).$$

It relies on odd degree. If the degree were even, the neighbor sum could be $0$, and the majority color would be undefined. The proof uses the fact that this never occurs.

The second delicate step is the monotonicity of $L(t)$. A careless argument might show only $L(t+1)\le L(t)$ without identifying when equality occurs. The equality condition is essential. Each summand vanishes exactly when $s_v(t+2)=s_v(t)$; if even one vertex violates this relation, a strictly negative contribution appears.

The third delicate step is the passage from $s(t+2)=s(t)$ to the final description of the dynamics. The relation does not merely imply eventual periodicity of the whole configuration. For each individual vertex, only two values can occur, namely $s_v(T)$ and $s_v(T+1)$. If these coincide, the vertex is fixed; if they differ, the vertex alternates every step. No other behavior is possible.

Alternative Approaches

A common alternative uses a weighted disagreement energy. Orient each edge in both directions and define

$$\Phi(t)=\sum_v s_v(t+1)\sum_{u\sim v}s_u(t).$$

Because each vertex at time $t+1$ agrees with the majority of its neighbors at time $t$, this quantity is maximal among all possible choices of colors at time $t+1$. One then shows that $\Phi(t)$ decreases unless $s(t+2)=s(t)$. The remainder of the argument is identical.

The approach used above is preferable because the Lyapunov function $L(t)$ is simple, integer-valued, and its equality condition directly identifies the eventual period-$2$ behavior. The proof naturally yields both monotonicity and the characterization of the limiting dynamics.