En el campo matemático de la geometría combinatoria , el problema de Littlewood-Offord es el problema de determinar el número de subsumas de un conjunto de vectores que caen en un conjunto convexo dado . Más formalmente, si V es un espacio vectorial de dimensión d , el problema es determinar, dado un subconjunto finito de vectores de S y una convexa subconjunto A , el número de subconjuntos de S cuya suma está en A .
El primer límite superior de este problema fue probado (para d = 1 yd = 2) en 1938 por John Edensor Littlewood y A. Cyril Offord . [1] Este lema de Littlewood-Offord establece que si S es un conjunto de n números reales o complejos de valor absoluto al menos uno y A es cualquier disco de radio uno, entonces no más dede los 2 n posibles subsumas de S caen en el disco.
En 1945 Paul Erdős mejoró el límite superior para d = 1 a
utilizando el teorema de Sperner . [2] Este límite es agudo; la igualdad se logra cuando todos los vectores en S son iguales. En 1966, Kleitman demostró que el mismo límite se aplicaba a los números complejos. En 1970, extendió esto al escenario en el que V es un espacio normado . [2]
Suponga que S = { v 1 ,…, v n }. Restando
de cada subsuma posible (es decir, cambiando el origen y luego escalando por un factor de 2), el problema de Littlewood-Offord es equivalente al problema de determinar el número de sumas de la forma
que caen en el conjunto objetivo A , dondetoma el valor 1 o -1. Esto hace que el problema sea probabilístico , en el que la cuestión es la distribución de estos vectores aleatorios y qué se puede decir sin saber nada más sobre la v i .
Referencias
- ^ Littlewood, JE; Offord, AC (1943). "Sobre el número de raíces reales de una ecuación algebraica aleatoria (III)". Rec. Matemáticas. (Mat. Sbornik) . Nouvelle Série. 12 (54): 277–286.
- ^ a b Bollobás, Béla (1986). Combinatoria . Cambridge. ISBN 0-521-33703-8.