2
$\begingroup$

Problem 6 of 2008 Iran TST is as follows:

Let $T$ be a directed complete graph with $801$ vertices. Prove you can find two disjoint set of vertices $L, R \subset V_T$ with $|L| = |R| = 7$ such that for every $v \in L, w \in R$, the $\overline{vw}$ edge is directed from $v$ towards $w$.

The problem admits a probabilistic method solution, and I was thinking of applying probabilistic method in this way, which don't work:

It can be proved easily using Pigeonhole Principle that for any complete graph with $n$ vertices, there's a vertex having outdegree atleast $\frac{n-1}{2}$.

So, based on this it's not terribly hard to see for $w \leq \frac{n-1}{2}$, we can partition $V_T = W \cup L$ with $W \cap L = \{ \phi \}$ and $|W| = w$ such that for every vertex $v \in W$, there are atleast $\frac{n-w}{2}$ vertices $u_1, \cdots, u_{\frac{n-w}{2}} \in L$ such that the edge $vu_i$ is from $v$ towards $u_i$.

Now, for a random subset $S$ having $7$ elements from $L$, let the random variable $X_S$ denote the number of vertices in $W$ which have an edge towards every vertex in $S$. Also, for $1 \leq i \leq w$, let $X_{S,i}$ denote $1$ if $v_i \in W$ has an edge directed towards every vertex in $S$, or $0$ otherwise.

Note that $\mathbb{E}[X_{S,i}] = \frac{\binom{d_i}{7}}{\binom{n-w}{7}} \geq \frac{\binom{\frac{n-2w}{2}}{7}}{\binom{n-w}{7}}$, where $d_i$ denotes the number of vertices $u \in L$ such that there's an edge from $v_i$ towards $u$. Using linearity of expectation, we have $$ \mathbb{E}[X_S] = \mathbb{E}[\sum_{1 \leq i \leq w} X_{S, i}] = \sum_{1 \leq i \leq w} \mathbb{E}[X_{S,i}] \geq \frac{w\binom{\frac{n-2w}{2}}{7}}{\binom{n-w}{7}} \approx \frac{w}{2^7} $$. If we pick $w = 385$, this gives $\mathbb{E}[X_S] > 3$ - hence there's an $S$ with $X_S$ atleast $4$, which proves the weaker version of the problem: We can find $L, R \subset V_T$ with $|L| = 4$ and $|R| = 7$ such that for every $v \in L, w \in R$, the $\overline{vw}$ edge is directed from $v$ towards $w$.

The official solution is this:

For a random subset $S \subset V_T$ with $|S| = 7$, let $X_S$ denote the number of vertices $v \in T$ such that it has an edge towards every vertex of $S$. Also, let $X_{S,v}$ denote $1$ if there's an edge from $v$ towards every vertex of $S$, or $0$ otherwise. Letting $d_v$ to be the outdegree of $v$, we clearly have $\mathbb{E}[X_{S,v}] = \frac{\binom{d_v}{7}}{\binom{801}{7}}$.

Using linearity of expectation and convexity of $\binom{x}{7}$, Jensen's inequality and the fact (easily proved by double counting) $\sum_{v \in T} d_v = \frac{800*801}{2}$, we get $$\mathbb{E}[X_S] = \mathbb{E}[\sum_{v \in T} X_{S,v}] = \sum_{v \in T} \mathbb{E}[X_{S,v}] = \sum_{v \in T} \frac{\binom{d_v}{7}}{\binom{801}{7}} \geq \frac{801 \binom{\frac{\sum_{v \in T}{d_v}}{801}}{7}}{\binom{801}{7}} = \frac{801 \binom{400}{7}}{\binom{801}{7}} > 6$$, hence there's atleast one $S$ with $X_S \geq 7$, which ceases the deal.

The thing I don't have any intution is that I find the official solution uses a more "dumb" argument that mine - for example, if there's some vertex which has no outdegree, it's useless to count $X_S$ for that as that would reduce the $\mathbb{E}[X_S]$. But the official solution counts $X_S$ for every vertices - while in my solution I count them only for vertices which have high outdegrees ($\geq \frac{n-2w}{2}$)-but still my solution fails to prove the problem, but the official solution magically works.

What's a rough intuition behind the fact that my arguement will fail (or does a modification of that works ?)

$\endgroup$
  • $\begingroup$ By $W \cap L = \{\phi\}$ do you mean $W \cap L = \varnothing$? $\endgroup$ – Misha Lavrov Aug 29 '18 at 20:37
2
$\begingroup$

The vertices you are picking don't actually have particularly high out-degree - at least, not as far as your solution can tell.

If you pick $w = 1$, then you are observing that there is a vertex with out-degree $\frac{n-1}{2}$. But the average out-degree in a directed complete graph is $\frac{n-1}{2}$ (since the sum of the out-degrees is $\frac{n(n-1)}{2}$, and there are $n$ vertices). So when $w=1$, you've found $1$ vertex that is average.

When $w$ is large, you are picking $w$ vertices that have degree at least $\frac{n-2w}{2}$. But this degree bound is actually substantially below average. If $n=801$ and $w=385$, these vertices have degree at least $16$ (and I'm actually not sure your approximation of $\frac{w}{2^7}$ holds up in this case). The average degree, meanwhile, is still $400$.

So you may be picking the $w$ vertices with the highest degree, but you're not using the fact that they have high degree.

Meanwhile, the official solution is using all vertices, but it is taking into account the actual out-degree $d_v$ of every vertex. The application of Jensen's inequality lets us reduce to the worst case: the expected value is minimized when all out-degrees are equal, which means they're all $\frac{n-1}{2}$. In this case, we get more vertices to consider than you do, and their out-degrees are all higher than your lower bounds on them, so the result is better.

(This is the worst case because if there are vertices with very low degree, there are also vertices with high degree to make up for it. The high degree helps us more than the low degree hurts us because $\binom{d_v}{2}$ is quadratic in the degree: this is essentially what the convexity argument is about.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.