Quadri-tilings of the Plane

We introduce quadri-tilings and show that they are in bijection with dimer models on a family of graphs R ^* arising from rhombus tilings. Using two height functions, we interpret a sub-family of all quadri-tilings, called triangular quadri-tilings, as an interface model in dimension 2+2. Assigning “critical" weights to edges of R ^*, we prove an explicit expression, only depending on the local geometry of the graph R ^*, for the minimal free energy per fundamental domain Gibbs measure; this solves a conjecture of Kenyon (Invent Math 150:409–439, 2002). We also show that when edges of R ^* are asymptotically far apart, the probability of their occurrence only depends on this set of edges. Finally, we give an expression for a Gibbs measure on the set of all triangular quadri-tilings whose marginals are the above Gibbs measures, and conjecture it to be that of minimal free energy per fundamental domain.     

Vertices of given degree in series‐parallel graphs

We show that the numbers of vertices of a given degree k ≥ 1 in several kinds of series‐parallel labeled graphs of size n satisfy a central limit theorem with mean and variance proportional to n, and quadratic exponential tail estimates. We further prove a corresponding theorem for the number of nodes of degree two in labeled planar graphs. The proof method is based on generating functions and singularity analysis. In particular, we need systems of equations for multivariate generating functions and transfer results for singular representations of analytic functions. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

A Renormalization Group Method by Harmonic Extensions and the Classical Dipole Gas

In this paper, we develop a new renormalization group method, which is based on conditional expectations and harmonic extensions, to study functional integrals of small perturbations of Gaussian fields. In this new method, one integrates Gaussian fields inside domains at all scales conditioning on the fields outside these domains, and by the variation principle solves local elliptic problems. It does not rely on an a priori decomposition of the Gaussian covariance. We apply this method to the model of classical dipole gas on the lattice, and show that the scaling limit of the generating function with smooth test functions is the generating function of the renormalized Gaussian free field.     

Convex‐round graphs are circular‐perfect

We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal K_r‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002     

Geodesic Distance in Planar Graphs: An Integrable Approach

We discuss the enumeration of planar graphs using bijections with suitably decorated trees, which allow for keeping track of the geodesic distances between faces of the graph. The corresponding generating functions obey non-linear recursion relations on the geodesic distance. These are solved by use of stationary multi-soliton tau-functions of suitable reductions of the KP hierarchy. We obtain a unified formulation of the (multi-) critical continuum limit describing large graphs with marked points at large geodesic distances, and obtain integrable differential equations for the corresponding scaling functions. This provides a continuum formulation of two-dimensional quantum gravity, in terms of the geodesic distance. 2000 Mathematics Subject Classification: Primary—05C30; Secondary—05A15, 05C05, 05C12, 68R05     

Maximal planar graphs of diameter two

A maximal planar graph is a simple planar graph in which every face is a triangle. We show here that such graphs with maximum degree Δ and diameter two have no more than 3/2Δ + 1 vertices. We also show that there exist maximal planar graphs with diameter two and exactly [3/2Δ + 1] vertices.     

Universality in the 2D Ising model and conformal invariance of fermionic observables

It is widely believed that the celebrated 2D Ising model at criticality has a universal and conformally invariant scaling limit, which is used in deriving many of its properties. However, no mathematical proof has ever been given, and even physics arguments support (a priori weaker) M?bius invariance. We introduce discrete holomorphic fermions for the 2D Ising model at criticality on a large family of planar graphs. We show that on bounded domains with appropriate boundary conditions, those have universal and conformally invariant scaling limits, thus proving the universality and conformal invariance conjectures.     

Gaussian free fields for mathematicians

The d-dimensional Gaussian free field (GFF), also called the (Euclidean bosonic) massless free field, is a d-dimensional-time analog of Brownian motion. Just as Brownian motion is the limit of the simple random walk (when time and space are appropriately scaled), the GFF is the limit of many incrementally varying random functions on d-dimensional grids. We present an overview of the GFF and some of the properties that are useful in light of recent connections between the GFF and the Schramm–Loewner evolution. Partially supported by NSF grant DMS0403182.     

Ups and Downs of First Order Sentences on Random Graphs

whenever is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization. Received October 2, 1998     

On scaling limits and Brownian interlacements

We consider continuous time interlacements on ? ^d , d ≥ 3, and investigate the scaling limit of their occupation times. In a suitable regime, referred to as the constant intensity regime, this brings Brownian interlacements on ? ^d into play, whereas in the high intensity regime the Gaussian free field shows up instead. We also investigate the scaling limit of the isomorphism theorem of [40]. As a by-product, when d = 3, we obtain an isomorphism theorem for Brownian interlacements.     

Singularity among selfsimilar Gaussian random fields with different scaling parameters and others

Abstract

It is shown in this paper that the probability measures generated by selfsimilar Gaussian random fields are mutually singular, whenever they have different scaling parameters. So are those generated from a selfsimilar Gaussian random field and a stationary Gaussian random field. Certain conditions are also given for the singularity of the probability measures generated from two Gaussian random fields whose covariance functions are Schoenberg–Lévy kernels, and for those from stationary Gaussian random fields with spectral densities.     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

Fast and exact synthesis of some operator scaling Gaussian random fields

Operator scaling Gaussian random fields, as anisotropic generalizations of self-similar fields, know an increasing interest for theoretical studies in the literature. However, up to now, they were only defined through stochastic integrals, without explicit covariance functions. In this paper we exhibit explicit covariance functions, as anisotropic generalizations of fractional Brownian fields ones, and define corresponding Operator scaling Gaussian random fields. This allows us to propose a fast and exact method of simulation in dimension 2 based on the circulant embedding matrix method, following ideas of Stein [34] for fractional Brownian surfaces syntheses. This is a first piece of work to popularize these models in anisotropic spatial data modeling.     

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

Planarity and Edge Poset Dimension

Different areas of discrete mathematics lead to instrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all of the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensionalN-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.     

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability.     

Scaling limits for internal aggregation models with multiple sources

We study the scaling limits of three different aggregation models on ℤ ^d : internal DLA, in which particles perform random walks until reaching an unoccupied site; the rotor-router model, in which particles perform deterministic analogues of random walks; and the divisible sandpile, in which each site distributes its excess mass equally among its neighbors. As the lattice spacing tends to zero, all three models are found to have the same scaling limit, which we describe as the solution to a certain PDE free boundary problem in ℝ ^d . In particular, internal DLA has a deterministic scaling limit. We find that the scaling limits are quadrature domains, which have arisen independently in many fields such as potential theory and fluid dynamics. Our results apply both to the case of multiple point sources and to the Diaconis-Fulton smash sum of domains.     

The Laplacian and Dirac operators on critical planar graphs

On a periodic planar graph whose edge weights satisfy a certain simple geometric condition, the discrete Laplacian and Dirac operators have the property that their determinants and inverses only depend on the local geometry of the graph. We obtain explicit expressions for the logarithms of the (normalized) determinants, as well as the inverses of these operators. We relate the logarithm of the determinants to the volume plus mean curvature of an associated hyperbolic ideal polyhedron. In the associated dimer and spanning tree models, for which the determinants of the Dirac operator and the Laplacian respectively play the role of the partition function, this allows us to compute the entropy and correlations in terms of the local geometry. In addition, we define a continuous family of special discrete holomorphic functions which, via convolutions, gives a general process for constructing discrete holomorphic functions and discrete harmonic functions on critical planar graphs. Oblatum 6-III-2002 & 12-VI-2002?Published online: 6 August 2002     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.