Let $N$ be a positive integer. Kingdom Wierdo has $N$ castles, with at most one road between each pair of cities. There are at most four guards on each road. To cost down, the King of Wierdos makes the following policy: (1) For any three castles, if there are roads between any two of them, then any of these roads cannot have four guards. (2) For any four castles, if there are roads between any two of them, then for any one castle among them, the roads from it toward the other three castles cannot all have three guards. Prove that, under this policy, the total number of guards on roads in Kingdom Wierdo is smaller than or equal to $N^2$. Remark: Proving that the number of guards does not exceed $cN^2$ for some $c > 1$ independent of $N$ will be scored based on the value of $c$. Proposed by usjl
Problem
Source: 2023 Taiwan TST Round 3 Mock Exam P5
Tags: graph theory, Taiwan, combinatorics
29.04.2023 09:37
good question. respect from the other side of the channel.
29.04.2023 11:02
Consider a clique decomposition of the graph which minimizes the number of "cross-edges" between cliques.Now consider cliques of sizes $a_i$ and $a_j$(Call them A and B),with a cross edge.WLOG $a_j \ge a_i$.By the condition ,$a_j$ is at least two .Now consider a vertex in A,then the sum of weights of edges from that vertex into B is atmost $2a_j$.If there is exactly one edge its obvious.Assuming there are at least two edges,we must have that their weight is at most $2(a_j-3)+6$,since it is connected to atmost $a_j-1$ vertices in B,due to the minimality condition as we can otherwise move it to B.Thus there are at most $2a_i*a_j$ edge weights between them.Summing over all cliques ,we have the edge weight sum is at most sum($a_i^2$)+2 sum($a_i.a_j$) which is $N^2$.
29.04.2023 17:50
Not as nice of a solution, but I think it works. First we note, that if there exist an edge with 4 guards in it, the induction is very simple. Now let an edge be blue if it has 2 guards and red if it has 3. Case 1. There exists a red cycle a_1, a_2, … a_j where all the non adjacent vertices are connected by a blue edge. Let this cycle be A and the rest of the graph be B. We see that there are at most twice as many red edges between A and B than there are non-edges between A and B, which follows from the (2) condition. This gives a nice enough bound for the sum of weights of edges between A and B so we can proceed with induction. Case 2. There doesn’t exist such a cycle. Take the longest red path a_1, a_2, …a_j where a_1 isn’t connected with a_j ,but all the other vertices a connected by red or blue edges. Call the vertices of this graph A and the rest of the graph B. Once again we can bound the sum of weights between A and B. Take a vertices X from B. If X is connected by a red edge to say a_k and a_l with k < l, then there must exist k < m < l, such that X and a_m aren’t connected or we get back to Case 1. So if there are at least 2 red edges between A and B, once again it holds that the number of non-edges is not less and half of the red edges. So the only way this doesn’t hold if there is only 1 red edge between A and B and all the others are blue (the are no non-edges). From the condition (2) of the problem we get that the red edge must either be connected to a_1 or a_j, but then we get a longer red path. So contradiction.
04.08.2023 18:17
IAmTheHazard wrote: ZYKOV SYMMETRIZATION ZYKOV SYMMETRIZATION Let $f(v)$ denote the number of guards on some edge adjacent to a vertex $v$. If $f(v)>f(w)$ where $v$ and $w$ aren't adjacent, then we can delete $w$ and the edges containing it and replace it with a copy $v'$ of $v$ (with the same number of guards on edges). This preserves the desired properties of the graph, since $v$ and $w$ were not adjacent, hence if some edge $\overline{uv'}$ is part of a $K_3$ then $\overline{uv}$ was part of an isomorphic (i.e. same edge weights) $K_3$ pre-replacement, and the same is true if $\overline{uv'}$ is part of a $K_4$, hence copying the number of guards on $\overline{uv}$ works and increases the total number of guards. Therefore, consider a graph $G$ with number of guards maximal. I claim that $G$ is a complete multipartite graph. Indeed, if we have some vertices $u,v,w$ such that $u$ isn't adjacent to $v$ or $w$, but $\overline{vw}$ is an edge, we can delete both $v$ and $w$ and replace them with copies of $u$. Since any optimal graph clearly will have at least two guards on every edge, the number of guards on $\overline{vw}$ pre-replacement is double-counted in $f(v)+f(w)$, hence the total number of guards will increase with this operation. Thus, in an optimal graph, anti-adjacency is transitive, which implies the desired claim. We now consider the following cases: Case 1: $G$ is bipartite. Then it clearly has at most $N^2/4$ edges, and hence at most $N^2$ guards. Case 2: $G$ is $3$-partite. Then it clearly has at most $N^2/3$ edges, and since every edge is part of a triangle, at most $N^2$ guards. Case 3: $G$ is $k$-partite, where $k \geq 4$. Then every edge is part of a $K_4$, so for every vertex $v$, there are at most two $k$-partite "independent sets", neither of which is the one that $v$ lies in, such that there exists an edge from $v$ to these independent sets having $3$ guards—all the others must have $2$ guards. Then take the largest independent set, which contains $i$ vertices, and pick a vertex from it. This vertex has $N-i$ edges connected to it, and at most $2i$ of them can have $3$ guards, hence $$f(v) \leq 3(2i)+2(N-3i)=2N,$$with equality only holding if the two other independent sets we pick are also maximal. If there exists some $f(v) \leq 2N-1$ (where $v$ is in a maximal independent set) then we can delete it and apply inductive hypothesis to the remaining graph. Otherwise, if equality holds for every vertex, then no vertex $w$ in a non-maximal independent set can be in an edge with $3$ guards, so there are at most $2(N-1)$ guards on the edges of $w$, so we can delete it and induct down as well. It remains to deal with the case where there are no non-maximal independent sets, i.e. every independent set has size $i$. But then summing $f(v) \leq 2N$ over every vertex yields the desired result. These three cases combined finish the problem. $\blacksquare$ Remark: I would be interested in a proof of case 3 which is cleaner. That being said, I don't think case 3 is particularly hard to handle in the way I did it here—just messy.
04.08.2023 18:35
IAmTheHazard wrote: Remark: I would be interested in a proof of case 3 which is cleaner. That being said, I don't think case 3 is particularly hard to handle in the way I did it here—just messy. The symmetrization trick allows you to assume that the weights of the edges between any given pair of independent sets are all the same. You can also notice that if we shrink all the independent sets to a vertex, then the weight-3 edges form disjoint cycles. The rest is just a simple counting+AM-GM.