Problema de Zarankiewicz

El problema de Zarankiewicz , un problema no resuelto en matemáticas, pide el mayor número posible de aristas en un grafo bipartito que tiene un número dado de vértices y no tiene subgrafos bipartitos completos de un tamaño dado. ^[1] Pertenece al campo de la teoría de grafos extremales , una rama de la combinatoria , y lleva el nombre del matemático polaco Kazimierz Zarankiewicz , quien propuso varios casos especiales del problema en 1951. ^[2]

Planteamiento del problema

Un grafo bipartito consta de dos conjuntos disjuntos de vértices y , y un conjunto de aristas cada una de las cuales conecta un vértice en con un vértice en . No hay dos aristas que puedan conectar a la vez el mismo par de vértices. Un grafo bipartito completo es un grafo bipartito en el que cada par de un vértice de y un vértice de está conectado entre sí. Un grafo bipartito completo en el que tiene vértices y tiene vértices se denota . Si es un grafo bipartito, y existe un conjunto de vértices de y vértices de que están todos conectados entre sí, entonces estos vértices inducen un subgrafo de la forma . (En esta formulación, el orden de y es significativo: el conjunto de vértices debe ser de y el conjunto de vértices debe ser de , no al revés). ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle s}$ ${\displaystyle V}$ ${\displaystyle t}$ ${\displaystyle K_{s,t}}$ ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle s}$ ${\displaystyle U}$ ${\displaystyle t}$ ${\displaystyle V}$ ${\displaystyle K_{s,t}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle U}$ ${\displaystyle t}$ ${\displaystyle V}$

La función de Zarankiewicz denota el número máximo posible de aristas en un grafo bipartito para el cual y , pero que no contiene un subgrafo de la forma . Como abreviatura para un caso especial importante, es lo mismo que . El problema de Zarankiewicz pide una fórmula para la función de Zarankiewicz o (en su defecto) límites asintóticos estrictos para la tasa de crecimiento de suponiendo que es una constante fija, en el límite cuando tiende al infinito. ${\displaystyle z(m,n;s,t)}$ ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle |U|=m}$ ${\displaystyle |V|=n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle z(n;t)}$ ${\displaystyle z(n,n;t,t)}$ ${\displaystyle z(n;t)}$ ${\displaystyle t}$ ${\displaystyle n}$

Este problema es el mismo que el de determinar jaulas con circunferencia seis. El problema de Zarankiewicz, las jaulas y la geometría finita están fuertemente interrelacionados. ^[3] ${\displaystyle s=t=2}$

El mismo problema también se puede formular en términos de geometría digital . Los posibles bordes de un grafo bipartito se pueden visualizar como los puntos de un rectángulo en la red de enteros , y un subgrafo completo es un conjunto de filas y columnas en este rectángulo en el que están presentes todos los puntos. Por lo tanto, denota el número máximo de puntos que se pueden colocar dentro de una cuadrícula de tal manera que ningún subconjunto de filas y columnas forme una cuadrícula completa. ^[4] Una definición alternativa y equivalente es que es el entero más pequeño tal que cada (0,1)-matriz de tamaño con unos debe tener un conjunto de filas y columnas tales que la submatriz correspondiente esté formada solo por 1s . ${\displaystyle G=(U\cup V,E)}$ ${\displaystyle |U|\times |V|}$ ${\displaystyle z(m,n;s,t)}$ ${\displaystyle m\times n}$ ${\displaystyle s\times t}$ ${\displaystyle z(m,n;s,t)}$ ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle k+1}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\times t}$

Ejemplos

Un gráfico bipartito con 4 vértices en cada lado, 13 aristas y ningún subgrafo, y un conjunto equivalente de 13 puntos en una cuadrícula de 4 × 4, que muestra que . ${\displaystyle K_{3,3}}$ ${\displaystyle z(4;3)\geq 13}$

El número pide el número máximo de aristas en un grafo bipartito con vértices en cada lado que no tiene 4-ciclos (su circunferencia es de seis o más). Por lo tanto, (logrado por un camino de tres aristas), y (un hexágono ). ${\displaystyle z(n;2)}$ ${\displaystyle n}$ ${\displaystyle z(2;2)=3}$ ${\displaystyle z(3;2)=6}$

En su formulación original del problema, Zarankiewicz pidió los valores de para . Las respuestas fueron proporcionadas poco después por Wacław Sierpiński : , , y . ^[4] El caso de es relativamente simple: un grafo bipartito de 13 aristas con cuatro vértices en cada lado de la bipartición, y ningún subgrafo, puede obtenerse añadiendo una de las diagonales largas al grafo de un cubo . En la otra dirección, si un grafo bipartito con 14 aristas tiene cuatro vértices en cada lado, entonces dos vértices en cada lado deben tener grado cuatro. Eliminar estos cuatro vértices y sus 12 aristas incidentes deja un conjunto no vacío de aristas, cualquiera de las cuales junto con los cuatro vértices eliminados forma un subgrafo. ${\displaystyle z(n;3)}$ ${\displaystyle n=4,5,6}$ ${\displaystyle z(4;3)=13}$ ${\displaystyle z(5;3)=20}$ ${\displaystyle z(6;3)=26}$ ${\displaystyle z(4;3)}$ ${\displaystyle K_{3,3}}$ ${\displaystyle K_{3,3}}$

Límites superiores

El teorema de Kővári-Sós-Turán proporciona un límite superior a la solución del problema de Zarankiewicz. Fue establecido por Tamás Kővári, Vera T. Sós y Pál Turán poco después de que se planteara el problema:

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

Kővári, Sós y Turán demostraron originalmente esta desigualdad para . ^[5] Poco después, Hyltén-Cavallius observó que esencialmente se puede utilizar el mismo argumento para demostrar la desigualdad anterior. ^[6] Štefan Znám dio una mejora en el segundo término del límite superior de : ^[7] ${\displaystyle z(n;t)}$ ${\displaystyle z(n;t)}$

${\displaystyle z(n;t)<(t-1)^{1/t}n^{2-1/t}+{\frac {1}{2}}(t-1)n+1.}$

Si se supone que y son constantes, entonces asintóticamente, utilizando la notación O grande , estas fórmulas se pueden expresar como ${\displaystyle s}$ ${\displaystyle t}$

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

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

En el caso particular , suponiendo sin pérdida de generalidad que , tenemos el límite superior asintótico ${\displaystyle m=n}$ ${\displaystyle s\leq t}$

${\displaystyle z(n,n;s,t)=O(n^{2-1/s}).}$

Límites inferiores

Se puede verificar que entre los dos límites superiores asintóticos de en la sección anterior, el primer límite es mejor cuando , y el segundo límite se vuelve mejor cuando . Por lo tanto, si se puede mostrar un límite inferior para que coincida con el límite superior hasta una constante, entonces mediante un argumento de muestreo simple (ya sea en un gráfico bipartito o en un gráfico bipartito que alcance el número máximo de aristas), podemos mostrar que para todos , uno de los dos límites superiores anteriores es ajustado hasta una constante. Esto lleva a la siguiente pregunta: ¿es el caso de que para cualquier fijo y , tenemos ${\displaystyle z(m,n;s,t)}$ ${\displaystyle m=o(n^{s/t})}$ ${\displaystyle m=\omega (n^{s/t})}$ ${\displaystyle z(n^{s/t},n;s,t)}$ ${\displaystyle n^{t/s}\times t}$ ${\displaystyle m\times m^{s/t}}$ ${\displaystyle m,n}$ ${\displaystyle s\leq t}$ ${\displaystyle m\leq n^{s/t}}$

${\displaystyle z(m,n;s,t)=\Omega (mn^{1-1/s})}$? ^[8]

En el caso especial , hasta factores constantes, tiene el mismo orden que , el número máximo de aristas en un grafo -vértice (no necesariamente bipartito) que no tiene como subgrafo. En una dirección, un grafo bipartito con vértices en cada lado y aristas debe tener un subgrafo con vértices y al menos aristas; esto se puede ver al elegir vértices uniformemente al azar de cada lado y tomar la expectativa. En la otra dirección, podemos transformar un grafo con vértices y ninguna copia de en un grafo bipartito con vértices en cada lado de su bipartición, el doble de aristas y todavía ninguna copia de , tomando su doble cobertura bipartita . ^[9] Igual que arriba, con la convención de que , se ha conjeturado que ${\displaystyle m=n}$ ${\displaystyle z(n,n;s,t)}$ ${\displaystyle {\text{ex}}(n,K_{s,t})}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle n}$ ${\displaystyle z(n,n;s,t)}$ ${\displaystyle n}$ ${\displaystyle z(n,n;s,t)/4}$ ${\displaystyle n/2}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle n}$ ${\displaystyle K_{s,t}}$ ${\displaystyle s\leq t}$

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

para todos los valores constantes de . ^[10] ${\displaystyle s,t}$

Para algunos valores específicos de (por ejemplo, para valores suficientemente mayores que , o para ), las afirmaciones anteriores se han demostrado utilizando varias construcciones algebraicas y algebraicas aleatorias. Al mismo tiempo, la respuesta a la pregunta general aún nos resulta desconocida. ${\displaystyle s,t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s=2}$

Gráficas de incidencia en geometría finita

El gráfico de Levi del plano de Fano da lugar al gráfico de Heawood , un gráfico bipartito con siete vértices en cada lado, 21 aristas y ningún 4-ciclo.

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

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

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

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

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

Gráficas normativas y gráficas normativas proyectivas

Para valores suficientemente mayores que , la conjetura anterior fue verificada 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. ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/s})}$

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

${\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 grafo tiene vértices y al menos aristas. Para ver que este grafo es libre de vértices, observe que cualquier vecino común de vértices debe satisfacer ${\displaystyle p^{s}}$ ${\displaystyle p^{2s-1}/2}$ ${\displaystyle K_{s,s!+1}}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle y_{1},\ldots ,y_{s}\in \mathbb {F} _{p^{s}}}$

${\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}})}$

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

El mismo resultado se puede demostrar para todos 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 sobre el conjunto de vértices , tal que dos vértices son adyacentes si y solo si , donde es el mapa de norma definido por . Mediante un argumento similar al anterior, se puede verificar que es un grafo libre de aristas. ${\displaystyle t>(s-1)!}$ ${\displaystyle \mathbb {F} _{p^{s-1}}\times \mathbb {F} _{p}^{\times }}$ ${\displaystyle (X,x),(Y,y)}$ ${\displaystyle N(X+Y)=xy}$ ${\displaystyle N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}}$ ${\displaystyle N(x)=x^{(p^{s}-1)/(p-1)}}$ ${\displaystyle K_{s,t}}$ ${\displaystyle \Omega (n^{2-1/s})}$

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

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

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

Particiones de camarilla

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

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

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

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

Construcciones algebraicas aleatorias

^{Blagojević, Bukh y Karasev [18]} y Bukh ^[19] también dieron pruebas alternativas de para suficientemente mayores que utilizando el método de construcciones algebraicas aleatorias. La idea básica es tomar un polinomio aleatorio y considerar el grafo entre dos copias de cuyos bordes son todos aquellos pares tales que . ${\displaystyle {\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle f:\mathbb {F} _{q}^{s}\times \mathbb {F} _{q}^{s}\rightarrow \mathbb {F} _{q}}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle (x,y)}$ ${\displaystyle f(x,y)=0}$

Para empezar, sea una potencia prima y . Sea ${\displaystyle q}$ ${\displaystyle n=q^{2}}$

${\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 en , grado como máximo en , y además satisfactorio para todo . Sea el grafo aleatorio asociado en el conjunto de vértices , tal que dos vértices y son adyacentes si y solo si . ${\displaystyle s^{2}}$ ${\displaystyle X=(x_{1},\dots ,x_{s})}$ ${\displaystyle s^{2}}$ ${\displaystyle Y=(y_{1},\dots ,y_{s})}$ ${\displaystyle f(X,Y)=f(Y,X)}$ ${\displaystyle X,Y}$ ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x,y)=0}$

Para demostrar el límite inferior asintótico, basta con mostrar que el número esperado de aristas en es . Para cada subconjunto , denotamos el subconjunto de vértices de que "se desvanece en ": ${\displaystyle G}$ ${\displaystyle \Omega (q^{2s-1})}$ ${\displaystyle s}$ ${\displaystyle U\subset \mathbb {F} _{q}^{s}}$ ${\displaystyle Z_{U}}$ ${\displaystyle \mathbb {F} _{q}^{s}\setminus U}$ ${\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\}}$.

Usando el límite de Lang-Weil para polinomios en , podemos deducir que siempre se tiene o para alguna constante grande , lo que implica ${\displaystyle f(\cdot ,u)}$ ${\displaystyle \mathbb {F} _{q}^{s}}$ ${\displaystyle Z_{U}\leq C}$ ${\displaystyle Z_{U}>q/2}$ ${\displaystyle C}$

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

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

Aplicaciones

El teorema de Kővári–Sós–Turán se ha utilizado en geometría discreta para limitar el número de incidencias entre objetos geométricos de varios tipos. Como ejemplo simple, un conjunto de puntos y líneas en el plano euclidiano no tiene necesariamente , por lo que por el teorema de Kővári–Sós–Turán tiene incidencias punto-línea. Este límite es estricto cuando es mucho mayor que , pero no cuando y son casi iguales, en cuyo caso el teorema de Szemerédi–Trotter proporciona un límite más estricto. Sin embargo, el teorema de Szemerédi–Trotter puede demostrarse dividiendo los puntos y líneas en subconjuntos para los que el límite de Kővári–Sós–Turán es estricto. ^[21] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle K_{2,2}}$ ${\displaystyle O(nm^{1/2}+m)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(n^{2/3}m^{2/3}+n+m)}$

Véase también

• Grafos libres de bicliques , grafos dispersos cuya escasez está controlada por la solución del problema de Zarankiewicz
• Problema del subgrafo prohibido , una generalización no bipartita del problema de Zarankiewicz
• Caracterización de gráficos prohibidos , familias de gráficos definidas por subgráficos prohibidos de varios tipos
• Teorema de Turán , un límite en el número de aristas de un grafo con un subgrafo completo prohibido

Referencias

1. Bollobás, Béla (2004), "VI.2 Subgrafos completos de grafos r -partitos", Teoría de grafos extremos , Mineola, NY: Dover Publications Inc., págs. 309–326, MR  2078877. Reimpresión de la edición de 1978 de Academic Press, MR 0506522.
2. Zarankiewicz, K. (1951), "Problema P 101", Colloq. Matemáticas. , 2 : 301. Como lo cita Bollobás (2004).
3. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 4 de marzo de 2016. Consultado el 16 de septiembre de 2014 .{{cite web}}: CS1 maint: archived copy as title (link)
4. Sierpiński, W. (1951), "Sur un problème concernant un reseau à 36 puntos", Ann. Soc. Polon. Matemáticas. , 24 : 173–174, SEÑOR  0059876.
5. Kővári, T.; T. Sós, V .; Turán, P. (1954), “Sobre un problema de K. Zarankiewicz” (PDF) , Coloquio Matemáticas. , 3 : 50–57, doi : 10,4064/cm-3-1-50-57 , SEÑOR  0065617.
6. Hyltén-Cavallius, C. (1958), "Sobre un problema combinatorio", Colloquium Mathematicum , 6 : 59–65, doi : 10.4064/cm-6-1-61-65 , MR  0103158. Como lo cita Bollobás (2004).
7. Znám, Š. (1963), "Sobre un problema combinatorio de K. Zarankiewicz", Colloquium Mathematicum , 11 : 81–84, doi : 10.4064/cm-11-1-81-84 , MR  0162733. Como lo cita Bollobás (2004).
8. Conlon, David (2021), "Algunas observaciones sobre el problema de Zarankiewicz", Mathematical Proceedings of the Cambridge Philosophical Society , 173 : 155–161, arXiv : 2007.12816 , doi :10.1017/S0305004121000475, S2CID  220793154.
9. Bollobás (2004), Teorema 2.3, p. 310.
10. Bollobás (2004), Conjetura 15, p. 312.
11. Reiman, I. (1958), "Über ein Problem von K. Zarankiewicz", Acta Mathematica Academiae Scientiarum Hungaricae , 9 (3–4): 269–273, doi :10.1007/bf02020254, MR  0101250, S2CID  121692172.
12. Bollobás (2004), Corolario 2.7, p. 313.
13. Brown, WG (1966), "Sobre gráficos que no contienen un gráfico de Thomsen", Canadian Mathematical Bulletin , 9 (3): 281–285, doi : 10.4153/CMB-1966-036-2 , MR  0200182, S2CID  121306253.
14. Füredi, Zoltán (1996), "Nuevas asintóticas para números bipartitos de Turán", Journal of Combinatorial Theory , Serie A, 75 (1): 141–144, doi : 10.1006/jcta.1996.0067 , MR  1395763.
15. Kollár, János; Rónyai, Lajos; Szabó, Tibor (1996), "Gráficos normativos y números de Turán bipartitos", Combinatorica , 16 (3): 399–406, doi :10.1007/BF01261323, MR  1417348, S2CID  26363618.
16. Alon, Noga ; Rónyai, Lajos; Szabó, Tibor (1999), "Gráficos de normas: variaciones y aplicaciones", Journal of Combinatorial Theory , Serie B, 76 (2): 280–290, doi : 10.1006/jctb.1999.1906 , MR  1699238.
17. Alón, Noga ; Mellinger, Keith E.; Mubayi, Dhruv; Verstraëte, Jacques (2012), "El teorema de Bruijn-Erdős para hipergrafos", Des. Códigos Criptogr. , 65 (3): 233–245, arXiv : 1007.4150 , doi : 10.1007/s10623-011-9555-4, S2CID  15064936.
18. Blagojević, Pavle; Bukh, Boris; Karasev, Roman (2013), "Números de Turán para grafos libres de K _s,t : obstrucciones topológicas y construcciones algebraicas", Israel Journal of Mathematics , 197 : 199–214, arXiv : 1108.5254 , doi : 10.1007/s11856-012-0184-z.
19. Bukh, Boris (2015), "Construcción algebraica aleatoria de grafos extremos", Bull. London Math. Soc. , 47 : 939–945, arXiv : 1409.3856.
20. Bukh, Boris (2021), Gráficos extremos sin biclíneos exponencialmente pequeños , arXiv : 2107.04167.
21. Matoušek, Jiří (2002), Lecciones sobre geometría discreta , Textos de posgrado en matemáticas, vol. 212, Nueva York: Springer-Verlag, págs. 65-68, doi :10.1007/978-1-4613-0039-7, ISBN 0-387-95373-6, Sr.  1899299.