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

Showing math.COShow all

19 papers · 1 filter

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

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

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…

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.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.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.CO2018★ 3 cited

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

Ferenc Bencs, Ewan Davies, Viresh Patel +1

For a graph $G = (V, E)$ , $k \in 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_{\su…

math.CO2018

Note on the zero-free region of the hard-core model

Ferenc Bencs, Péter Csikvári

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

math.CO2018

Some coefficient sequences related to the descent polynomial

Ferenc Bencs

The descent polynomial of a finite $I \subseteq Z^{+}$ is the polynomial $d (I, n)$ , for which the evaluation at $n > max (I)$ is the number of permutations on $n$ elements, such…

math.CO2017★ 1 cited

One more remark on the adjoint polynomial

Ferenc Bencs

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

math.CO2017★ 3 cited

On trees with real rooted independence polynomial

Ferenc Bencs

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)=…

math.CO2014

Christoffel-Darboux type identities for independence polynomial

Ferenc Bencs

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. Seymou…

Sustainable trees

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

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

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

Random cluster model on regular graphs

On the location of chromatic zeros of series-parallel graphs

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

Evaluations of Tutte polynomials of regular graphs

Upper bound for the number of spanning forests of regular graphs

Some applications of Wagner's weighted subgraph counting polynomial

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

Note on the zero-free region of the hard-core model

Some coefficient sequences related to the descent polynomial

One more remark on the adjoint polynomial

On trees with real rooted independence polynomial

Christoffel-Darboux type identities for independence polynomial

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