Cómo demostrar que la eliminación de un máximo de $(m-s)(n-t)/s$ bordes de un $K_{m,n}$ nunca destruirá todo su $K_{s,t}$ subgráficos.

Question

Este problema es de Teoría de Grafos de Diestel Capítulo 7 (Teoría de Grafos Extremos) sección 5 (lema de regularidad) problema 9.

Estaba pensando en aplicar el teorema de Erdos y Stone, pero sinceramente estoy perdido y no estoy seguro de cómo abordar este problema. Cualquier ayuda será muy apreciada.

Answer 1

El Función Zarankiewicz $z(m, n; s, t)$ denota el máximo número posible de aristas en un grafo bipartito $G = (U, V, E)$ para lo cual $|U| = m$ y $|V| = n$ pero que no contiene un subgrafo de la forma $Ks,t$ .

Por lo tanto, basta con demostrar que $z(m, n; s, t)\le mn-(m-s)(n-t)/s-1$ . Para ello contamos con una herramienta tan potente como Teorema de Kovári-Sós-Turán . Por eso,

$$z(m, n; s, t)<(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m.$$

Por lo tanto, basta con demostrar que

$(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m\le mn-(m-s)(n-t)/s-1$

$(s-1)^{1/t}(n-t+1)m^{-1/t}+t-1\le n-(1-s/m)(n-t)/s-1$

$\left(\frac{s-1}m\right)^t(n-t-1)+\left(\frac 1s-\frac 1m\right)(n-t)+t\le n$ .

Por lo tanto, basta con demostrar que

$\left(\frac{s-1}m\right)^t+\frac 1s-\frac 1m\le 1$ .

Suponiendo que $t,s\ge 1$ y $s-1\le m$ basta con demostrar que

$\frac{s-1}m+\frac 1s-\frac 1m\le 1$

$s^2-2s+m\le sm$

$s^2\le (s-1)m+2s$ .

Pero $(s-1)m+2s\ge (s-1)^2+2s=s^2+1>s^2$ .

PS. Si uno prefiere una prueba casera a una civilizada, entonces podemos considerar los siguientes argumentos. Sea la bipartición de vértices del grafo $K_{m,n}$ está constituido por $m$ vértices rojos $\{v_1,\dots, v_m\}$ y $n$ vértices azules. Supongamos que hemos eliminado $d$ aristas del gráfico $K_{m,n}$ y el gráfico resultante $G$ no contiene $K_{s,t}$ subgráficos. Sea $1\le s\le m$ , $1\le t\le n$ y $$\deg v_1\ge \deg v_2\ge \dots \ge \deg v_s\ge\dots \ge \deg v_m$$ sean los grados de los vértices rojos de $G$ . Como el conjunto de vértices azules no contiene ningún subconjunto de tamaño $t$ con cada vértice adyacente a cada uno de los vértices $\{v_1,\dots, v_s\}$ entonces

$$(n-\deg v_1)+ (n-\deg v_2)+\dots+(n-\deg v_s)\ge n-t+1$$

$$ns-\sum_{i=1}^s \deg v_i\ge n-t+1$$

$$ns-n+t-1 \ge \sum_{i=1}^s \deg v_i$$

Por otra parte, dado que $\deg v_1\ge \deg v_2\ge \dots \deg v_m$ ,

$$\sum_{i=1}^s \deg v_i\ge\frac sm\left(\sum_{i=1}^m \deg v_i\right)= \frac sm|E(G)|= \frac sm (mn-d).$$

$$ns-n+t-1\ge \frac sm (mn-d)$$

$$d \ge \frac{m(n-t+1)}{s}$$

Por lo tanto, basta con demostrar que

$\frac{m(n-t+1)}{s}\ge \frac{(m-s)(n-t)}{s}+1$

$m(n-t+1) \ge (m-s)(n-t) +s$

$mn-mt+m \ge mn-mt-ns+st+s$

$ns+m \ge st+s$

que se desprende de $n\ge t$ y $m\ge s$ .