Una prueba meramente algebraica del lema de Sauer-Shelah-Perles

Abstract

The objective of this memory is to give a purely algebraic proof of the Sauer- Shelah-Perles Lemma (inspired by the elegant proof in [FrPa,1983]), based only in duality in the Q−algebra Q[Vn] of polynomial functions de_ned on the zero-dimensional algebraic variety of subsets of the set [n] := {1, 2, . . . , n}. In fact, two di_erent proofs of this lemma will be given. Furthermore, we prove how several other classical results from Combinatorics are particular examples of a Trace (Inversion) Formula in _nite Q−algebras. For instance, one of this results is the general form of the Inclusion-Exclusion Principle (both with direct and reverse order associated to subsets inclusion). This approach also allows us to show a basis of the space of null t−designs, which di_ers from the one described in Theorem 4 of [DeFr,1982]. All results are still true if we replace Q[Vn] by K[Vn], where K is a perfect _eld of characteristic di_erent from 2. This memory has then the underlying purpose of connecting two _elds of mathematical knowledge that are not usually connected, at least not in this form.

El objetivo de esta memoria es dar una demostración puramente algebraica del Lema de Sauer-Shelah-Perles (inspirada en la elegante demostración que aparece en [FrPa,1983]), basada únicamente en técnicas de dualidad en la Q−álgebra Q[Vn] de funciones polinomiales definidas en la variedad algebraica cero-dimensional de subconjuntos del conjunto [n] := {1, 2, . . . , n}. De hecho, se darán dos demostraciones distintas de este lema. Además, demostramos cómo algunos otros resultados clásicos de la combinatoria son ejemplos particulares de una Fórmula (de Inversión) de la Traza en Q−álgebras finitas. Por ejemplo, uno de estos resultados es la forma general del Principio de Inclusión-exclusión (considerando tanto el orden usual como el orden reverso asociado a la inclusión de subconjuntos). Este enfoque también nos permite presentar una base del espacio de null t−designs, que difiere de la proporcionada en el Teorema 4 de [DeFr,1982]. Todos los resultados siguen siendo ciertos si reemplazamos Q[Vn] por K[Vn], donde K es un cuerpo perfecto de característica distinta de 2. Así, esta memoria tiene el propósito subyacente de conectar dos campos del conocimiento matemático que no suelen estarlo, al menos no de la forma aquí presentada.