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 particionar X en dos subconjuntos disjuntos Y y Z de tal manera que cada conjunto en C cumple ambos Y y Z .
La propiedad recibe su nombre del matemático Felix Bernstein , quien introdujo la propiedad por primera vez en 1908. [1]
Propiedad B es equivalente a 2-colorear la hypergraph descrito por la colección C . Un hipergráfico 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 gráficos bipartitos . La propiedad B a menudo se estudia para hipergráficos 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 una colección C tiene la propiedad B se denomina problema de división de conjuntos .
Conjunto de familias más pequeñas sin propiedad B
El número más pequeño de conjuntos en una colección de conjuntos de tamaño n tal 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 probado un límite superior de 23 (Seymour, Toft) y un límite inferior de 21 (Manning). En el momento de escribir este artículo (marzo de 2017), todavía no hay una entrada OEIS para la secuencia m ( n ), debido a la falta de términos conocidos.
- m (1)
- Para n = 1, establezca X = {1} y C = {{1}}. Entonces C no tiene la propiedad B.
- m (2)
- Para n = 2, establezca 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 (establezca Y = {1} y Z = {2, 3 }), entonces m (2)> = 3.
- m (3)
- Para n = 3, establezca 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 Steiner S 7 ); C no tiene la propiedad B (entonces m (3) <= 7), pero si se omite cualquier elemento de C , entonces ese elemento puede tomarse como Y , y el conjunto de elementos restantes C 'tendrá la propiedad B (entonces para este caso particular, m (3)> = 7). Se pueden comprobar todas las demás colecciones de 6 conjuntos de 3 para ver que todas tengan la propiedad B.
- m (4)
- Östergård (2014) a través de una búsqueda exhaustiva encontró m (4) = 23. Seymour (1974) construyó un hipergrama en 11 vértices con 23 aristas sin propiedad B, lo que muestra que m (4) <= 23. Manning (1995) redujo el piso tal que m (4)> = 21.
Asintóticas de m ( n )
Erdős (1963) demostró que para cualquier colección de menos de conjuntos de talla n , existe un 2-color en el que todos los conjuntos son bicromáticos. La prueba es simple: 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 tanto, existe una buena coloración.
Erdős (1964) mostró la existencia de un hipergrama n -uniforme con hiperforestas que no tiene la propiedad B (es decir, no tiene una coloración 2 en la que todas las hiperfiladuras son bicromáticas), estableciendo un límite superior.
Schmidt (1963) demostró que cada colección de como máximo conjuntos de tamaño n tiene la propiedad B. Erdős y Lovász conjeturaron que. Beck en 1978 mejoró el límite inferior a, dónde es un pequeño número positivo arbitrario. En 2000, Radhakrishnan y Srinivasan mejoraron el límite inferior a. Utilizaron un algoritmo probabilístico inteligente.
Ver 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 emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ Beck, J. (1978), "On 3-cromatic hypergraphs", Discrete Mathematics , 24 (2): 127-137, doi : 10.1016 / 0012-365X (78) 90191-7 , MR 0522920
Otras lecturas
- Erdős, Paul (1963), "Sobre un problema combinatorio", Nordisk Mat. Tidskr. , 11 : 5-10
- Erds, P. (1964). "Sobre un problema combinatorio. II". Acta Mathematica Academiae Scientiarum Hungaricae . 15 (3–4): 445–447. doi : 10.1007 / BF01897152 .
- Schmidt, WM (1964). "Un problema kombinatorisches 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 London Mathematical Society , 8 (4): 681–682, doi : 10.1112 / jlms / s2-8.4.681.
- Toft, Bjarne (1975), "Sobre los hipergráficos críticos del color", en Hajnal, A .; Rado, Richard ; Sós, Vera T. (eds.), Conjuntos infinitos y finitos: Para 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", Electronic Research Announcements of the American Mathematical Society , 1 (3): 112-113, doi : 10.1090 / S1079-6762-95 -03004-6.
- Beck, J. (1978), "On 3-cromatic hypergraphs", 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 del hipergráfico 2" , Estructuras y algoritmos aleatorios , 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. Desgarrar. Varsovie , 30 : 31–38.
- Erdős, P .; Hajnal, A. (1961), "En una propiedad de familias de conjuntos", Acta Math. Acad. Sci. Colgado. , 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 4 hipergrafos uniformes sin propiedad B" . Matemáticas aplicadas discretas . 163, Parte 2: 199-204. doi : 10.1016 / j.dam.2011.11.035 .