Teorema del coloreo de carreteras
Road coloring problem
- Fecha
- 2009 · fiabilidad alta
- Lugar
- Ramat Gan, Distrito de Tel Aviv, Israel
- Autoría
- Avraham Trahtman (conjeturado por Roy Adler y Benjamin Weiss)
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema de teoría de grafos y dinámica simbólica que demuestra que todo grafo dirigido fuertemente conexo y aperiódico con el mismo grado de salida en cada vértice admite un etiquetado de sus aristas que sincroniza el camino hacia cualquier vértice desde cualquier otro; conjeturado por Roy Adler y Benjamin Weiss y demostrado por Avraham Trahtman en 2009.
A qué dio paso
- Aplicaciones en dinámica simbólica
- Relevancia en la sincronización de instrucciones en robótica y redes
- Resolución de una conjetura combinatoria abierta durante décadas