En matemáticas, el segundo problema de vecindad es un problema no resuelto sobre grafos orientados planteado por Paul Seymour . Intuitivamente, sugiere que en una red social descrita por un grafo de este tipo, alguien tendrá al menos tantos amigos de amigos como amigos. [1] [2]
El problema también se conoce como conjetura de la segunda vecindad o conjetura de la distancia dos de Seymour . [1] [3]
Un grafo orientado es un grafo dirigido finito obtenido a partir de un grafo simple no dirigido mediante la asignación de una orientación a cada arista. De manera equivalente, es un grafo dirigido que no tiene bucles propios, ni aristas paralelas, ni ciclos de dos aristas. La primera vecindad de un vértice (también llamada su vecindad abierta ) consiste en todos los vértices a una distancia de uno de , y la segunda vecindad de consiste en todos los vértices a una distancia de dos de . Estas dos vecindades forman conjuntos disjuntos , ninguno de los cuales se contiene a sí mismo.
En 1990, Paul Seymour conjeturó que, en todo grafo orientado, siempre existe al menos un vértice cuyo segundo vecindario es al menos tan grande como su primer vecindario. De manera equivalente, en el cuadrado del grafo , el grado de es 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 grafos orientados, los torneos (orientaciones de grafos completos). Dean había conjeturado previamente que todo torneo obedece a la conjetura del segundo vecindario, y este caso especial se conoció como la conjetura de Dean. [4]
Un vértice en un gráfico dirigido cuyo segundo vecindario es al menos tan grande como su primer vecindario se llama vértice de Seymour . [5]
En la segunda conjetura de vecindad, la condición de que el grafo no tenga ciclos de dos aristas es necesaria, ya que en grafos que tienen tales ciclos (por ejemplo, el grafo completamente orientado) todas las segundas vecindades pueden estar vacías o pequeñas.
Fisher (1996) demostró la conjetura de Dean, el caso especial del segundo problema de vecindad para torneos. [6]
Para algunos grafos, un vértice de grado de salida mínimo será un vértice de Seymour. Por ejemplo, si un grafo dirigido tiene un sumidero, un vértice de grado de salida cero, entonces el sumidero es automáticamente un vértice de Seymour, porque sus primeros y segundos vecindarios tienen ambos tamaño cero. En un grafo sin sumideros, un vértice de grado de salida uno es siempre un vértice de Seymour. En las orientaciones de grafos sin triángulos , cualquier vértice de grado de salida mínimo es nuevamente un vértice de Seymour, porque para cualquier arista de a otro vértice , los vecinos de salida de todos pertenecen al segundo vecindario de . [7]
En el caso de grafos arbitrarios con grados de vértice superiores, los vértices de grado mínimo podrían no ser vértices de Seymour, pero la existencia de un vértice de grado bajo puede conducir a la existencia de un vértice de Seymour cercano. Utilizando este tipo de razonamiento, se ha demostrado que la segunda conjetura de vecindad es verdadera para cualquier grafo orientado que contenga al menos un vértice de grado de salida ≤ 6. [8]
Los torneos aleatorios y algunos gráficos dirigidos aleatorios tienen muchos vértices de Seymour con alta probabilidad. [5] Cada gráfico orientado tiene un vértice cuyo segundo vecindario es al menos 2 veces más grande que el primer vecindario, donde
es la raíz real del polinomio . [9]
![{\displaystyle \gamma ={\frac {1}{6}}\left(-1+{\sqrt[{3}]{53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\aproximadamente 0,657}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b32efcf531b7721616f8f8a5a20e6ef022d7e2e)
