En matemáticas, el segundo problema de vecindad es un problema sin resolver sobre gráficas orientadas planteado por Paul Seymour . Intuitivamente, sugiere que en una red social descrita por tal gráfico, alguien tendrá al menos tantos amigos de amigos como amigos. El problema también se conoce como la conjetura del segundo vecindario o la conjetura de la distancia dos de Seymour .
Declaración
Un gráfico orientado es un gráfico dirigido finito que se obtiene a partir de un gráfico simple no dirigido asignando una orientación a cada borde. De manera equivalente, es un gráfico dirigido que no tiene bucles propios, ni aristas paralelas ni ciclos de dos aristas. La primera vecindad de un vértice(también llamado vecindario abierto ) consiste en todos los vértices a una distancia uno de, y el segundo barrio de consta de todos los vértices a una distancia dos de . Estos dos vecindarios forman conjuntos disjuntos , ninguno de los cuales contiene sí mismo.
En 1990, Paul Seymour conjeturó que, en todo grafo orientado, siempre existe al menos un vérticecuyo segundo vecindario es al menos tan grande como su primer vecindario. De manera equivalente, en el cuadrado de la gráfica , el grado dees al menos el doble. El problema fue publicado por primera vez por Nathaniel Dean y Brenda J. Latka en 1995, en un artículo que estudiaba el problema en una clase restringida de gráficos orientados, los torneos (orientaciones de gráficos completos). Dean había conjeturado previamente que cada torneo obedece a la segunda conjetura del vecindario, y este caso especial se conoció como la conjetura de Dean. [1]
¿Cada grafo orientado contiene un vértice Seymour?
Un vértice en un gráfico dirigido cuya segunda vecindad es al menos tan grande como su primera vecindad se llama vértice Seymour . [2] En la conjetura de la segunda vecindad, la condición de que la gráfica no tenga ciclos de dos aristas es necesaria, ya que en las gráficas que tienen tales ciclos (por ejemplo, la gráfica orientada completa) todas las segundas vecindades pueden estar vacías o ser pequeñas.
Resultados parciales
Fisher (1996) demostró la conjetura de Dean, el caso especial del segundo problema vecinal para los torneos. [3]
Para algunos gráficos, un vértice de grado mínimo de salida será un vértice Seymour. Por ejemplo, si un gráfico dirigido tiene un sumidero, un vértice de grado cero, entonces el sumidero es automáticamente un vértice Seymour, porque su primer y segundo vecindario tienen ambos tamaño cero. En un gráfico sin sumideros, un vértice de grado uno es siempre un vértice Seymour. En las orientaciones de las gráficas gráficas sin triángulos , cualquier vértice de grado mínimo de salida es de nuevo un vértice Seymour, porque para cualquier borde de a otro vértice , los vecinos de todos pertenecen al segundo barrio de . [4] Para gráficos arbitrarios con grados de vértice más altos, los vértices de grado mínimo pueden no ser vértices de Seymour, pero la existencia de un vértice de bajo grado aún puede conducir a la existencia de un vértice de Seymour cercano. Usando este tipo de razonamiento, se ha demostrado que la segunda conjetura de vecindad es cierta para cualquier grafo orientado que contenga al menos un vértice de grado ≤ 6. [5]
Los torneos aleatorios y los gráficos orientados al azar tienen muchos vértices Seymour con alta probabilidad. [2] Cada grafo orientado tiene un vértice cuyo segundo vecindario es al menos veces tan grande como el primer barrio, donde
es la raíz real del polinomio . [6]
Ver también
Referencias
- ↑ Dean, Nathaniel; Latka, Brenda J. (1995), "Cuadrando el torneo: un problema abierto", Actas de la XXVI Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Boca Raton, FL, 1995), Congressus Numerantium , 109 : 73 –80, MR 1369296
- ^ a b Cohn, Zachary; Godbole, Anant; Wright Harkness, Elizabeth; Zhang, Yiguang (2016), "El número de vértices de Seymour en torneos aleatorios y dígrafos", Graphs and Combinatorics , 32 (5): 1805–1816, arXiv : 1502.04061 , doi : 10.1007 / s00373-015-1672-9 , MR 3543199
- ^ Fisher, David C. (1996), "Cuadrar un torneo: una prueba de la conjetura de Dean", Journal of Graph Theory , 23 (1): 43–48, doi : 10.1002 / (SICI) 1097-0118 (199609) 23: 1 <43 :: AID-JGT4> 3.0.CO; 2-K , MR 1402137
- ^ Brantner, James; Brockman, Greg; Kay, Bill; Snively, Emma (2009), "Contribuciones a la conjetura del segundo vecindario de Seymour", Involve , 2 (4): 385–393, arXiv : 0808.0946 , doi : 10.2140 / involut.2009.2.387 , MR 2579558
- ^ Kaneko, Yoshihiro; Locke, Stephen C. (2001), "El enfoque de grado mínimo para la conjetura de la distancia 2 de Paul Seymour", Actas de la XXXII Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Baton Rouge, LA, 2001), Congressus Numerantium , 148 : 201–206, MR 1887387
- ^ Chen, Guantao; Shen, Jian; Yuster, Raphael (2003), "Segundo barrio a través del primer barrio en dígrafos", Annals of Combinatorics , 7 (1): 15-20, doi : 10.1007 / s000260300001 , MR 1984642
enlaces externos
- Segunda conjetura de vecindario de Seymour , Problemas abiertos en teoría de grafos y combinatoria, Douglas B. West .