Source author record

Viresh Patel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics Computational Complexity math-ph math.MP math.PR

Catalog footprint

Research overview

15works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sampling from the low temperature Potts model through a Markov chain on flows

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 configurations, we consider the equivalent problem of sampling flows. We show, using path coupling, that a simple and natural Markov chain on the set of flows is rapidly mixing. As a result we find a $δ$ -approximate sampling algorithm for the Potts model at low enough temperatures, whose running time is bounded by $O(m^2\log(mδ^{-1}))$ for graphs $G$ with $m$ edges.

preprint2021arXiv

Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

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 complex plane. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all $|λ|\neq 1$ by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens around $λ=1$ , where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point $λ=1$ , and more generally on the entire unit circle. For an integer $Δ\geq 3$ and edge interaction parameter $b\in (0,1)$ we show #P-hardness for approximating the partition function on graphs of maximum degree $Δ$ on the arc of the unit circle where the Lee-Yang zeros are dense. This result contrasts with known approximation algorithms when $|λ|\neq 1$ or when $λ$ is in the complementary arc around $1$ of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs.

preprint2021arXiv

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

For a graph $G=(V,E)$ , $k\in \mathbb{N}$ , and a complex number $w$ the partition function of the univariate Potts model is defined as ${\bf Z}(G;k,w):=\sum_{ϕ:V\to [k]}\prod_{\substack{uv\in E \\ ϕ(u)=ϕ(v)}}w,$ where $[k]:=\{1,\ldots,k\}$ . In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any $Δ\in \mathbb{N}$ and any $k\geq eΔ+1$ , there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${\bf Z}(G;k,w)\neq 0$ for any $w\in U$ and any graph $G$ of maximum degree at most $Δ$ . (Here $e$ denotes the base of the natural logarithm.) For small values of $Δ$ we are able to give better results. As an application of our results we obtain improved bounds on $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$ -colourings of graphs of small maximum degree.

preprint2020arXiv

A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $α\in (0,1)$ , there exists a $c=c(α)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$ -regular graph $G$ on $n$ vertices with $D\geq αn$ , determines whether $G$ contains a cycle on at least $n - c$ vertices. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.

preprint2020arXiv

Structure and colour in triangle-free graphs

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 $\lceil\frac12χ\rceil$ . This is sharp up to a factor $2$ . This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $χ$ contains an induced cycle of length $Ω(χ\logχ)$ as $χ\to\infty$ . Even if one only demands an induced path of length $Ω(χ\logχ)$ , the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$ -free graph has chromatic number at most $c D/\log D$ . We prove this assertion with `triangle-free' replaced by `regular girth $5$ '.

preprint2019arXiv

Decomposing tournaments into paths

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 decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$ . There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.

preprint2019arXiv

Statistical physics approaches to Unique Games

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 Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.

preprint2015arXiv

A domination algorithm for $\{0,1\}$ -instances of the travelling salesman problem

We present an approximation algorithm for $\{0,1\}$ -instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial-time algorithm which has domination ratio $1-n^{-1/29}$ . In other words, given a $\{0,1\}$ -edge-weighting of the complete graph $K_n$ on $n$ vertices, our algorithm outputs a Hamilton cycle $H^*$ of $K_n$ with the following property: the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of $H^*$ is at most $n^{-1/29}$ . Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio $1/2-o(1)$ for arbitrary edge-weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant $C$ such that $n^{-1/29}$ cannot be replaced by $\exp(-(\log n)^C)$ in the result above.

preprint2015arXiv

Excluding hooks and their complements

The celebrated Erdos-Hajnal conjecture states that for every $n$ -vertex undirected graph $H$ there exists $\eps(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{\eps(H)}$. A weaker version of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^{\compl}$. We show that the weaker conjecture holds if $H$ is any path with a pendant edge at its third vertex; thus we give a new infinite family of graphs for which the conjecture holds.

preprint2014arXiv

Finding Shortest Paths between Graph Colourings

The $k$ -colouring reconfiguration problem asks whether, for a given graph $G$ , two proper $k$ -colourings $α$ and $β$ of $G$ , and a positive integer $\ell$ , there exists a sequence of at most $\ell+1$ proper $k$ -colourings of $G$ which starts with $α$ and ends with $β$ and where successive colourings in the sequence differ on exactly one vertex of $G$ . We give a complete picture of the parameterized complexity of the $k$ -colouring reconfiguration problem for each fixed $k$ when parameterized by $\ell$ . First we show that the $k$ -colouring reconfiguration problem is polynomial-time solvable for $k=3$ , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $k \geq 4$ , we show that the $k$ -colouring reconfiguration problem, when parameterized by $\ell$ , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

preprint2014arXiv

Mixing of the Glauber dynamics for the ferromagnetic Potts model

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 interaction strength, we study the interplay between the maximum degree ( $Δ$ ) of the underlying graph and the number of colours or spins ( $q$ ) in determining whether the dynamics mixes rapidly or not. We find a lower bound $L$ on the number of colours such that Glauber dynamics is rapidly mixing if at least $L$ colours are used. We give a closely-matching upper bound $U$ on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random $Δ$ -regular graphs when at most $U$ colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree $Δ$ , e.g. toroidal grids for $Δ= 4$ .

preprint2014arXiv

Parameterized TSP: Beating the Average

In the Travelling Salesman Problem (TSP), we are given a complete graph $K_n$ together with an integer weighting $w$ on the edges of $K_n$ , and we are asked to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the average weight of a Hamilton cycle of $K_n$ for the weighting $w$ . Vizing (1973) asked whether there is a polynomial-time algorithm which always finds a Hamilton cycle of weight at most $h(w)$ . He answered this question in the affirmative and subsequently Rublineckii (1973) and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalisation of Vizing's result: for each fixed $k$ , we give an algorithm that decides whether, for any input edge weighting $w$ of $K_n$ , there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs such a cycle if it exists). For $k$ fixed, the running time of the algorithm is polynomial in $n$ , where the degree of the polynomial does not depend on $k$ (i.e., the generalised Vizing problem is fixed-parameter tractable with respect to the parameter $k$ ).

preprint2013arXiv

Poset limits can be totally ordered

S.Janson [Poset limits and exchangeable random posets, Combinatorica 31 (2011), 529--563] defined limits of finite posets in parallel to the emerging theory of limits of dense graphs. We prove that each poset limit can be represented as a kernel on the unit interval with the standard order, thus answering an open question of Janson. We provide two proofs: real-analytic and combinatorial. The combinatorial proof is based on a Szemeredi-type Regularity Lemma for posets which may be of independent interest. Also, as a by-product of the analytic proof, we show that every atomless ordered probability space admits a measure-preserving and almost order-preserving map to the unit interval.

preprint2012arXiv

Tight inequalities among set hitting times in Markov chains

Given an irreducible discrete-time Markov chain on a finite state space, we consider the largest expected hitting time $T(α)$ of a set of stationary measure at least $α$ for $α\in(0,1)$ . We obtain tight inequalities among the values of $T(α)$ for different choices of $α$ . One consequence is that $T(α) \le T(1/2)/α$ for all $α< 1/2$ . As a corollary we have that, if the chain is lazy in a certain sense as well as reversible, then $T(1/2)$ is equivalent to the chain's mixing time, answering a question of Peres. We furthermore demonstrate that the inequalities we establish give an almost everywhere pointwise limiting characterisation of possible hitting time functions $T(α)$ over the domain $α\in(0,1/2]$ .

preprint2010arXiv

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

In this paper, we show that for an $n$ -vertex graph $G$ of genus $g$ , the edge expansion of $G$ can be determined in time $n^{O(g^2)}$ . We show that the same is true for various other similar measures of edge connectivity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Viresh Patel

Research overview

Is this your work?

15 publications

Sampling from the low temperature Potts model through a Markov chain on flows

Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

Structure and colour in triangle-free graphs

Decomposing tournaments into paths

Statistical physics approaches to Unique Games

A domination algorithm for $\{0,1\}$ -instances of the travelling salesman problem

Excluding hooks and their complements

Finding Shortest Paths between Graph Colourings

Mixing of the Glauber dynamics for the ferromagnetic Potts model

Parameterized TSP: Beating the Average

Poset limits can be totally ordered

Tight inequalities among set hitting times in Markov chains

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

See the researcher in context

Building this map preview

Viresh Patel

Research overview

Is this your work?

15 publications

Sampling from the low temperature Potts model through a Markov chain on flows

Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

Structure and colour in triangle-free graphs

Decomposing tournaments into paths

Statistical physics approaches to Unique Games

A domination algorithm for {0,1}\{0,1\}{0,1}-instances of the travelling salesman problem

Excluding hooks and their complements

Finding Shortest Paths between Graph Colourings

Mixing of the Glauber dynamics for the ferromagnetic Potts model

Parameterized TSP: Beating the Average

Poset limits can be totally ordered

Tight inequalities among set hitting times in Markov chains

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

See the researcher in context

Building this map preview

A domination algorithm for $\{0,1\}$ -instances of the travelling salesman problem