8 papers
Path decompositions of random directed graphs
Alberto Espuny Díaz, Viresh Patel, Fabian Stroh
We consider the problem of decomposing the edges of a directed graph into as few paths as possible. There is a natural lower bound for the number of paths needed in an edge decompo…
Switch-based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
Pieter Kleer, Viresh Patel, Fabian Stroh
We consider the irreducibility of switch-based Markov chains for the approximate uniform sampling of Hamiltonian cycles in a given undirected dense graph on vertices. As our ma…
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Viresh Patel, Fabian Stroh
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given , there exists a such that the fo…
Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
Pjotr Buys, Andreas Galanis, Viresh Patel +1
We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter on the unit circle in the compl…
Structure and colour in triangle-free graphs
N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg +3
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number contains a rainbow independent set of size $…
Statistical physics approaches to Unique Games
Matthew Coulson, Ewan Davies, Alexandra Kolla +2
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Game…