Zobrazeno 1 - 10
of 176
pro vyhledávání: '"Patel, Viresh"'
Autor:
Patel, Viresh, Yıldız, Mehmet Akif
We consider the problem of decomposing the edges of a digraph into as few paths as possible. A natural lower bound for the number of paths in any path decomposition of a digraph $D$ is $\frac{1}{2}\sum_{v\in V(D)}|d^+(v)-d^-(v)|$; any digraph that ac
Externí odkaz:
http://arxiv.org/abs/2411.06982
The partition function of the Ising model of a graph $G=(V,E)$ is defined as $Z_{\text{Ising}}(G;b)=\sum_{\sigma:V\to \{0,1\}} b^{m(\sigma)}$, where $m(\sigma)$ denotes the number of edges $e=\{u,v\}$ such that $\sigma(u)=\sigma(v)$. We show that for
Externí odkaz:
http://arxiv.org/abs/2311.05574
A conjecture of Jackson from 1981 states that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian. We prove this conjecture for sufficiently large $n$. In fact we prove a more general result that for all $\alpha>0$, ther
Externí odkaz:
http://arxiv.org/abs/2309.11677
We prove that for any graph $G$ of maximum degree at most $\Delta$, the zeros of its chromatic polynomial $\chi_G(x)$ (in $\mathbb{C}$) lie inside the disc of radius $5.94 \Delta$ centered at $0$. This improves on the previously best known bound of a
Externí odkaz:
http://arxiv.org/abs/2309.10928
Autor:
Patel, Viresh, Regts, Guus
Publikováno v:
Bulletin of EATCS 138, no. 3 (2022)
In this article we consider certain well-known polynomials associated with graphs including the independence polynomial and the chromatic polynomial. These polynomials count certain objects in graphs: independent sets in the case of the independence
Externí odkaz:
http://arxiv.org/abs/2212.08143
We prove that for every $\varepsilon > 0$ there exists $n_0=n_0(\varepsilon)$ such that every regular oriented graph on $n > n_0$ vertices and degree at least $(1/4 + \varepsilon)n$ has a Hamilton cycle. This establishes an approximate version of a c
Externí odkaz:
http://arxiv.org/abs/2203.10112
Publikováno v:
In Journal of Combinatorial Theory, Series B November 2024 169:233-252
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 decomposition of a directed graph $D$ in terms of its degree sequence: this i
Externí odkaz:
http://arxiv.org/abs/2109.13565
We prove that for any graph $G$ of maximum degree at most $\Delta$, the zeros of its chromatic polynomial $\chi_G(z)$ (in $\mathbb{C}$) lie outside the disk of radius $5.02 \Delta$ centered at $0$. This improves on the previously best known bound of
Externí odkaz:
http://arxiv.org/abs/2105.03304
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. W
Externí odkaz:
http://arxiv.org/abs/2103.07360