Problema de Zarankiewicz

Para${\displaystyle s=t=2}$, un grafo bipartito con${\displaystyle n}$vértices en cada lado,${\displaystyle \Omega (n^{3/2})}$bordes y no${\displaystyle K_{2,2}}$puede obtenerse como el gráfico de Levi , o gráfico de incidencia punto-línea, de un plano proyectivo de orden${\displaystyle q}$, un sistema de${\displaystyle q^{2}+q+1}$puntos y${\displaystyle q^{2}+q+1}$líneas en las que cada par de puntos determina una línea única, y cada par de líneas se intersecan en un punto único. Construimos un grafo bipartito asociado a este plano proyectivo que tiene una parte de vértices como sus puntos, la otra parte de vértices como sus líneas, de tal manera que un punto y una línea están conectados si y solo si son incidentes en el plano proyectivo. Esto conduce a una${\displaystyle K_{2,2}}$-gráfico gratuito con${\displaystyle q^{2}+q+1}$vértices y${\displaystyle (q^{2}+q+1)(q+1)}$bordes. Dado que este límite inferior coincide con el límite superior dado por I. Reiman, ^{[ 11 ]} tenemos el asintótico ^{[ 12 ]}

${\displaystyle z(n;2)=(1/2+o(1))n^{3/2}.}$

Para${\displaystyle s=t=3}$, grafos bipartitos con${\displaystyle n}$vértices en cada lado,${\displaystyle \Omega (n^{5/3})}$bordes y no${\displaystyle K_{3,3}}$Puede construirse nuevamente a partir de geometría finita, haciendo que los vértices representen puntos y esferas (de un radio fijo cuidadosamente elegido) en un espacio afín finito tridimensional , y haciendo que las aristas representen incidencias punto-esfera. ^{[ 13 ]}

En términos más generales, considere${\displaystyle s=2}$y cualquier${\displaystyle t}$. Dejar${\displaystyle \mathbb {F} _{q}}$ser el${\displaystyle q}$campo finito de -elementos y${\displaystyle h}$ser un elemento de orden multiplicativo${\displaystyle t}$, en el sentido de que${\displaystyle H=\{1,h,\dots ,h^{t-1}\}}$forma un${\displaystyle t}$-subgrupo de elementos del grupo multiplicativo${\displaystyle \mathbb {F} _{q}^{*}}$Decimos que dos elementos distintos de cero${\displaystyle (a,b),(a',b')\in \mathbb {F} _{q}\times \mathbb {F} _{q}}$son equivalentes si tenemos${\displaystyle a'=h^{d}a}$y${\displaystyle b'=h^{d}b}$para algunos${\displaystyle d}$Consideremos un gráfico.${\displaystyle G}$en el conjunto de todas las clases de equivalencia${\displaystyle \langle a,b\rangle }$, de tal manera que${\displaystyle \langle a,b\rangle }$y${\displaystyle \langle x,y\rangle }$están conectados si y solo si${\displaystyle ax+by\in H}$. Se puede verificar que${\displaystyle G}$está bien definido y libre de${\displaystyle K_{2,t+1}}$y cada vértice en${\displaystyle G}$tiene título${\displaystyle q}$o${\displaystyle q-1}$. Por lo tanto, tenemos el límite superior ^{[ 14 ]}

${\displaystyle z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.}$

Para${\displaystyle t}$suficientemente más grande que${\displaystyle s}$, la conjetura anterior${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/s})}$fue verificado por Kollár, Rónyai y Szabó ^{[ 15 ]} y Alon, Rónyai y Szabó ^{[ 16 ]} utilizando la construcción de gráficos normativos y gráficos normativos proyectivos sobre campos finitos.

Para${\displaystyle t>s!}$, consideremos el grafo normado NormGraph _p,s con conjunto de vértices${\displaystyle \mathbb {F} _{p^{s}}}$, de tal manera que cada dos vértices${\displaystyle a,b\in \mathbb {F} _{p^{s}}}$están conectados si y solo si${\displaystyle N(a+b)=1}$, dónde${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$es el mapa de normas

${\displaystyle N(x)=x\cdot x^{p}\cdot x^{p^{2}}\cdots x^{p^{s-1}}=x^{(p^{s}-1)/(p-1)}.}$

No es difícil verificar que el gráfico tiene${\displaystyle p^{s}}$vértices y al menos${\displaystyle p^{2s-1}/2}$bordes. Para ver que este gráfico es${\displaystyle K_{s,s!+1}}$-libre, observe que cualquier vecino común${\displaystyle x}$de${\displaystyle s}$vértices${\displaystyle y_{1},\ldots ,y_{s}\in \mathbb {F} _{p^{s}}}$debe satisfacer

${\displaystyle 1=N(x+y_{i})=(x+y_{i})\cdot (x+y_{i})^{p}\cdots (x+y_{i})^{p^{s-1}}=(x+y_{i})\cdot (x^{p}+y_{i}^{p})\cdots (x^{p^{s-1}}+y_{i}^{p^{s-1}})}$

a pesar de${\displaystyle i=1,\ldots ,s}$, que es un sistema de ecuaciones que tiene como máximo${\displaystyle s!}$soluciones.

El mismo resultado puede demostrarse para todos${\displaystyle t>(s-1)!}$utilizando el grafo de norma proyectiva , una construcción ligeramente más fuerte que la anterior. El grafo de norma proyectiva ProjNormGraph _p,s es el grafo en el conjunto de vértices${\displaystyle \mathbb {F} _{p^{s-1}}\times \mathbb {F} _{p}^{\times }}$, de tal manera que dos vértices${\displaystyle (X,x),(Y,y)}$son adyacentes si y solo si${\displaystyle N(X+Y)=xy}$, dónde${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$es el mapa de normas definido por${\displaystyle N(x)=x^{(p^{s}-1)/(p-1)}}$. Mediante un argumento similar al anterior, se puede verificar que es un${\displaystyle K_{s,t}}$-gráfico gratuito con${\displaystyle \Omega (n^{2-1/s})}$bordes.

El enfoque del gráfico de norma anterior también proporciona límites inferiores ajustados en${\displaystyle z(m,n;s,t)}$para ciertas opciones de${\displaystyle m,n}$. ^{[ 16 ]} En particular, para${\displaystyle s\geq 2}$,${\displaystyle t>s!}$, y${\displaystyle n^{1/t}\leq m\leq n^{1+1/t}}$, tenemos

${\displaystyle z(m,n;s,t)=\Theta (mn^{1-1/s}).}$

En el caso${\displaystyle m=(1+o(1))n^{1+1/s}}$Consideremos el grafo bipartito.${\displaystyle G}$con bipartición${\displaystyle V=V_{1}\cup V_{2}}$, de tal manera que${\displaystyle V_{1}=\mathbb {F} _{p^{t}}\times \mathbb {F} _{p}^{\times }}$y${\displaystyle V_{2}=\mathbb {F} _{p^{t}}}$. Para${\displaystyle A\in V_{1}}$y${\displaystyle (B,b)\in V_{2}}$, dejar${\displaystyle A\sim (B,b)}$en${\displaystyle G}$si y solo si${\displaystyle N(A+B)=b}$, dónde${\displaystyle N(\cdot )}$es el mapa de normas definido anteriormente. Para ver que${\displaystyle G}$es${\displaystyle K_{s,t}}$-gratis, considere${\displaystyle s}$tuplas${\displaystyle (B_{1},b_{1}),\ldots ,(B_{s},b_{s})\in V_{1}}$. Observe que si el${\displaystyle s}$Si las tuplas tienen un vecino común, entonces${\displaystyle B_{i}}$deben ser distintos. Usando el mismo límite superior en el número de soluciones del sistema de ecuaciones, sabemos que estos${\displaystyle s}$Las tuplas tienen como máximo${\displaystyle s!<t}$vecinos comunes.

Utilizando un resultado relacionado sobre números de partición de cliques, Alon, Mellinger, Mubayi y Verstraëte ^{[ 17 ]} demostraron una cota inferior ajustada sobre${\displaystyle z(m,n;2,t)}$para arbitrario${\displaystyle t}$: si${\displaystyle m=(1+o(1))n^{t/2}}$, entonces tenemos

${\displaystyle z(m,n;2,t)=(1+o(1))mn^{1/2}}$.

Para${\displaystyle 2\leq t\leq n}$, decimos que una colección de subconjuntos ${\displaystyle A_{1},\dots ,A_{\ell }\subset [n]}$es una partición de camarilla de${\displaystyle H\subset {[n] \choose t}}$si${\displaystyle \bigcup _{i=1}^{\ell }{A_{i} \choose t}}$formar una partición de ${\displaystyle H}$. Observe que para cualquier${\displaystyle k}$, si existe alguna${\displaystyle H\subset {[n] \choose t}}$de tamaño${\displaystyle (1-o(1)){n \choose t}}$y${\displaystyle m=(1+o(1)){n \choose t}/{k \choose t}}$, de tal manera que exista una partición de${\displaystyle H}$en${\displaystyle m}$camarillas de tamaño${\displaystyle k}$, entonces tenemos${\displaystyle z(m,n;2,t)=km}$. De hecho, suponiendo${\displaystyle A_{1},\dots ,A_{m}\subset [n]}$es una partición de${\displaystyle H}$en${\displaystyle m}$camarillas de tamaño${\displaystyle k}$, podemos dejar${\displaystyle G}$ser el${\displaystyle m\times n}$grafo bipartito con${\displaystyle V_{1}=\{A_{1},\dots ,A_{m}\}}$y${\displaystyle V_{2}=[n]}$, de tal manera que${\displaystyle A_{i}\sim v}$en${\displaystyle G}$si y solo si${\displaystyle v\in A_{i}}$. Desde el${\displaystyle A_{i}}$formar una partición de camarilla,${\displaystyle G}$no puede contener una copia de${\displaystyle K_{2,t}}$.

Queda por demostrar que tal partición de camarilla existe para cualquier${\displaystyle m=(1+o(1))n^{t/2}}$Para demostrar esto, dejemos${\displaystyle \mathbb {F} _{q}}$sea ​​el campo finito de tamaño${\displaystyle q}$y${\displaystyle V=\mathbb {F} _{q}\times \mathbb {F} _{q}}$. Para cada polinomio${\displaystyle p(\cdot )}$de grado como máximo${\displaystyle t-1}$encima${\displaystyle \mathbb {F} _{q}}$, definir${\displaystyle C_{p}=\{(x,p(x)):x\in \mathbb {F} _{q}\}\subset V}$. Dejar${\displaystyle {\mathcal {C}}}$ser la colección de todos${\displaystyle C_{p}}$, de modo que${\displaystyle |{\mathcal {C}}|=q^{t}=n^{t/2}}$y cada${\displaystyle C_{p}}$tiene tamaño${\displaystyle q={\sqrt {n}}}$. Claramente no hay dos miembros de${\displaystyle {\mathcal {C}}}$pueden compartir${\displaystyle t}$miembros. Dado que el único${\displaystyle t}$-conjuntos en${\displaystyle V}$que no pertenecen a${\displaystyle H}$son aquellos que tienen al menos dos puntos que comparten la misma primera coordenada, sabemos que casi todos${\displaystyle t}$-subconjuntos de${\displaystyle V}$están contenidos en algunos${\displaystyle C_{p}}$.

Pruebas alternativas de${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$para${\displaystyle t}$suficientemente más grande que${\displaystyle s}$También fueron proporcionados por Blagojević, Bukh y Karasev ^{[ 18 ]} y por Bukh ^{[ 19 ]} utilizando el método de construcciones algebraicas aleatorias. La idea básica es tomar un polinomio aleatorio${\displaystyle f:\mathbb {F} _{q}^{s}\times \mathbb {F} _{q}^{s}\rightarrow \mathbb {F} _{q}}$y considere el gráfico${\displaystyle G}$entre dos copias de${\displaystyle \mathbb {F} _{q}^{s}}$cuyos bordes son todos esos pares${\displaystyle (x,y)}$de tal manera que${\displaystyle f(x,y)=0}$.

Para empezar, dejemos${\displaystyle q}$ser una potencia principal y${\displaystyle n=q^{2}}$. Dejar

${\displaystyle f\in \mathbb {F} _{q}[x_{1},\dots ,x_{s},y_{1},\dots ,t_{s}]_{\leq s^{2}}}$

sea ​​un polinomio aleatorio con grado como máximo${\displaystyle s^{2}}$en${\displaystyle X=(x_{1},\dots ,x_{s})}$, grado como máximo${\displaystyle s^{2}}$en${\displaystyle Y=(y_{1},\dots ,y_{s})}$y además satisfactorio${\displaystyle f(X,Y)=f(Y,X)}$a pesar de${\displaystyle X,Y}$. Dejar${\displaystyle G}$sea ​​el grafo aleatorio asociado en el conjunto de vértices${\displaystyle \mathbb {F} _{q}^{s}}$, de tal manera que dos vértices${\displaystyle x}$y${\displaystyle y}$son adyacentes si y solo si${\displaystyle f(x,y)=0}$.

Para demostrar la cota inferior asintótica, basta con mostrar que el número esperado de aristas en${\displaystyle G}$es${\displaystyle \Omega (q^{2s-1})}$. Por cada${\displaystyle s}$-subconjunto${\displaystyle U\subset \mathbb {F} _{q}^{s}}$, dejamos${\displaystyle Z_{U}}$denota el subconjunto de vértices de${\displaystyle \mathbb {F} _{q}^{s}\setminus U}$que "desaparece en${\displaystyle f(\cdot ,U)}$":

${\displaystyle Z_{U}=\{x\in \mathbb {F} _{q}^{s}\setminus U:f(x,u)=0{\text{ for all }}u\in U\}}$.

Utilizando la cota de Lang-Weil para polinomios${\displaystyle f(\cdot ,u)}$en${\displaystyle \mathbb {F} _{q}^{s}}$, podemos deducir que uno siempre tiene${\displaystyle Z_{U}\leq C}$o${\displaystyle Z_{U}>q/2}$para alguna constante grande${\displaystyle C}$, lo cual implica

${\displaystyle \mathbb {P} (|Z_{U}|>C)=\mathbb {P} (|Z_{U}|>q/2)}$.

Desde${\displaystyle f}$se elige aleatoriamente sobre${\displaystyle \mathbb {F} _{q}}$, no es difícil demostrar que la probabilidad del lado derecho es pequeña, por lo que el número esperado de${\displaystyle s}$-subconjuntos${\displaystyle U}$con${\displaystyle |Z_{U}|>C}$también resultó ser pequeño. Si eliminamos un vértice de cada uno de ellos${\displaystyle U}$, entonces el gráfico resultante es${\displaystyle K_{s,C+1}}$libre, y el número esperado de aristas restantes sigue siendo grande. Esto finaliza la prueba de que${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$a pesar de${\displaystyle t}$suficientemente grande con respecto a${\displaystyle s}$Más recientemente, se han obtenido varios resultados que verifican la conjetura.${\displaystyle z(m,n;s,t)=\Omega (n^{2-1/s})}$para diferentes valores de${\displaystyle s,t}$, utilizando ideas similares pero con más herramientas de la geometría algebraica. ^{[ 8 ] [ 20 ]}