Ferenc Bencs

activity

20142026

most citedFactor-of-iid Schreier decorations of lattices in Euclidean spaces

8 citations · 33 across the 25 of their papers we have counts for

collaborators

32 papers

math.CO2026

Sustainable trees

Ferenc Bencs, Maarten van Dijk, Krystal Guo

Let $X$ be a connected graph and let $λ_{1} (X)$ denote the spectral radius of its adjacency matrix. An edge $e$ of $X$ is sustainable if it can be deleted and replaced by a non-edge…

math.PR2026

On the self-intersection time of non-backtracking random walks

Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ \geq 3$ we show that the expected self-intersection time i…

math.CO2026

On the complex zeros and the computational complexity of approximating the reliability polynomial

Ferenc Bencs, Chiara Piombi, Guus Regts

In this paper we relate the location of the complex zeros of the reliability polynomial to parameters at which a certain family of rational functions derived from the reliability p…

cs.DS2025

On zeros and algorithms for disordered systems: mean-field spin glasses

Ferenc Bencs, Brice Huang, Daniel Z. Lee +2

Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statisti…

cs.DS2025

Barvinok's interpolation method meets Weitz's correlation decay approach

Ferenc Bencs, Guus Regts

In this paper we take inspiration from Weit'z algorithm for approximating the independence polynomial to provide a new algorithm for computing the coefficients of the Taylor series…

math.CO2025

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs

Ferenc Bencs, Guus Regts

We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $χ_{G} (x)$ , lie inside the disk centered at $0$ of radius $4.25Δ (G)$ , where $Δ (G)$ denotes the maxim…

math.CO2024

Number of Eulerian orientations for Benjamini--Schramm convergent graph sequences

Ferenc Bencs, Márton Borbényi, Péter Csikvári

For a graph $G$ let $ε (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 Euleria…

math.CO2024

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

Ferenc Bencs, Khallil Berrekkal, Guus Regts

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 $U \subset C$ that contains the i…

math.CO2024★ 1 cited

Approximating the volume of a truncated relaxation of the independence polytope

Ferenc Bencs, Guus Regts

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 poly…

math.PR2023

Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees

Ferenc Bencs, Khallil Berrekkal, Guus Regts

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, Ma…

math.CO2023★ 1 cited

Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs

Ferenc Bencs, Pjotr Buys

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 de…

cs.CC2022

Approximating the chromatic polynomial is as hard as computing it exactly

Ferenc Bencs, Jeroen Huijben, Guus Regts

We show that for any non-real algebraic number $q$ such that $∣ q - 1∣ > 1$ or $ℜ (q) > \frac{3}{2}$ it is \textsc{\#P}-hard to compute a multiplicative (resp. additive) approximation to…

math.CO2022★ 3 cited

Random cluster model on regular graphs

Ferenc Bencs, Márton Borbényi, Péter Csikvári

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) = A \subseteq E (G) \sum q^{k (A)} w^{∣ A ∣},$ where $k (A)$ denotes…

math.CO2022

On the location of chromatic zeros of series-parallel graphs

Ferenc Bencs, Jeroen Huijben, Guus Regts

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∣ \leq 1$ , we show d…

cs.DM2022

On complex roots of the independence polynomial

Ferenc Bencs, Péter Csikvári, Piyush Srivastava +1

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 vani…

math.PR2022★ 2 cited

Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $Δ$ -regular tree for large $Δ$

Ferenc Bencs, David de Boer, Pjotr Buys +1

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 interac…

math.CO2021★ 3 cited

The limit of the zero locus of the independence polynomial for bounded degree graphs

Ferenc Bencs, Pjotr Buys, Han Peters

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…

math.PR2021★ 2 cited

Factor-of-iid balanced orientation of non-amenable graphs

Ferenc Bencs, Aranka Hrušková, László Márton Tóth

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…

math.CO2021

Evaluations of Tutte polynomials of regular graphs

Ferenc Bencs, Péter Csikvári

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$ …

math.CO2021

Upper bound for the number of spanning forests of regular graphs

Ferenc Bencs, Péter Csikvári

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…

math.MG2021

Extremizers and stability of the Betke--Weil inequality

Ferenc A. Bartha, Ferenc Bencs, Károly J. Böröczky +1

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/ (63) L (K)^{2}$ , where $L (K)$ is the perimete…

math.PR2021★ 8 cited

Factor-of-iid Schreier decorations of lattices in Euclidean spaces

Ferenc Bencs, Aranka Hrušková, László Márton Tóth

A Schreier decoration is a combinatorial coding of an action of the free group $F_{d}$ on the vertex set of a $2 d$ -regular graph. We investigate whether a Schreier decoration exists…

math.CO2020

Some applications of Wagner's weighted subgraph counting polynomial

Ferenc Bencs, Péter Csikvári, Guus Regts

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 roo…

math.PR2020★ 1 cited

Atoms of the matching measure

Ferenc Bencs, András Mészáros

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 unimod…

Sustainable trees

On the self-intersection time of non-backtracking random walks

On the complex zeros and the computational complexity of approximating the reliability polynomial

On zeros and algorithms for disordered systems: mean-field spin glasses

Barvinok's interpolation method meets Weitz's correlation decay approach

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs

Number of Eulerian orientations for Benjamini--Schramm convergent graph sequences

Deterministic approximate counting of colorings with fewer than 2Δ colors via absence of zeros

Approximating the volume of a truncated relaxation of the independence polytope

Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees

Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs

Approximating the chromatic polynomial is as hard as computing it exactly

Random cluster model on regular graphs

On the location of chromatic zeros of series-parallel graphs

On complex roots of the independence polynomial

Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite Δ-regular tree for large Δ

The limit of the zero locus of the independence polynomial for bounded degree graphs

Factor-of-iid balanced orientation of non-amenable graphs

Evaluations of Tutte polynomials of regular graphs

Upper bound for the number of spanning forests of regular graphs

Extremizers and stability of the Betke--Weil inequality

Factor-of-iid Schreier decorations of lattices in Euclidean spaces

Some applications of Wagner's weighted subgraph counting polynomial

Atoms of the matching measure

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $Δ$ -regular tree for large $Δ$