Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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