En matemáticas , un k - grafo ultrahomogéneo es un grafo en el que cada isomorfismo entre dos de sus subgrafos inducidos de como máximo k vértices puede extenderse a un automorfismo de todo el grafo. Un k - grafo homogéneo obedece a una versión debilitada de la misma propiedad en la que cada isomorfismo entre dos subgrafos inducidos implica la existencia de un automorfismo de todo el grafo que mapea un subgrafo con el otro (pero no necesariamente extiende el isomorfismo dado). [1]
Un gráfico homogéneo es un gráfico que es k -homogéneo para cada k , o equivalentemente k -ultrahomogéneo para cada k . [1]
Clasificación
Las únicas gráficas finitas homogéneas son las gráficas de conglomerados mK n formadas a partir de las uniones disjuntas de gráficas completas isomorfas , las gráficas de Turán formadas como las gráficas de complemento de mK n , la gráfica de torre de 3 × 3 y el ciclo de 5 . [2]
Las únicas gráficas homogéneas infinitas contables son las uniones disjuntas de gráficas completas isomórficas (con el tamaño de cada gráfica completa, el número de gráficas completas o ambos números infinitos contables), sus gráficas de complemento, las gráficas de Henson junto con sus gráficas de complemento, y el gráfico de Rado . [3]
Si un gráfico es 5-ultrahomogéneo, entonces es ultrahomogéneo para cada k . Solo hay dos gráficos conectados que son 4-ultrahomogéneos pero no 5-ultrahomogéneos: el gráfico de Schläfli y su complemento. La prueba se basa en la clasificación de grupos simples finitos . [4]
Variaciones
Un gráfico es homogéneo conectado si cada isomorfismo entre dos subgrafos inducidos conectados puede extenderse a un automorfismo de todo el gráfico. Además de los gráficos homogéneos, los gráficos finitos homogéneos conectados incluyen todos los gráficos de ciclo , todos los gráficos de torre cuadrada , el gráfico de Petersen y el gráfico de Clebsch de 5 regulares . [5]
Notas
Referencias
- Buczak, JMJ (1980), Teoría de grupos finitos , Ph.D. tesis, Universidad de Oxford. Como lo cita Devillers (2002) .
- Cameron, Peter Jephson (1980), "6 gráficos transitivos", Journal of Combinatorial Theory , Serie B, 28 : 168–179, doi : 10.1016 / 0095-8956 (80) 90063-5. Como lo cita Devillers (2002) .
- Devillers, Alice (2002), Clasificación de algunas estructuras homogéneas y ultrahomogéneas , Ph.D. tesis, Université Libre de Bruxelles.
- Gardiner, A. (1976), "Gráficos homogéneos", Journal of Combinatorial Theory , Serie B, 20 (1): 94-102, doi : 10.1016 / 0095-8956 (76) 90072-1 , MR 0419293.
- Gardiner, A. (1978), "Condiciones de homogeneidad en gráficos", Journal of Combinatorial Theory , Serie B, 24 (3): 301–310, doi : 10.1016 / 0095-8956 (78) 90048-5 , MR 0496449.
- Gray, R .; Macpherson, D. (2010), "Gráficos homogéneos conectados contables", Journal of Combinatorial Theory , Serie B, 100 (2): 97-118, doi : 10.1016 / j.jctb.2009.04.002 , MR 2595694.
- Lachlan, AH; Woodrow, Robert E. (1980), "Gráficos no dirigidos ultrahomogéneos contables", Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10.2307 / 1999974 , MR 0583847.
- Ronse, Christian (1978), "Sobre gráficos homogéneos", Revista de la Sociedad Matemática de Londres , Segunda serie, 17 (3): 375–379, doi : 10.1112 / jlms / s2-17.3.375 , MR 0500619.