Combinatoria extrema y aditiva

Si buscamos el máximo de aristas sin triángulos, un dibujo con muchas aristas demuestra que ese tamaño se puede alcanzar. Para demostrar que es el máximo hace falta además que ningún grafo permitido pueda tener más.

Trabajamos con grafos finitos simples no dirigidos. Un triángulo son tres vértices unidos por sus tres parejas. Prohibirlo permite otros ciclos, por ejemplo de longitud cuatro. Permitir aristas repetidas cambiaría el problema y sus cotas.

El teorema de Mantel afirma que un grafo simple sin triángulos con n vértices tiene como máximo ⌊n²/4⌋ aristas. La construcción que alcanza ese valor divide los vértices en dos partes de tamaños ⌊n/2⌋ y ⌈n/2⌉ y conecta todas las parejas entre partes.

No se conectan parejas dentro de una parte. Cada arista cambia de parte; después de tres cambios no podemos volver a la parte inicial. Por tanto no hay triángulos. Los cruces de líneas del dibujo no añaden vértices.

Si uv es arista y no hay triángulos, N(u) y N(v) son disjuntos: un vecino común cerraría uno.

Al sumar por todas las aristas, cada d(v) aparece d(v) veces, de modo que Σd(v)²≤nm.

Cauchy–Schwarz da .

Como m es entero, se toma el suelo. Si m=0, la cota se cumple directamente; no se divide por cero.

Un bipartito completo con partes a y n−a tiene a(n−a) aristas.

Completar el cuadrado da .

Se maximiza eligiendo a tan próximo como sea posible a n/2.

Turán generaliza la idea: al prohibir K_{r+1}, la construcción extrema es un grafo completo r-partito con partes equilibradas. Con r≥3 se permiten triángulos entre tres partes distintas. Cambia la configuración prohibida y no se reutiliza la cota n²/4 como si fuera universal.

Hay |A||B| parejas ordenadas con un elemento de cada conjunto, pero varias pueden dar el mismo resultado. Un conjunto elimina las repeticiones.

La cota superior cuenta parejas. Para la inferior ordenamos A y B y usamos una cadena estrictamente creciente: a₁+b₁<…<+b₁<+b₂<…<+. Contiene r+s−1 sumas distintas.

Por tanto hay 2m+1 resultados, frente a (m+1)² parejas.

Una progresión de r términos con paso no nulo en los enteros también tiene 2r−1 sumas distintas consigo misma. Traslación y cambio de paso mantienen ese recuento. Tener crecimiento pequeño sugiere estructura, pero no significa que todo conjunto sea literalmente un intervalo de enteros consecutivos.

La prueba de la cadena usa el orden de los enteros compatible con suma.

Por eso la cota 2|H|−1 no puede imponerse allí de forma general.

En ℤ/pℤ, con p primo, Cauchy–Davenport afirma |A+B|≥min(p,|A|+|B|−1) para A y B no vacíos. El mínimo respeta el tamaño del grupo y la primalidad excluye los subgrupos propios no triviales que pueden impedir el crecimiento. Se trata de un teorema adicional; la cadena ordenada no es su prueba modular.

Entonces .

La energía cuenta cuádruplas ordenadas con a+b=c+d: para cada s se puede elegir una pareja de r(s) formas y la otra también.

Cauchy–Schwarz da , así que E(A)≥|A|⁴/|A+A|. Un conjunto suma pequeño obliga a muchas colisiones. E(A) no es una probabilidad ni solo el número de sumas repetidas.

En problemas extremos se combina un límite superior con una construcción. En conjuntos suma, una cota inferior demuestra crecimiento mínimo; una energía grande indica colisiones, pero por sí sola no determina exactamente la forma del conjunto.

Resultados estructurales más profundos, como los de tipo Freiman, requieren enunciar sus condiciones y la conclusión precisa sobre progresiones generalizadas. Los recuentos elementales anteriores no autorizan a clasificar cualquier conjunto solo por una razón de duplicación.