-
Number of Eulerian orientations for Benjamini--Schramm convergent graph sequences
Abstract: For a graph $G$ let $\varepsilon(G)$ denote the number of Eulerian orientations, and $v(G)$ denote the number of vertices of $G$. We show that if $(G_n)_n$ is a sequence of Eulerian graphs that are convergent in Benjamini--Schramm sense, then $\lim\limits_{n\to \infty}\frac{1}{v(G_n)}\ln \varepsilon(G_n)$ is convergent.
Submitted 26 September, 2024; originally announced September 2024.
Comments: 15 pages, 3 figures
-
arXiv:2408.04727 [pdf, ps, other]
Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
Abstract: Let $Δ,q\geq 3$ be integers. We prove that there exists $η\geq 0.002$ such that if $q\geq (2-η)Δ$, then there exists an open set $\mathcal{U}\subset \mathbb{C}$ that contains the interval $[0,1]$ such that for each $w\in \mathcal{U}$ and any graph $G=(V,E)$ of maximum degree at most $Δ$, the partition function of the anti-ferromagnetic $q$-state Potts model evaluated at $w$ does not vanish. This p… ▽ More
Submitted 8 August, 2024; originally announced August 2024.
-
arXiv:2404.08577 [pdf, ps, other]
Approximating the volume of a truncated relaxation of the independence polytope
Abstract: Answering a question of Gamarnik and Smedira, we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. Our algorithm is obtained by viewing the volume as an evaluation of a graph polynomial and we approximate this evaluation using Barvinok's interpolation method.
Submitted 12 April, 2024; originally announced April 2024.
MSC Class: 05C31; 52B55; 05C69
-
arXiv:2310.04338 [pdf, ps, other]
Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
Abstract: We show that the anti-ferromagnetic Potts model on trees exhibits strong spatial mixing for a near-optimal range of parameters. Our work complements recent results of Chen, Liu, Mani, and Moitra [arXiv.2304.01954] who showed this to be true in the infinite temperature setting, corresponding to uniform proper colorings. We furthermore prove weak spatial mixing results complementing results in [arXi… ▽ More
Submitted 6 October, 2023; originally announced October 2023.
Comments: 23 pages
-
Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs
Abstract: In this paper we investigate the distribution of zeros of the independence polynomial of hypergraphs of maximum degree $Δ$. For graphs the largest zero-free disk around zero was described by Shearer as having radius $λ_s(Δ)=(Δ-1)^{Δ-1}/Δ^Δ$. Recently it was shown by Galvin et al. that for hypergraphs the disk of radius $λ_s(Δ+1)$ is zero-free; however, it was conjectured that the actual truth shou… ▽ More
Submitted 31 May, 2023; originally announced June 2023.
Comments: 34 pages, 4 figures
MSC Class: 05C31; 05C65; 05C69; 37F44; 37F46
-
Approximating the chromatic polynomial is as hard as computing it exactly
Abstract: We show that for any non-real algebraic number $q$ such that $|q-1|>1$ or $\Re(q)>\frac{3}{2}$ it is \textsc{\#P}-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polynomial evaluated at $q$ on planar graphs. This implies \textsc{\#P}-hardness for all non-real algebraic $q$ on the family of all graphs. We moreover prove several… ▽ More
Submitted 13 November, 2023; v1 submitted 24 November, 2022; originally announced November 2022.
Comments: 47 pages; minor changes based on referee comments. The number of pages has gone up significantly because we used a different document class, namely cc. Accepted for publication in Computational Complexity
MSC Class: 68Q17; primary; 05C31; secondary
-
Random cluster model on regular graphs
Abstract: For a graph $G=(V,E)$ with $v(G)$ vertices the partition function of the random cluster model is defined by $$Z_G(q,w)=\sum_{A\subseteq E(G)}q^{k(A)}w^{|A|},$$ where $k(A)$ denotes the number of connected components of the graph $(V,A)$. Furthermore, let $g(G)$ denote the girth of the graph $G$, that is, the length of the shortest cycle. In this paper we show that if $(G_n)_n$ is a sequence of… ▽ More
Submitted 13 October, 2022; v1 submitted 13 May, 2022; originally announced May 2022.
Comments: 38 pages
-
On the location of chromatic zeros of series-parallel graphs
Abstract: In this paper we consider the zeros of the chromatic polynomial of series-parallel graphs. Complementing a result of Sokal, showing density outside the disk $|q-1|\leq1$, we show density of these zeros in the half plane $\Re(q)>3/2$ and we show there exists an open region $U$ containing the interval $(0,32/27)$ such that $U\setminus\{1\}$ does not contain zeros of the chromatic polynomial of serie… ▽ More
Submitted 15 May, 2023; v1 submitted 21 April, 2022; originally announced April 2022.
Comments: Small changes based on referee comments. Accepted for publication in the Electronic Journal of Combinatorics
MSC Class: 05C31 (Primary) 05C15; 37F10; 82B20 (Secondary)
-
On complex roots of the independence polynomial
Abstract: It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial $Z_G(λ)$ of a graph $G$ of maximum degree at most $d+1$ does not vanish provided that $\vertλ\vert \leq \frac{d^d}{(d+1)^{d+1}}$. Significant extensions of this result have recently been given in the case $\Re λ\geq 0$ by Peters and Regts (2019) and Bencs and Csikvári (arxiv:1807.08963).… ▽ More
Submitted 13 November, 2022; v1 submitted 11 April, 2022; originally announced April 2022.
Comments: Extended version., to appear in proceedings of SODA 2023
-
arXiv:2203.15457 [pdf, ps, other]
Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $Δ$-regular tree for large $Δ$
Abstract: In this paper we prove that for any integer $q\geq 5$, the anti-ferromagnetic $q$-state Potts model on the infinite $Δ$-regular tree has a unique Gibbs measure for all edge interaction parameters $w\in [1-q/Δ,1)$, provided $Δ$ is large enough. This confirms a longstanding folklore conjecture.
Submitted 21 August, 2023; v1 submitted 29 March, 2022; originally announced March 2022.
Comments: 21 pages, 1 figure. Small corrections based on referee comments. Published in Journal of Statistical Physics
MSC Class: 60K35 (Primary); 82B20; 05C99 (Secondary)
Journal ref: J Stat Phys 190, 140 (2023)
-
The limit of the zero locus of the independence polynomial for bounded degree graphs
Abstract: The goal of this paper is to accurately describe the maximal zero-free region of the independence polynomial for graphs of bounded degree, for large degree bounds. In previous work with de Boer, Guerini and Regts it was demonstrated that this zero-free region coincides with the normality region of the related occupation ratios. These ratios form a discrete semi-group that is in a certain sense gen… ▽ More
Submitted 11 November, 2021; originally announced November 2021.
MSC Class: 05C31; 37F10
-
arXiv:2106.12530 [pdf, ps, other]
Factor-of-iid balanced orientation of non-amenable graphs
Abstract: We show that if a non-amenable, quasi-transitive, unimodular graph $G$ has all degrees even then it has a factor-of-iid balanced orientation, meaning each vertex has equal in- and outdegree. This result involves extending earlier spectral-theoretic results on Bernoulli shifts to the Bernoulli graphings of quasi-transitive, unimodular graphs. As a consequence, we also obtain that when $G$ is regula… ▽ More
Submitted 14 June, 2021; originally announced June 2021.
Comments: 24 pages, 1 figure. This is one of two papers that are replacing the shorter arXiv submission arXiv:2101.12577v1 Factor of iid Schreier decoration of transitive graphs
MSC Class: 60G10; 60K35; 37A15; 37A30; 37A50; 20E05
Journal ref: European Journal of Combinatorics, vol. 115 (2024), p. 103784
-
arXiv:2105.06801 [pdf, ps, other]
Upper bound for the number of spanning forests of regular graphs
Abstract: We show that if $G$ is a $d$--regular graph on $n$ vertices, then the number of spanning forests $F(G)$ satisfies $F(G)\leq d^n$. The previous best bound due to Kahale and Schulman gave $(d+1/2+O(1/d))^n$. We also have the more precise conjecture that $$F(G)^{1/n}\leq \frac{(d-1)^{d-1}}{(d^2-2d-1)^{d/2-1}}.$$ If this conjecture is true, then the expression on the right hand side is the best possib… ▽ More
Submitted 8 December, 2022; v1 submitted 14 May, 2021; originally announced May 2021.
Comments: arXiv admin note: text overlap with arXiv:2105.06798
MSC Class: 05C30; 05C31; 05C70
-
arXiv:2105.06798 [pdf, ps, other]
Evaluations of Tutte polynomials of regular graphs
Abstract: Let $T_G(x,y)$ be the Tutte polynomial of a graph $G$. In this paper we show that if $(G_n)_n$ is a sequence of $d$-regular graphs with girth $g(G_n)\to \infty$, then for $x\geq 1$ and $0\leq y\leq 1$ we have $$\lim_{n\to \infty}T_{G_n}(x,y)^{1/v(G_n)}=t_d(x,y),$$ where… ▽ More
Submitted 14 May, 2021; originally announced May 2021.
MSC Class: 05C30; 05C31; 05C70
-
Extremizers and stability of the Betke--Weil inequality
Abstract: Let $K$ be a compact convex domain in the Euclidean plane. The mixed area $A(K,-K)$ of $K$ and $-K$ can be bounded from above by $1/(6\sqrt{3})L(K)^2$, where $L(K)$ is the perimeter of $K$. This was proved by Ulrich Betke and Wolfgang Weil (1991). They also showed that if $K$ is a polygon, then equality holds if and only if $K$ is a regular triangle. We prove that among all convex domains, equalit… ▽ More
Submitted 22 March, 2021; originally announced March 2021.
MSC Class: Primary 52A39; 52A40; 52A10; Secondary 52A25; 52A38
-
Factor-of-iid Schreier decorations of lattices in Euclidean spaces
Abstract: A Schreier decoration is a combinatorial coding of an action of the free group $F_d$ on the vertex set of a $2d$-regular graph. We investigate whether a Schreier decoration exists on various countably infinite transitive graphs as a factor of iid. We show that $\mathbb{Z}^d,d\geq3$, the square lattice and also the three other Archimedean lattices of even degree have finitary-factor-of-iid Schrei… ▽ More
Submitted 21 June, 2021; v1 submitted 29 January, 2021; originally announced January 2021.
Comments: 25 pages. This is an extended version of the first part of the earlier preprint "Factor of iid Schreier decorations of transitive graphs''. Non-amenable results are split off into a separate preprint titled "Factor-of-iid balanced orientation of non-amenable graphs''
MSC Class: 05E18; 05C63; 37A30; 60C05
-
Some applications of Wagner's weighted subgraph counting polynomial
Abstract: We use Wagner's weighted subgraph counting polynomial to prove that the partition function of the anti-ferromagnetic Ising model on line graphs is real rooted and to prove that roots of the edge cover polynomial have length at most $4$. We moreover discuss how our results relate to efficient algorithms for approximately computing evaluations of these polynomials.
Submitted 20 September, 2021; v1 submitted 1 December, 2020; originally announced December 2020.
MSC Class: 05C35 (Primary) 05C31; 05C70; 05C80 (Secondary)
-
arXiv:2005.12107 [pdf, ps, other]
Atoms of the matching measure
Abstract: We prove that the matching measure of an infinite vertex-transitive connected graph has no atoms. Generalizing the results of Salez, we show that for an ergodic non-amenable unimodular random rooted graph with uniformly bounded degrees, the matching measure has only finitely many atoms. Ku and Chen proved the analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polyn… ▽ More
Submitted 25 May, 2020; originally announced May 2020.
Comments: 38 pages
-
Lee-Yang Zeros of the antiferromagnetic Ising Model
Abstract: We investigate the location of zeros for the partition function of the anti-ferromagnetic Ising Model, focusing on the zeros lying on the unit circle. We give a precise characterization for the class of rooted Cayley trees, showing that the zeros are nowhere dense on the most interesting circular arcs. In contrast, we prove that when considering all graphs with a given degree bound, the zeros are… ▽ More
Submitted 17 July, 2019; originally announced July 2019.
Comments: Includes large figures
-
arXiv:1812.07532 [pdf, ps, other]
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
Abstract: 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 tha… ▽ More
Submitted 5 April, 2021; v1 submitted 18 December, 2018; originally announced December 2018.
Comments: Some minor changes based on referee comments. Accepted for publication in AIHPD. 22 pages; 2 figures
Journal ref: Ann. Inst. Henri Poincaré Comb. Phys. Interact. 8 (2021), no. 3, pp. 459--489
-
Note on the zero-free region of the hard-core model
Abstract: In this paper we prove a new zero-free region for the partition function of the hard-core model, that is, the independence polynomials of graphs with largest degree $Δ$. This new domain contains the half disk $$D=\left\{ λ\in \mathbb{C}\ |\ \mathrm{Re}(λ)\geq 0, |λ|\leq \frac{7}{8}\tan \left( \fracπ{2(Δ-1)}\right)\right\}.$$
Submitted 3 April, 2020; v1 submitted 24 July, 2018; originally announced July 2018.
Comments: 7 pages, 1 figure
-
Some coefficient sequences related to the descent polynomial
Abstract: The descent polynomial of a finite $I\subseteq \mathbb{Z}^+$ is the polynomial $d(I,n)$, for which the evaluation at $n>\max(I)$ is the number of permutations on $n$ elements, such that $I$ is the set of indices where the permutation is descending. In this paper we will prove some conjectures concerning coefficient sequences of $d(I,n)$. As a corollary we will describe some zero-free regions for t… ▽ More
Submitted 15 January, 2019; v1 submitted 2 June, 2018; originally announced June 2018.
Comments: 21 pages, 9 figures
MSC Class: 05A05; 05E15
-
Invariant random subgroups of groups acting on rooted trees
Abstract: We investigate invariant random subgroups in groups acting on rooted trees. Let $\mathrm{Alt}_f(T)$ be the group of finitary even automorphisms of the $d$-ary rooted tree $T$. We prove that a nontrivial ergodic IRS of $\mathrm{Alt}_f(T)$ that acts without fixed points on the boundary of $T$ contains a level stabilizer, in particular it is the random conjugate of a finite index subgroup. Applying… ▽ More
Submitted 10 January, 2021; v1 submitted 17 January, 2018; originally announced January 2018.
Comments: Minor revision, accepted in Transactions of the AMS; 32 pages with Appendix, 4 figures
MSC Class: 20E08; 20B27; 05C25; 22D40
-
arXiv:1703.05685 [pdf, ps, other]
One more remark on the adjoint polynomial
Abstract: The adjoint polynomial of $G$ is \[h(G,x)=\sum_{k=1}^n(-1)^{n-k}a_k(G)x^k,\] where $a_k(G)$ denotes the number of ways one can cover all vertices of the graph $G$ by exactly $k$ disjoint cliques of $G$. In this paper we show the the adjoint polynomial of a graph $G$ is a simple transformation of the independence polynomial of another graph $\widehat{G}$. This enables us to use the rich theory of i… ▽ More
Submitted 7 April, 2017; v1 submitted 16 March, 2017; originally announced March 2017.
MSC Class: 05C31
-
arXiv:1703.05409 [pdf, ps, other]
On trees with real rooted independence polynomial
Abstract: The independence polynomial of a graph $G$ is \[I(G,x)=\sum\limits_{k\ge 0}i_k(G)x^k,\] where $i_k(G)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0(G)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees. In particular we will give a new proof of the real-rootedness of the independence polynomia… ▽ More
Submitted 15 March, 2017; originally announced March 2017.
MSC Class: Primary: 05C31; Secondory: 05C69; 05C30
-
arXiv:1409.2527 [pdf, ps, other]
Christoffel-Darboux type identities for independence polynomial
Abstract: In this paper we introduce some Christoffel-Darboux type identities for independence polynomials. As an application, we give a new proof of a theorem of M. Chudnovsky and P. Seymour, claiming that the independence polynomial of a claw-free graph has only real roots. Another application is related to a conjecture of Merrifield and Simmons.
Submitted 8 September, 2014; originally announced September 2014.
MSC Class: 05C31