115 citations · 203 across the 24 of their papers we have counts for
27 papers
Approximate counting using Taylor's theorem: a survey
Viresh Patel, Guus Regts
In this article we consider certain well-known polynomials associated with graphs including the independence polynomial and the chromatic polynomial. These polynomials count certai…
Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs
Allan Lo, Viresh Patel, Mehmet Akif Yıldız
We prove that for every there exists such that every regular oriented graph on vertices and degree at least $(1/4 + \varepsilon)n…
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…
Improved bounds for zeros of the chromatic polynomial on bounded degree graphs
Maurizio Moreschi, Viresh Patel, Guus Regts +1
We prove that for any graph of maximum degree at most , the zeros of its chromatic polynomial (in ) lie outside the disk of radius centered at…
Sampling from the low temperature Potts model through a Markov chain on flows
Jeroen Huijben, Viresh Patel, Guus Regts
In this paper we consider the algorithmic problem of sampling from the Potts model and computing its partition function at low temperatures. Instead of directly working with spin c…
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…
Decomposing tournaments into paths
Allan Lo, Viresh Patel, Jozef Skokan +1
We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomp…
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
Ferenc Bencs, Ewan Davies, Viresh Patel +1
For a graph , , and a complex number the partition function of the univariate Potts model is defined as \[ {\bf Z}(G;k,w):=\sum_{ϕ:V\to [k]}\prod_{\su…
Computing the number of induced copies of a fixed graph in a bounded degree graph
Viresh Patel, Guus Regts
In this paper we show that for any graph of order and any graph of order and maximum degree one can compute the number of subsets of that induces a g…
Discrepancy and large dense monochromatic subsets
Ross Kang, Viresh Patel, Guus Regts
Erdős and Pach (1983) introduced the natural degree-based generalisations of Ramsey numbers, where instead of seeking large monochromatic cliques in a -edge coloured complete gr…
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
Viresh Patel, Guus Regts
In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomial…
Excluding hooks and their complements
Krzysztof Choromanski, Dvir Falik, Anita Liebenau +2
The celebrated Erdos-Hajnal conjecture states that for every -vertex undirected graph there exists $\eps(H)>0$ such that every graph that does not contain as an indu…
Hamilton cycles in sparse robustly expanding digraphs
Allan Lo, Viresh Patel
The notion of robust expansion has played a central role in the solution of several conjectures involving the packing of Hamilton cycles in graphs and directed graphs. These and ot…
On a Ramsey-type problem of Erdős and Pach
Ross J. Kang, Eoin Long, Viresh Patel +1
In this paper we show that there exists a constant such that for any graph on vertices either or its complement has an induced subgraph on ver…
Parameterized TSP: Beating the Average
Gregory Gutin, Viresh Patel
In the Travelling Salesman Problem (TSP), we are given a complete graph together with an integer weighting on the edges of , and we are asked to find a Hamilton cycl…
Finding Shortest Paths between Graph Colourings
Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2
The -colouring reconfiguration problem asks whether, for a given graph , two proper -colourings and of , and a positive integer , there exists a sequence…
A precise threshold for quasi-Ramsey numbers
Ross J. Kang, János Pach, Viresh Patel +1
We consider a variation of Ramsey numbers introduced by Erdős and Pach (1983), where instead of seeking complete or independent sets we only seek a -homogeneous set, a vertex su…
A domination algorithm for -instances of the travelling salesman problem
Daniela Kühn, Deryk Osthus, Viresh Patel
We present an approximation algorithm for -instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we giv…
Mixing of the Glauber dynamics for the ferromagnetic Potts model
Magnus Bordewich, Catherine Greenhill, Viresh Patel
We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interact…
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
Daniela Kühn, John Lapinskas, Deryk Osthus +1
A conjecture of Thomassen from 1982 states that for every k there is an f(k) so that every strongly f(k)-connected tournament contains k edge-disjoint Hamilton cycles. A classical…