Bond percolation on isoradial graphs: criticality and universality

In an investigation of percolation on isoradial graphs, we prove the criticality of canonical bond percolation on isoradial embeddings of planar graphs, thus extending celebrated earlier results for homogeneous and inhomogeneous square, triangular, and other lattices. This is achieved via the star–triangle transformation, by transporting the box-crossing property across the family of isoradial graphs. As a consequence, we obtain the universality of these models at the critical point, in the sense that the one-arm and $2j$ -alternating-arm critical exponents (and therefore also the connectivity and volume exponents) are constant across the family of such percolation processes. The isoradial graphs in question are those that satisfy certain weak conditions on their embedding and on their track system. This class of graphs includes, for example, isoradial embeddings of periodic graphs, and graphs derived from rhombic Penrose tilings.     

The Fermionic Observable in the Ising Model and the Inverse Kac–Ward Operator

We show that the critical Kac–Ward operator on isoradial graphs acts in a certain sense as the operator of s-holomorphicity, and we identify the fermionic observable for the spin Ising model as the inverse of this operator. This result is partially a consequence of a more general observation that the inverse Kac–Ward operator on any planar graph is given by what we call a fermionic generating function. We also present a general picture of the non-backtracking walk representation of the critical and supercritical inverse Kac–Ward operators on isoradial graphs.     

Discrete complex analysis on isoradial graphs

We study discrete complex analysis and potential theory on a large family of planar graphs, the so-called isoradial ones. Along with discrete analogues of several classical results, we prove uniform convergence of discrete harmonic measures, Green?s functions and Poisson kernels to their continuous counterparts. Among other applications, the results can be used to establish universality of the critical Ising and other lattice models.     

Scaling limit of isoradial dimer models and the case of triangular quadri-tilings

We consider dimer models on planar graphs which are bipartite, periodic and satisfy a geometric condition called isoradiality, defined in [R. Kenyon, The Laplacian and Dirac operators on critical planar graphs, Invent. Math. 150 (2) (2002) 409–439]. We show that the scaling limit of the height function of any such dimer model is a Gaussian free field. Triangular quadri-tilings were introduced in [B. de Tilière, Quadri-tilings of the plane, math.PR/0403324, Probab. Theory Related Fields, in press]; they are dimer models on a family of isoradial graphs arising from rhombus tilings. By means of two height functions, they can be interpreted as random interfaces in dimension 2+2. We show that the scaling limit of each of the two height functions is a Gaussian free field, and that the two Gaussian free fields are independent.     

Partition function of periodic isoradial dimer models

Isoradial dimer models were introduced in Kenyon (Invent Math 150(2):409–439, 2002)—they consist of dimer models whose underlying graph satisfies a simple geometric condition, and whose weight function is chosen accordingly. In this paper, we prove a conjecture of (Kenyon in Invent Math 150(2):409–439, 2002), namely that for periodic isoradial dimer models, the growth rate of the toroidal partition function has a simple explicit formula involving the local geometry of the graph only. This is a surprising feature of periodic isoradial dimer models, which does not hold in the general periodic dimer case (Kenyon et al. in Ann Math, 2006). Supported by Swiss National Fund under grant 47102009.     

Isoradial Bodies

In this paper we show that for any dimension $d \ge 2$ there exists a non-spherical strongly isoradial body, i.e., a non-spherical body of constant breadth, such that its orthogonal projections on any subspace has constant in- and circumradius. Besides the curiosity aspect of these bodies, they are highly relevant for the analysis of geometric inequalities between the radii and their extreme cases.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Rigidity of Quasicrystallic and <Emphasis Type="Italic">Z</Emphasis><Superscript><Emphasis Type="Italic">γ</Emphasis></Superscript>-Circle Patterns

The uniqueness of the orthogonal Z ^γ -circle patterns as studied by Bobenko and Agafonov is shown, given the combinatorics and some boundary conditions. Furthermore we study (infinite) rhombic embeddings in the plane which are quasicrystallic, that is, they have only finitely many different edge directions. Bicoloring the vertices of the rhombi and adding circles with centers at vertices of one of the colors and radius equal to the edge length leads to isoradial quasicrystallic circle patterns. We prove for a large class of such circle patterns which cover the whole plane that they are uniquely determined up to affine transformations by the combinatorics and the intersection angles. Combining these two results, we obtain the rigidity of large classes of quasicrystallic Z ^γ -circle patterns.     

一类点传递但边不传递的正则图及其覆盖图

利用轮子图构造出一类图,证明了这类图都是点传递但边不传递的正则图,并证明了通过覆盖的方法,可以使一类2m²(m>3,m为正整数)阶非边传递图变成对称图,这类对称图实际上是亚循环图.     

On cover-structure graphs

Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.     

Combinatorial optimization with 2-joins

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.     

Planar and infinite hypohamiltonian and hypotraceable graphs

Chvátal raised the question whether or not planar hypohamiltonian graphs exist and Grünbaum conjectured the nonexistence of such graphs. We shall describe an infinite class of planar hypohamiltonian graphs and infinite classes of planar hypotraceable graphs of connectivity two (resp. three). Infinite hypohamiltonian (resp. htpotraceable) graphs are also described. It is shown how the study of infinite hypotraceable graphs leads to a new infinite family of finite hypotraceable graphs.     

Chromatically unique graphs

We show that two infinite families of graphs are chromatically unique. The graphs in these families can be obtained from the wheel graphs by deleting some of the spoke edges. Also, we prove that certain related graphs are not chromatically unique.     

Tough spiders

Spider graphs are the intersection graphs of subtrees of subdivisions of stars. Thus, spider graphs are chordal graphs that form a common superclass of interval and split graphs. Motivated by previous results on the existence of Hamilton cycles in interval, split and chordal graphs, we show that every 3/2‐tough spider graph is hamiltonian. The obtained bound is best possible since there are (3/2 – ε)‐tough spider graphs that do not contain a Hamilton cycle. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 23–40, 2007     

Cartesian products of block graphs

Hamming graphs (being the Cartesian products of complete graphs) are known to be the quasi-median graphs not containing the 3-vertex path as a convex subgraph. Similarly, the Cartesian products of trees have been characterized among median graphs by a single forbidden convex subgraph. In this note a common generalization of these two results is given that characterizes the Cartesian products of block graphs.     

Enumeration of connected invariant graphs

Let h be a finite group acting on unlabeled graphs which does not change connectivity. Examples include edge reversal in directed graphs and permutations of colors in edge and/or vertex colored graphs. The generating functions of h-invariant (directed) graphs and h-invariant (weakly) connected (directed) graphs are discussed. This leads to a recursive formula for calculating the number of connected graphs when the total number of graphs is known. This is then applied to self-dual signed graphs, self-converse digraphs, and color cyclic graphs. Asymptotic expansions are also obtained. As expected, almost all of the above h-invariant graphs are connected and the asymptotic number of disconnected graphs has a simple interpretation.     

Enumerative Properties of Rooted Circuit Maps

In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps.     

Some flow-equivalent planar and non-planar graphs

We find three non-planar graphs which are flow-equivalent to planar graphs. It is also shown that some non-planar graphs are not flow-equivalent to any planar graph.     

End-transitive graphs

We investigate the structure of connected graphs, not necessarily locally finite, with infinitely many ends. We study end-transitive such graphs and such graphs with the property that the stabilizer of some end acts transitively on the vertices of the graph. In both cases we show that the graphs have a tree-like structure.