Capturando a un ladrón en un hipergráfico k-uniforme aleatorio

Resumen El juego de Cops and Robber generalmente se juega en un gráfico, donde un grupo de policías intenta atrapar a un ladrón que se mueve a lo largo de los bordes del gráfico. El número de policías de un gráfico es el número mínimo de policías requeridos para ganar el juego. Una conjetura importante en esta área, debido a Meyniel, establece que el número de policías de un gráfico conectado de n vértices es O (n). En 2016, Prałat y Wormald mostraron que esta conjetura se sostiene con alta probabilidad para gráficos aleatorios por encima del umbral de conectividad. Además, Łuczak y Prałat mostraron que en una escala -el número de policías demuestra un sorprendente comportamiento en zigzag en regímenes densos del gráfico aleatorio binomial G (n, p). En este trabajo, consideramos el juego de Cops and Robber en un hipergráfico, donde los jugadores se mueven a lo largo de hiperborde en lugar de bordes. Mostramos que con alta probabilidad el número de policías del hipergráfico aleatorio binomial Gᵏ (n, p) es O ({nk}\, n) para un amplio rango de parámetros p y k y que en una escala -nuestra cota superior en el número de policías surge como el mínimo de dos curvas en zigzag complementarias, a diferencia del caso de G (n, p). Además, conjeturamos que el número de policías de un hipergráfico k-uniforme conectado en n vértices es O ({nk}\, ).