8 papers
Creating Subgraphs in Semi-Random Hypergraph Games
Natalie Behague, Pawel Pralat, Andrzej Rucinski
The semi-random hypergraph process is a natural generalisation of the semi-random graph process, which can be thought of as a one player game. For fixed , starting with an e…
The Fagnano Triangle Patrolling Problem
Konstantinos Georgiou, Somnath Kundu, Pawel Pralat
We investigate a combinatorial optimization problem that involves patrolling the edges of an acute triangle using a unit-speed agent. The goal is to minimize the maximum (1-gap) id…
Asynchronous Majority Dynamics on Binomial Random Graphs
Divyarthi Mohan, Pawel Pralat
We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is "corr…
Label propagation on binomial random graphs
Marcos Kiwi, Lyuben Lichev, Dieter Mitsche +1
We study the behavior of a label propagation algorithm (LPA) on the ErdÅs-Rényi random graph . Initially, given a network, each vertex starts with a random labe…
Almost all 9-regular graphs have a modulo-5 orientation
Michelle Delcourt, Reaz Huq, Pawel Pralat
In 1972 Tutte famously conjectured that every 4-edge-connected graph has a nowhere zero 3-flow; this is known to be equivalent to every 5-regular, 4-edge-connected graph having an…
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than Rounds
Alan Frieze, Pu Gao, Calum MacRury +2
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on vertices. In each round, a vertex is…