Propiedad B

En matemáticas , la propiedad B es una determinada propiedad de la teoría de conjuntos . Formalmente, dado un conjunto finito X , una colección C de subconjuntos de X tiene la propiedad B si podemos dividir X en dos subconjuntos disjuntos Y y Z de manera que cada conjunto en C cumpla con Y y Z.

La propiedad recibe su nombre del matemático Felix Bernstein , quien presentó la propiedad por primera vez en 1908. ^[1]

La propiedad B es equivalente a 2-colorear el hipergrafo descrito por la colección C . Un hipergrafo con la propiedad B también se llama 2-coloreable . ^[2]^{: 468} A veces también se le llama bipartito , por analogía con los grafos bipartitos . La propiedad B se estudia a menudo para hipergrafos uniformes (sistemas de conjuntos en los que todos los subconjuntos del sistema tienen la misma cardinalidad) pero también se ha considerado en el caso no uniforme. ^[3]

El problema de comprobar si un conjunto C tiene la propiedad B se denomina problema de división de conjuntos .

Conjunto más pequeño de familias sin propiedad B

El número más pequeño de conjuntos en una colección de conjuntos de tamaño n tales que C no tiene la propiedad B se denota por m ( n ).

Valores conocidos de m(n)

Se sabe que m (1) = 1, m (2) = 3 y m (3) = 7 (como se puede ver en los siguientes ejemplos); el valor de m (4) = 23 (Östergård), aunque encontrar este resultado fue el resultado de una búsqueda exhaustiva. Se ha demostrado un límite superior de 23 (Seymour, Toft) y un límite inferior de 21 (Manning). Al momento de escribir este artículo (marzo de 2017), aún no hay una entrada OEIS para la secuencia m ( n ), debido a la falta de términos conocidos.

m (1): Para n = 1, se establece X = {1} y C = {{1}}. Entonces C no tiene la propiedad B.

m (2): Para n = 2, se hace X = {1, 2, 3} y C = {{1, 2}, {1, 3}, {2, 3}} (un triángulo). Entonces C no tiene la propiedad B, por lo que m (2) <= 3. Sin embargo, C ' = {{1, 2}, {1, 3}} sí la tiene (se hace Y = {1} y Z = {2, 3}), por lo que m (2) >= 3.

m (3): Para n = 3, el conjunto X = {1, 2, 3, 4, 5, 6, 7}, y C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} (el sistema triple de Steiner S ₇ ); C no tiene la Propiedad B (por lo que m (3) <= 7), pero si se omite algún elemento de C , entonces ese elemento puede tomarse como Y , y el conjunto de elementos restantes C ' tendrá la Propiedad B (por lo que para este caso particular, m (3) >= 7). Se pueden comprobar todas las demás colecciones de 6 3-conjuntos para ver que todos tienen la Propiedad B.

m (4): Östergård (2014) a través de una búsqueda exhaustiva encontró m (4) = 23. Seymour (1974) construyó un hipergrafo en 11 vértices con 23 aristas sin la Propiedad B, lo que muestra que m (4) <= 23. Manning (1995) redujo el piso de tal manera que m (4) >= 21.

Asintótica demetro(norte)

Erdős (1963) demostró que para cualquier colección de menos de conjuntos de tamaño n , existe una coloración bicromática en la que todos los conjuntos son bicromáticos. La prueba es sencilla: considere una coloración aleatoria. La probabilidad de que un conjunto arbitrario sea monocromático es . Por un límite de unión , la probabilidad de que exista un conjunto monocromático es menor que . Por lo tanto, existe una buena coloración. $Estilo de visualización 2^{n-1}}$ $Estilo de visualización 2^{-n+1}}$ $Estilo de visualización 2^{n-1}2^{-n+1}=1}$

Erdős (1964) demostró la existencia de un hipergrafo n -uniforme con hiperaristas que no tiene la propiedad B (es decir, no tiene una 2-coloración en la que todas las hiperaristas sean bicromáticas), estableciendo un límite superior. $O(2^{n}\cdot n^{2})$

Schmidt (1963) demostró que cada colección de conjuntos de tamaño n como máximo tiene la propiedad B. Erdős y Lovász conjeturaron que . En 1978, Beck mejoró el límite inferior a , donde es un número positivo arbitrario pequeño. En 2000, Radhakrishnan y Srinivasan mejoraron el límite inferior a . Utilizaron un algoritmo probabilístico inteligente. $Estilo de visualización n/(n+4)\cdot 2^{n}}$ $m(n)=\theta (2^{n}\cdot n)$ $m(n)=\Omega (n^{1/3-\epsilon }2^{n})$ $\épsilon$ $m(n)=\Omega (2^{n}\cdot {\sqrt {n/\log n}})$

Véase también

Referencias

^ Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber. , 60 : 325–328.
^ Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr. 0859549
^ Beck, J. (1978), "Sobre hipergrafos 3-cromáticos", Discrete Mathematics , 24 (2): 127–137, doi : 10.1016/0012-365X(78)90191-7 , MR 0522920

Lectura adicional

Erdős, Paul (1963), "Sobre un problema combinatorio", Nordisk Mat. Tidskr. , 11 : 5-10
Erdős, P. (1964). "Sobre un problema combinatorio. II". Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 445–447. doi : 10.1007/BF01897152 .
Schmidt, WM (1964). "Ein kombinatorisches Problem von P. Erdős und A. Hajnal". Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 373–374. doi : 10.1007/BF01897145 .
Seymour, Paul (1974), "Una nota sobre un problema combinatorio de Erdős y Hajnal", Boletín de la Sociedad Matemática de Londres , 8 (4): 681–682, doi :10.1112/jlms/s2-8.4.681.
Toft, Bjarne (1975), "Sobre hipergrafías de color crítico", en Hajnal, A. ; Rado, Richard ; Sós, Vera T. (eds.), Conjuntos infinitos y finitos: a Paul Erdös en su 60.º cumpleaños , North Holland Publishing Co., págs. 1445–1457.
Manning, GM (1995), "Algunos resultados sobre el problema m (4) de Erdős y Hajnal", Anuncios electrónicos de investigación de la American Mathematical Society , 1 (3): 112–113, doi : 10.1090/S1079-6762-95-03004-6.
Beck, J. (1978), "Sobre hipergrafos 3-cromáticos", Discrete Mathematics , 24 (2): 127–137, doi : 10.1016/0012-365X(78)90191-7.
Radhakrishnan, J.; Srinivasan, A. (2000), "Límites y algoritmos mejorados para la coloración de hipergrafos 2", Random Structures and Algorithms , 16 (1): 4–32, doi :10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2.
Miller, EW (1937), "Sobre una propiedad de familias de conjuntos", Comp. Rend. Varsovie , 30 : 31–38.
Erdős, P .; Hajnal, A. (1961), "Sobre una propiedad de familias de conjuntos", Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 87–123, doi : 10.1007/BF02066676.
Abbott, HL; Hanson, D. (1969), "Sobre un problema combinatorio de Erdös", Canadian Mathematical Bulletin , 12 (6): 823–829, doi : 10.4153/CMB-1969-107-x
Östergård, Patric RJ (30 de enero de 2014). "Sobre el tamaño mínimo de hipergrafos 4-uniformes sin la propiedad B". Matemáticas Aplicadas Discretas . 163, Parte 2: 199–204. doi : 10.1016/j.dam.2011.11.035 .