BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let G be a triangle-free graph on n vertices with adjacency matrix eigenvalues μ1(G)≥μ2(G)≥⋯≥μn(G). In this paper we study the quantity μ1(G)+μn(G). We prove that for any triangle-free graph G we have μ1(G)+μn(G)≤(3−22)n. This was proved for regular graphs by Brandt, we show that the condition on regularity is not necessary. We also prove that among triangle-free strongly regular graphs the Higman-Sims graph achieves the maximum of nμ1(G)+μn(G).
The goal of this short paper to advertise the method of gauge transformations (aka holographic reduction, reparametrization) that is well-known in statistical physics and computer science, but less known in combinatorics. As an application of it we give a new proof of a theorem of A. Schrijver asserting that the number of Eulerian orientations of a d--regular graph on n vertices with even d is at least (2d/2(d/2d))n. We also show that a d--regular graph with even d has always at least as many Eulerian orientations as (d/2)--regular subgraphs.
Given a graph G with only even degrees let ε(G) denote the number of Eulerian orientations, and let h(G) denote the number of half graphs, that is, subgraphs F such that dF(v)=dG(v)/2 for each vertex v. Recently, Borbényi and Csikvári proved that ε(G)≥h(G) holds true for all Eulerian graphs with equality if and and only if G is bipartite. In this paper we give a simple new proof of this fact, and we give identities and inequalities for the number of Eulerian orientations and half graphs of a 2-cover of a graph G.
For a graph G on v(G) vertices let mk(G) denote the number of matchings of size k, and consider the partition function MG(λ)=∑k=0nmk(G)λk. In this paper we show that if G is a d--regular graph and 0<λ<(4d)−2, then v(G)1lnMG(λ)>v(Kd+1)1lnMKd+1(λ). The same inequality holds true if d=3 and λ<0.3575. More precise conjectures are also given.
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={λ∈C ∣ Re(λ)≥0,∣λ∣≤87tan(2(Δ−1)π)}.
Recently, M.\ Abért and T.\ Hubai studied the following problem. The chromatic measure of a finite simple graph is defined to be the uniform distribution on its chromatic roots. Abért and Hubai proved that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. They also showed that the normalized log of the chromatic polynomial converges to a harmonic real function outside a bounded disc. In this paper we generalize their work to a wide class of graph polynomials, namely, multiplicative graph polynomials of bounded exponential type. A special case of our results is that for any fixed complex number v0 the measures arising from the Tutte polynomial ZGn(z,v0) converge in holomorphic moments if the sequence (Gn) of finite graphs is Benjamini--Schramm convergent. This answers a question of Abért and Hubai in the affirmative. Even in the original case of the chromatic polynomial, our proof is considerably simpler.
We define the matching measure of a lattice L as the spectral measure of the tree of self-avoiding walks in L. We connect this invariant to the monomer-dimer partition function of a sequence of finite graphs converging to L. This allows us to express the monomer-dimer free energy of L in terms of the measure. Exploiting an analytic advantage of the matching measure over the Mayer series then leads to new, rigorous bounds on the monomer-dimer free energies of various Euclidean lattices. While our estimates use only the computational data given in previous papers, they improve the known bounds significantly.
A theorem of A. Schrijver asserts that a d-regular bipartite graph on 2n vertices has at least (dd−2(d−1)d−1)n perfect matchings. L. Gurvits gave an extension of Schrijver's theorem for matchings of density p. In this paper we give a stronger version of Gurvits's theorem in the case of vertex-transitive bipartite graphs. This stronger version in particular implies that for every positive integer k, there exists a positive constant c(k) such that if a d-regular vertex-transitive bipartite graph on 2n vertices contains a cycle of length at most k, then it has at least (dd−2(d−1)d−1+c(k))n perfect matchings. We also show that if (Gi) is a Benjamini--Schramm convergent graph sequence of vertex-transitive bipartite graphs, then v(Gi)lnpm(Gi) is convergent, where pm(G) and v(G) denote the number of perfect matchings and the number of vertices of G, respectively. We also show that if G is d-regular vertex-transitive bipartite graph on 2n vertices and mk(G) denote the number of matchings of size k, and M(G,t)=1+m1(G)t+m2(G)t2+⋯+mn(G)tn=∏k=1n(1+γk(G)t), where γ1(G)≤⋯≤γn(G), then γk(G)≥4(d−1)d2n2k2, and mn(G)mn−1(G)≤d2n2. The latter result improves on a previous bound of C. Kenyon, D. Randall and A. Sinclair. There are examples of d-regular bipartite graphs for which these statements fail to be true without the condition of vertex-transitivity.
Let H be a graph on n vertices and let the blow-up graph G[H] be defined as follows. We replace each vertex vi of H by a cluster Ai and connect some pairs of vertices of Ai and Aj if (vi,vj) was an edge of the graph H. As usual, we define the edge density between Ai and Aj as d(Ai,Aj)=∣Ai∣∣Aj∣e(Ai,Aj). We study the following problem. Given densities γij for each edge (i,j)∈E(H). Then one has to decide whether there exists a blow-up graph G[H] with edge densities at least γij such that one cannot choose a vertex from each cluster so that the obtained graph is isomorphic to H, i.e, no H appears as a transversal in G[H]. We call dcrit(H) the maximal value for which there exists a blow-up graph G[H] with edge densities d(Ai,Aj)=dcrit(H) ((vi,vj)∈E(H)) not containing H in the above sense. Our main goal is to determine the critical edge density and to characterize the extremal graphs.
In this paper we study several problems concerning the number of homomorphisms of trees. We give an algorithm for the number of homomorphisms from a tree to any graph by the Transfer-matrix method. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization of Bollobás and Tyomkyn's result concerning the number of walks in trees. Some other highlights of the paper are the following. Denote by hom(H,G) the number of homomorphisms from a graph H to a graph G. For any tree Tm on m vertices we give a general lower bound for hom(Tm,G) by certain entropies of Markov chains defined on the graph G. As a particular case, we show that for any graph G, exp(Hλ(G))λm−1≤hom(Tm,G), where λ is the largest eigenvalue of the adjacency matrix of G and Hλ(G) is a certain constant depending only on G which we call the spectral entropy of G. In the particular case when G is the path Pn on n vertices, we prove that hom(Pm,Pn)≤hom(Tm,Pn)≤hom(Sm,Pn), where Tm is any tree on m vertices, and Pm and Sm denote the path and star on m vertices, respectively. We also show that if Tm is any fixed tree and hom(Tm,Pn)>hom(Tm,Tn), for some tree Tn on n vertices, then Tn must be the tree obtained from a path Pn−1 by attaching a pendant vertex to the second vertex of Pn−1. All the results together enable us to show that $$ |\End(P_m)|\leq|\End(T_m)|\leq|\End(S_m)|, $$ where $\End(T_m)$ is the set of all endomorphisms of Tm (homomorphisms from Tm to itself).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.