Integers $n$ and $k$ satisfy $n > 2023k^3$. Kingdom Kitty has $n$ cities, with at most one road between each pair of cities. It is known that the total number of roads in the kingdom is at least $2n^{3/2}$. Prove that we can choose $3k + 1$ cities such that the total number of roads with both ends being a chosen city is at least $4k$.
Problem
Source: 2023 Taiwan TST Round 2 Independent Study 1-C
Tags: Taiwan TST, combinatorics, Taiwan
asbodke
08.04.2023 04:19
We present a sketch; the approximations here can easily be made more rigorous. Obviously, the average degree is $4\sqrt n$. The expected number of $K_{1,2}$s in the graph is \[ \sum_v \binom{d(v)}2 \ge \frac{n(4\sqrt n)^2}{2}=8n^2\]by Jensen. If $k=1$, then choose two vertices at random. The expected number of vertices adjacent to both of these vertices is \[ 8n^2 \binom n2^{-1} = 16>2.\]Thus we can take any $2$ of these vertices to create a $4$-cycle, as desired. Now we look at $k>1$. Pick $k$ vertices at random, forming a set $S$. There are an expected $8n^2(\tfrac{k^2}{n^2})>2k$ $K_{1,2}$s with two vertices of $S$ as leaves. Thus there are at least $2k$ vertices adjacent to $2$ vertices of $S$ (the number of vertices adjacent to $3$ or more vertices of $S$ can easily be proven to be negligible.) Combining $S$ with these $2k$ vertices, we get a subgraph with at least $4k$ edges, as desired.
starchan
09.03.2024 21:42
solved with Rushil, Adhitya, Ananda, Kanav, Siddharth, Malay
Lemma: If I have a graph $G$ on $m$ vertices with more than $m^{3/2}$ edges, then I can find a square in $G$.
Proof: For every vertex $u$ I first mark with $u$ all pairs of vertices $(v, w)$ for $v \ne w$ such that $uv, uw \in e(G)$. Every vertex $u$ marks at least \[\binom{d_G(u)}{2}\]pairs, and thus overall at least \[\sum \limits_{u \in v(G)} \binom{d_G(u)}{2}\]markings are made. From Jensen, this is at least \[ m \sum \limits_{u} \binom{\delta(G)}{2} > m^2\]where $\delta(G)$ is the average degree and the last bound follows from $\delta(G) \geq 2\sqrt{m}$.
It follows that I marked some pair $(v_1, v_2)$ is with at least two vertices $(u_1, u_2)$. It now follows that $u_1v_1u_2v_2$ is a cycle, which is the square we wanted.
As usual, I model Kingdom Kitty as a graph $G$ on $n$ vertices. While I can select a square, I will choose it and delete all its edges from the graph. I can do this while $e(G) > n^{3/2}$. Initially $e(G) > 2n^{3/2}$, and I lose exactly $4$ edges each time, so I will obtain at least $\frac{1}{4}n^{3/2}$ cycles.
I will then count for each vertex $v$ how many cycles it is a part of. The sum of these counts is at least $n^{3/2}$ and thus I will be able to ensure having some vertex in at least $1/n \cdot n^{3/2} = \sqrt{n}$ cycles.
Let these cycles be $C_1, C_2, \dots, C_{\ell}$, where $\ell \geq \sqrt{n} \geq k$. Consider the subgraph induced by the union of $C_1, C_2, \dots, C_k$. This has at most $3k+1$ vertices (at least one vertex is common to all of them) and exactly $4k$ edges. I add in more vertices to this union until it has exactly $3k+1$ vertices.
Now I have exactly $3k+1$ vertices in my induced subgraph $H$ and it has at least $4k$ edges, so I am done. $\square$
math_comb01
15.04.2024 20:26
Very cute! Claim 1: If there are more than $|E|^{3/2}$ edges, then there exists a $4$ cycle.
Clear, just count the number of $K_{1,2}$ and then just use jensen
Now, just choose as many squares as we can and we get $n^{3/2}/4$, then we have a vertex in at least $\sqrt{n} \geq k$ cycles, and now keep adding more vertices until it reaches $3k+1$ vertices and done.