Número de conjuntos 3 distintos formados como subconjuntos de una familia de conjuntos 4 uniformes

Question

Dejemos que $\mathcal{F} \subseteq \binom{[n]}{4}$ sea una colección de subconjuntos de tamaño 4 de $\{1,\ldots,n\}$ , es decir, una familia de conjuntos 4uniformes.

Dejemos que $\mathcal{F'}$ sea la colección de conjuntos de tamaño 3 para los que un superconjunto está contenido en $\mathcal{F}$ es decir, $$\mathcal{F'} := \{ S \subseteq [n] \colon |S|=3 \wedge \exists T \in \mathcal{F}: S \subseteq T \}.$$

¿Podemos dar un límite inferior asintótico para $|\mathcal{F'}|$ en términos de $|\mathcal{F}|$ ?

Si $\mathcal{F}$ contiene todos los tamaños $4$ subconjuntos de $[n]$ entonces $\mathcal{F'}$ contiene todos los tamaños $3$ subconjuntos de $[n]$ para que $|\mathcal{F}| = \binom{n}{4}$ y $|\mathcal{F'}| = \binom{n}{3}$ , dando $|\mathcal{F'}| \in \mathcal{\Omega}(|\mathcal{F}|^{3/4})$ . Espero que esto se mantenga en general. ¿Puede alguien indicarme la dirección correcta?

Answer 1

Los habituales término técnico dentro de la teoría de los hipergrafos para el conjunto $\mathcal{F}'$ en el OP es sombra (inferior) de $\mathcal{F}$ . Véase, por ejemplo, [Béla Bollobás: Combinatoria: Sistemas de conjuntos, hipergrafías, familias de vectores y probabilidad combinatoria . Cambridge University Press, 1986 ISBN 9780521337038; página 23].

A continuación, para facilitar el debate sobre (lb0) la notación $\mathcal{F}'$ no se utilizará, sino que usaré la notación más larga pero más explicativa

$\mathcal{F}' = \mathrm{Shad}_3(\mathcal{F})$

donde el lado derecho es justo lo que se define en el OP (y también se define a continuación). Como indica el índice inferior "3", esta noción puede, por supuesto, definirse de forma más general, de manera análoga. (notación)

También me tomo la libertad de utilizar $n=\{0,1,\dotsc,n-1\}$ en lugar de la del PO $[n]=\{1,\dotsc,n\}$ como el conjunto de la tierra. En particular,

Escribo $\binom{n}{k}$ para el conjunto de $k$ -subconjuntos de elementos de $n$ .

Un respuesta a su pregunta se puede obtener de un teorema de Kruskal y Katona. Para cualquier $0\leq k\leq n$ dejar $\prec$ denotan el orden lineal en $\binom{n}{k}$ definido por (alternativa) (colex)

$ A\prec B $ si y sólo si $\max( A\setminus B) < \max( B\setminus A)$ .

(Aquí, $\max$ denota el máximo habitual con respecto al orden lineal natural en $\omega$ .)

Para cualquier $k,l\in\omega$ , dejemos que $\mathrm{Init}_\prec(k,l)$ denotan el segmento inicial del orden lineal $(\binom{n}{k},\prec)$ que consiste en la primera $l$ elementos del orden lineal. (longitud)

Para cualquier hipergrafo $\mathcal{H}\subseteq 2^{n}$ dejar (plazo)

$\mathrm{Shad}_3(\mathcal{H}):=\{ S\subseteq n\colon \lvert S\rvert=3,\quad \exists e\in\mathcal{H},\ \ S\subseteq e\}$ .

Gyula O. H. Katona y Joseph Kruskal independientemente demostraron afirmaciones más generales que en particular implican que

$\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert\geq\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))\rvert\qquad$ para todos $n\in\omega$ y todos $\mathcal{F}\subseteq\binom{n}{4}$ ${}\hspace{22pt}$ (lb0)

Este es un límite inferior para $\lvert\mathcal{F}'\rvert=\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert$ Una prueba de lo que se pedía en el PO, en términos de $\lvert\mathcal{F}\rvert$ mientras que el límite es difícil de utilizar debido a la difícil función $m\mapsto \lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert$ .

En particular, el límite inferior no depende del estructura del hipergrafo $\mathcal{F}$ , sólo en su tamaño $\lvert\mathcal{F}\rvert$ . En cierto sentido, esto es mejor que el límite "asintótico" solicitado, ya que se mantiene para todo $n$ En otro sentido, es peor que lo que se pedía (porque carece de la transparencia informativa de una declaración como la expectativa del PO). $\Omega(\lvert\mathcal{F}\rvert^{\frac34})$ pero véase más adelante, donde también se proporciona).

Aunque pueda parecer insatisfactorio que el límite inferior de $\lvert\mathrm{Shad}_3(\cdot)\rvert$ en (lb0) es de nuevo en términos de esa misma función; sin embargo, el argumento de esa función en el límite inferior es uno específico hipergrafo explícito, a saber: $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))$ en el que $\mathcal{F}$ entra sólo por su tamaño, no por su estructura.

El hipergrafo $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ puede calcularse eficazmente para cada $m\in\omega$ y, sobre todo, el el conjunto de tierra utilizado es irrelevante siempre y cuando tenga al menos $4m$ elementos. Al tabular estos hipergráficos específicos, es importante señalar (absoluto) que esencialmente no hay ninguna dependencia de $n$ en el sentido de que los segmentos iniciales del orden colexicográfico no cambian con el aumento de $n$ , de modo que para tabular los hipergráficos $\mathrm{Init}_\prec(4,m)$ , $m\in\omega$ se puede suponer que el conjunto de tierra es $\omega$ y, por tanto, los hipergrafos $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ son ' datos unidimensionales ', es decir, una secuencia contable de hipergrafos 4uniformes.

Los primeros treinta y cinco términos del orden lineal $\prec$ en el suelo $\omega$ son

$0, 1, 2, 3$

$\prec$

$0, 1, 2, 4$

$\prec$

$0, 1, 3, 4$

$\prec$

$0, 2, 3, 4$

$\prec$

$1, 2, 3, 4$

$\prec$

$0, 1, 2, 5$

$\prec$

$0, 1, 3, 5$

$\prec$

$0, 2, 3, 5$

$\prec$

$1, 2, 3, 5$

$\prec$

$0, 1, 4, 5$

$\prec$

$0, 2, 4, 5$

$\prec$

$1, 2, 4, 5$

$\prec$

$0, 3, 4, 5$

$\prec$

$1, 3, 4, 5$

$\prec$

$2, 3, 4, 5$

$\prec$

$0, 1, 2, 6$

$\prec$

$0, 1, 3, 6$

$\prec$

$0, 2, 3, 6$

$\prec$

$1, 2, 3, 6$

$\prec$

$0, 1, 4, 6$

$\prec$

$0, 2, 4, 6$

$\prec$

$1, 2, 4, 6$

$\prec$

$0, 3, 4, 6$

$\prec$

$1, 3, 4, 6$

$\prec$

$2, 3, 4, 6$

$\prec$

$0, 1, 5, 6$

$\prec$

$0, 2, 5, 6$

$\prec$

$1, 2, 5, 6$

$\prec$

$0, 3, 5, 6$

$\prec$

$1, 3, 5, 6$

$\prec$

$2, 3, 5, 6$

$\prec$

$0, 4, 5, 6$

$\prec$

$1, 4, 5, 6$

$\prec$

$2, 4, 5, 6$

$\prec$

$3, 4, 5, 6$

y para todos $1\leq m\leq 35$ el hipergrafo $\mathrm{Init}_\prec(4,m)$ se obtiene recogiendo precisamente el primer $m$ términos en la secuencia anterior. Los hipergráficos $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ para $1\leq m\leq 35$ puede calcularse a partir de esta lista.

Una forma de expresar (lb0) es: el hipergrafo específico $\mathcal{F}:=\mathrm{Init}_\prec(4,m)$ es a hipergrafo de menos tamaño $\lvert F'\rvert$ de la $3$ -entre todos los hipergrafos de 4 uniones con $m$ en el set de tierra $n$ . (Suele ser no el minimizador único).

La función $\lambda\colon m\mapsto\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert$ es conocido como el Función Kruskal--Macaulay y está tabulado en OEIS A123573 , trazado allí como

Título. Esta es su función "límite inferior" en función del aumento de $\lvert\mathcal{F}\rvert$ . El parecido con el a parte de la curva del manjar blanco puede explicarse matemáticamente (cf. [FMRT1995] ).

Existe un resultado similar atribuido a László Lovász, que implica que

$\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert \geq \binom{h(\lvert \mathcal{F} \rvert)}{3}$

donde $h\colon\omega\to\mathbb{R}$ es la función definida por $h(x) := \max\{ \xi\in\mathbb{R}\colon\quad \xi>0, \quad x\geq \binom{\xi}{4} = \frac{\Gamma(\xi+1)}{\Gamma(4+1)\cdot\Gamma(\xi-4+1)} \}$ ${}\hspace{50pt}$ (lb1)

Una prueba de (lb1) puede encontrarse en (la demostración de) el Teorema 10.15 de (índice)

Stasys Jukna, Combinatoria extrema . Segunda edición. Springer 2011. xxiv+412 páginas. ISBN 978-3-642-17363-9

o en

Boriks Bukh, Teorema multidimensional de Kruskal-Katona SIAM J. Discrete Math, vol. 26(2), pp. 548-554, 2012. errata

Trabajar con estos límites no es fácil. Hay una curiosa conexión con la construcción de Takagi de una función continua no diferenciable en ninguna parte. Puedes encontrar más detalles en (las referencias en):

[FMRT1995] Peter Frankl, Makoto Matsumoto, Imre Z. Ruzsa, Norihide Tokushige: Sombras mínimas en hipergrafos uniformes y una generalización de la función Takagi . Revista de Teoría Combinatoria, Serie A 69 , 125-148 (1995)

Sin embargo, su conjetura/expectativa de que

$\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))\rvert \in \Omega(\lvert\mathcal{F}\rvert^{\frac34})$

se puede confirmar fácilmente con la ayuda del límite de Lovász (lb1) . Para ver esto, por brevedad dejemos $x=h(\lvert\mathcal{F}\rvert)$ y (m) $m=\lvert\mathcal{F}\rvert$ . La definición de $h$ en (lb1) implica que $x$ es el único real positivo con

$x^4-6x^3+11x^2-6x-24m=0$ $\hspace{125pt}$ (cuartico)

Esta ecuación cuártica tiene discriminante negativo para todos los casos no triviales $m\in\omega\setminus\{0\}$ por lo que tiene exactamente dos raíces reales, la mayor de las cuales es positiva e igual a

$x = x(m) = \frac12\left(3 + \sqrt{ 5 + 4 \sqrt{1 + 24m} } \right)$ .

El límite inferior en (lb1) por lo tanto es

$\frac{1}{12}\cdot\biggl( 3 + 3\sqrt{1+24m} + \sqrt{5+4\sqrt{1+24m}} + \sqrt{ 5 + 120m + 4(1+24m)^{\frac32} } \biggr)$$ |125pt}$ (lb.explícita)

Es evidente que (lb.explícita) que, como usted esperaba,

$\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert \in \Omega(m^{\frac34})$

La ampliación de Puiseux de $\frac{1}{3!}\cdot x(m)\cdot (x(m)-1) \cdot (x(m)-2)$ en el infinito es

$2(\frac23)^{1/4}\quad m^{\frac34} + (\frac32)^{1/2}\quad m^{\frac12} + \frac{13}{8\cdot 2^{1/4}\cdot 3^{3/4}}\quad m^{\frac14} + \frac14 + \frac{151}{768\cdot 24^{1/4}}\cdot m^{-\frac14} + \frac{1}{16\cdot 6^{1/2}}\cdot m^{-\frac12} + \frac{341}{24576\cdot 54^{1/4}}\cdot m^{-\frac34} + O(m^{-1})$

(No he calculado esto manualmente, lo que en principio sería rutinario, aunque hizo hacer una comprobación numérica con éxito con un valor aleatorio de $m$ .)

Por último, aquí tenemos un gráfico de la función exacta de Kruskal-Macaulay y de (lb.explícita) :

Por cierto, parece que hasta ahora nadie ha probado estimaciones generales de lo bien que está el límite inferior en (lb.explícita) se aproxima a la función Kruskal-Macaulay (por supuesto, es aguda para infinitos valores de $m$ mi punto es que no hay una estimación de lo mal que puede llegar a estar entre estos puntos).

${}$ __________________________

(absoluto) Esta propiedad es fácil de demostrar (un conjunto de 4 a partir de un conjunto básico más grande utilizando uno de los elementos del conjunto básico más grande no puede preceder a ninguno de los conjuntos ya conocidos porque su elemento "grande" diferirá de todo elementos de cualquier conjunto comparado con él, y que ese único elemento por sí mismo sea razón suficiente para clasificar ese 4-conjunto más alto que cualquiera de estos conjuntos). También es ampliamente conocido y a veces se menciona explícitamente en la literatura; por ejemplo, en [Gordon Royle: Enumeración combinatoria: Teoría y práctica . Curso CITS7209 en la Universidad de Australia Occidental 2004; Lecture 2, p. 19] se lee

En particular, dado cualquier $4$ -subconjunto de elementos de $\omega$ se puede calcular eficazmente su rango absoluto en el orden colexicográfico $\prec$ y ese rango es el mismo sin importar el conjunto $X$ con $4\subseteq X\subseteq\omega$ el conjunto de tierra es.

(alternativa) Las definiciones alternativas son

• $A\prec B$ $\Leftrightarrow$ el mayor número de la diferencia simétrica está en $B$

y

• $A\prec B$ $\Leftrightarrow$ si ambos $A$ y $B$ se representan como tuplas $\mathrm{rep}(A)$ y $\mathrm{rep}(B)$ en disminuyendo orden natural, entonces $\mathrm{rep}(A) <^{\mathrm{lexicographic}} \mathrm{rep}(B)$

(colex) Este orden lineal se suele denominar orden colexicográfico . Esto es no el orden obtenido al invertir el orden lexicográfico.

(índice) Curiosamente, el importante teorema de Kruskal-Katona, aunque está cuidadosamente tratado en el libro, es falta en el índice del libro que debería ser subsanado en la tercera edición.

(longitud) Aquí, $l$ es para "longitud", que aquí significa "número de elementos en el segmento, no la longitud teórica del segmento como dígrafo".

(m) La notación $m$ hace honor a la larga tradición de la teoría de grafos de denotar el número de aristas por $m$ .

(notación) Referencia [FMRT1995] escribe $\Delta_3(\cdot)$ en lugar de $\mathrm{Shadow}_3(\cdot)$ que yo evito porque ' $\Delta$ se utiliza para el grado de vértice máximo de un hipergrafo, y además tiene connotaciones de "operadores de diferencia", ninguna de las cuales es una asociación útil aquí.

(plazo) No hace falta decir que estas "sombras" no tienen ninguna relación significativa con la noción de "sombra" en el análisis no estándar. Otro término habitual aunque algo menos relevante, es esqueleto (de un complejo simplicial abstracto). Muy estrictamente hablando, habría que tomar primero el cierre descendente del hipergrafo dado $\mathcal{F}$ antes de poder hablar de su $d$ -esqueleto de dimensiones. Su $\mathcal{F}'$ es el $4$ -esqueleto dimensional de la $5$ -complejo simplicial abstracto de dimensiones $\lfloor\mathcal{F}\rfloor$ , donde $\lfloor\cdot\rfloor$ denota un cierre hacia abajo.