2
$\begingroup$

Show that deleting at most (m-s)(n-t)/s edges from a K_{m,n} will never destroy all its K_{s,t} subgraphs. I'm completly stuck here and any help would be welcome!

2 Answers 2

4

Here is a hint: If you can find some number $N$ of edge-disjoint $K_{s,t}$ subgraphs of $K_{m,n}$, then because they are edge-disjoint, you would have to delete at least $N$ edges from $K_{m,n}$ to be sure none of your subgraphs was intact.

0

Firstly, I'll assume $m \geq s \geq 1$ and $n \geq t \geq 1$, otherwise the claim is boring (or false). We can further assume $m>s$, otherwise the claim is trivial.

Notation: We can find $\lfloor m/s \rfloor$ disjoint $s$-subsets $S_1,S_2,\ldots,S_{\lfloor m/s \rfloor}$ of the vertices belonging to the part of size $m$. Let the vertices belonging to the part of size $n$ be labelled $1,2,\ldots,n$.

Algorithm

We will analyse the following algorithm for finding a $K_{s,t}$ subgraph:

  • Input: any subgraph $G$ of $K_{m,n}$. Let $D$ be the set of edges deleted from $K_{m,n}$ to form $G$.

  • For $i \in \{1,2,\ldots,\lfloor m/s \rfloor\}$ do:

    • Set $T=\{1,2,\ldots,t\}$.

    • While (true) do:

      • If $S_i \cup T$ induces a $K_{s,t}$ in $G$ then we are done (return $S_i \cup T$).

      • Otherwise there exists an edge $e_\mathrm{left}e_\mathrm{right} \in D$ with $e_\mathrm{left} \in S_i$ and $e_\mathrm{right} \in T$. Delete $e_\mathrm{right}$ from $T$.

      • If $\mathrm{max}(T)+1 \leq n$ then add $\mathrm{max}(T)+1$ to $T$. Otherwise break (out of the while loop).

  • return fail.

Analysis

Assume a $K_{s,t}$ is not found (i.e., fail is returned). For any $i$, the while loop will be executed exactly $n-t+1$ times (since $\max(T)$ increases by $1$ in each iteration). The for loop will be executed exactly $\lfloor m/s \rfloor$ times. Thus, in total, the while loop is executed $\lfloor m/s \rfloor(n-t+1)$ times. In each execution of the while loop, a distinct deleted edge is identified. Thus, at least $\lfloor m/s \rfloor(n-t+1)$ edges must have been deleted from $K_{m,n}$. This implies the claim in the question.


Note that aaron's earlier suggested approach does not work in general; a counterexample is when $m=n=7$ and $s=1$ and $t=4$. There are $7^2=49$ edges in $K_{7,7}$ and therefore there can be at most $\lfloor 49/4 \rfloor=12$ edge-disjoint copies of $K_{1,4}$ in $K_{7,7}$. However, the question allows us to delete $(m-s)(n-t)/s=18$ edges, which is more than enough to destroy $\leq 12$ edge-disjoint copies of $K_{1,4}$.