¿Existe un gráfico fuertemente regular con parámetros (99,14,1,2)?
En teoría de grafos , el problema de 99 grafos de Conway es un problema sin resolver que pregunta si existe un grafo no dirigido con 99 vértices , en el que cada dos vértices adyacentes tienen exactamente un vecino común, y en el que cada dos vértices no adyacentes tienen exactamente dos vecinos comunes. . De manera equivalente, cada borde debe ser parte de un triángulo único y cada par no adyacente debe ser una de las dos diagonales de un ciclo único de 4. John Horton Conway ofreció un premio de $ 1000 por su solución. [1]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/34/33-duoprism_graph.svg/220px-33-duoprism_graph.svg.png)
Propiedades
Si tal gráfico existe, sería necesariamente un gráfico localmente lineal y un gráfico fuertemente regular con parámetros (99,14,1,2). Los parámetros primero, tercero y cuarto codifican el enunciado del problema: el gráfico debe tener 99 vértices, cada par de vértices adyacentes debe tener 1 vecino común y cada par de vértices no adyacentes debe tener 2 vecinos comunes. El segundo parámetro significa que el gráfico es un gráfico regular con 14 aristas por vértice. [2]
Si esta gráfica existe, no puede tener simetrías que lleven cada vértice a cada otro vértice. [3] Se conocen restricciones adicionales sobre sus posibles grupos de simetrías. [4] [5]
Historia
La posibilidad de un gráfico con estos parámetros ya fue sugerida en 1969 por Norman L. Biggs , [6] y su existencia fue señalada como un problema abierto por otros antes de Conway. [3] [7] [8] [9] El propio Conway había trabajado en el problema ya en 1975, [7] pero ofreció el premio en 2014 como parte de un conjunto de problemas planteados en la Conferencia DIMACS sobre desafíos para identificar enteros. Secuencias. Otros problemas en el set incluyen la conjetura de thrackle , el espaciado mínimo de los sets de Danzer y la cuestión de quién gana después de la jugada 16 en la moneda del juego sylver . [1]
Gráficos relacionados
De manera más general, solo hay cinco combinaciones posibles de parámetros para las cuales podría existir un gráfico fuertemente regular con cada borde en un triángulo único y cada no borde formando la diagonal de un cuadrilátero único. Solo se sabe que existen gráficos con dos de estas cinco combinaciones. Estos dos gráficos son el gráfico de Paley de nueve vértices (el gráfico del duoprisma 3-3 ) con parámetros (9,4,1,2) y el gráfico de Berlekamp – van Lint – Seidel con parámetros (243,22,1,2 ). Los parámetros para los que se desconocen los gráficos son: (99,14,1,2), (6273,112,1,2) y (494019,994,1,2). El problema de 99 gráficos describe la más pequeña de estas combinaciones de parámetros para las que se desconoce la existencia de un gráfico. [4]
Referencias
- ↑ a b Conway, John H. , Five $ 1,000 Problems (Update 2017) (PDF) , On-Line Encyclopedia of Integer Sequences , consultado el 12 de febrero de 2019. Véase también la secuencia A248380 de OEIS .
- ^ Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), No el problema de 99 gráficos de Conway , arXiv : 1707.08047
- ^ a b Wilbrink, HA (agosto de 1984), "En el gráfico (99,14,1,2) fuertemente regular", en de Doelder, PJ; de Graaf, de, J .; van Lint, JH (eds.), Artículos dedicados a JJ Seidel (PDF) , Informe EUT, 84-WSK-03, Universidad Tecnológica de Eindhoven, págs. 342–355
- ^ a b Makhnev, AA; Minakova, IM (enero de 2004), "Sobre automorfismos de gráficos fuertemente regulares con parámetros, ", Matemáticas discretas y aplicaciones , 14 (2), doi : 10.1515 / 156939204872374 , MR 2069991 , S2CID 118034273
- ^ Behbahani, Majid; Lam, Clement (2011), "Gráficos fuertemente regulares con automorfismos no triviales", Matemáticas discretas , 311 (2–3): 132–144, doi : 10.1016 / j.disc.2010.10.005 , MR 2739917
- ^ Biggs, Norman (1971), Grupos finitos de automorfismos: curso impartido en la Universidad de Southampton, octubre-diciembre de 1969 , London Mathematical Society Lecture Note Series, 6 , Londres y Nueva York: Cambridge University Press, p. 111, ISBN 9780521082150, MR 0327563
- ^ a b Guy, Richard K. (1975), "Problemas", en Kelly, LM (ed.), Actas de una conferencia celebrada en la Universidad Estatal de Michigan, East Lansing, Michigan, 17-19 de junio de 1974 , Lecture Notes in Mathematics, 490 , Berlín y Nueva York: Springer-Verlag, págs. 233–244, doi : 10.1007 / BFb0081147 , MR 0388240. Véase el problema 7 (JJ Seidel), págs. 237-238.
- ^ Brouwer, AE ; Neumaier, A. (1988), "Una observación sobre los espacios lineales parciales de circunferencia 5 con una aplicación a gráficos fuertemente regulares" , Combinatorica , 8 (1): 57–61, doi : 10.1007 / BF02122552 , MR 0951993 , S2CID 206812356
- ^ Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR 1311922