The graphs of polytopes with involutory automorphisms

Steinitz’ theorem states that a graph is the graph of a 3-dimensional convex polytope if and only if it is planar and 3-connected. Grünbaum has shown that Steinitz’ proof can be modified to characterize the graphs of polytopes that are centrally symmetric or have a plane of symmetry. We show how to modify Steinitz’ proof to take care of the remaining involutory case—polytopes that are symmetric about a line. Research supported by NSF Grant GP-3470.     

On mappings whose sum is monotone

Proposition 1 of this article points at a gap in the proof of Kuhlmann’s characterization of algebraically maximal valued fields [2]. The author [1] showed how to fill this gap. His arguments involved tools of mathematical logic and infinite combinatorics. Proposition 2 of this article provides us with a simple proof of the key fact of Kuhlmann’s characterization.     

Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (O. V. Borodin et al., 2002). This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-colorable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (O. V. Borodin, A. V. Kostochka and D. R. Woodall, 1999) and acyclically 3-choosable (O. V. Borodin et. al, 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of k-cycles, where 4 ≤ k ≤ S. Here, we prove that every planar graph without cycles of length from 4 to 12 is acyclically 3-choosable.     

A Note on Schnyder’s Theorem

We give an alternate proof of Schnyder’s Theorem, that the incidence poset of a graph G has dimension at most three if and only if G is planar.     

On the convergence of circle packings to the Riemann map

Rodin and Sullivan (1987) proved Thurston’s conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby providing a refreshing geometric view of Riemann’s Mapping Theorem. We now present a new proof of the Rodin–Sullivan theorem. This proof is based on the argument principle, and has the following virtues. 1. It applies to more general packings. The Rodin–Sullivan paper deals with packings based on the hexagonal combinatorics. Later, quantitative estimates were found, which also worked for bounded valence packings. Here, the bounded valence assumption is unnecessary and irrelevant. 2. Our method is rather elementary, and accessible to non-experts. In particular, quasiconformal maps are not needed. Consequently, this gives an independent proof of Riemann’s Conformal Mapping Theorem. (The Rodin–Sullivan proof uses results that rely on Riemann’s Mapping Theorem.) 3. Our approach gives the convergence of the first and second derivatives, without significant additional difficulties. While previous work has established the convergence of the first two derivatives for bounded valence packings, now the bounded valence assumption is unnecessary. Oblatum 15-V-1995 & 13-XI-1995     

Transboundary extremal length

We introduce two basic notions, ‘transboundary extremal length’ and ‘fat sets’, and apply these concepts to the theory of conformal uniformization of multiply connected planar domains. A new short proof is given to Koebe's conjecture in the countable case: every planar domain with countably many boundary components is conformally equivalent to a circle domain. This theorem is further generalized in two direction. We show that the same statement is true for a wide class of domains with uncountably many boundary components, in particular for domains bounded byK-quasicircles and points. Moreover, these domains admit more general uniformizations. For example, every circle domain is conformally equivalent to a domain whose complementary components are heart-shapes and points. Incumbent of the William Z. and Eda Bess Novick Career Development Chair. Supported by NSF grant DMS-9112150.     

Schnyder Woods and Orthogonal Surfaces

In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the dimension theory of orders. Orthogonal surfaces explain connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says, that the face lattice of a 3-polytope minus one face has order dimension three. Our proof yields a linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.     

A Simple Recurrence for Covers of the Sphere With Branch Points of Arbitrary Ramification

The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800’s. This problem translates combinatorially into factoring a permutation of specified cycle type, with certain conditions on the cycle types of the factors, such as minimality and transitivity. Goulden and Jackson have given a proof for the number of minimal, transitive factorizations of a permutation into transpositions. This proof involves a partial differential equation for the generating series, called the Join-Cut equation. Recently, Bousquet-Mélou and Schaeffer have found the number of minimal, transitive factorizations of a permutation into arbitrary unspecified factors. This was proved by a purely combinatorial argument, based on a direct bijection between factorizations and certain objects called m-Eulerian trees. In this paper, we give a simple partial differential equation for Bousquet-Mélou and Schaeffer’s generating series, and for Goulden and Jackson’s generating series, as well as a new proof of the result by Bousquet-Mélou and Schaeffer. We apply algebraic methods based on Lagrange’s theorem, and combinatorial methods based on a new use of Bousquet-Mélou and Schaeffer’s m-Eulerian trees. Supported by a Discovery Grant from NSERC. Research supported by a Postgraduate Scholarship from NSERC. Received October 8, 2005     

Collapsing irreducible 3-manifolds with nontrivial fundamental group

Let M be a closed, orientable, irreducible, non-simply connected 3-manifold. We prove that if M admits a sequence of Riemannian metrics which volume-collapses and whose sectional curvature is locally controlled, then M is a graph manifold. This is the last step in Perelman’s proof of Thurston’s Geometrisation Conjecture.     

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.     

Some remarks on interval graphs

Using simplicial decompositions a new and simple proof of Lekkerkerker-Boland’s criterion for interval graphs is given. Also the infinite case is considered, and the problem is tackled to what extent the representation of a graph as an interval graph is unique. Dedicated to Tibor Gallai on his seventieth birthday     

SUPER EDGE-CONNECTIVITY OF DE BRUIJN AND KAUTZ UNDIRECTED GRAPHS

The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks. This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lue and Zhang‘s result on super edge-connectivity of the de Bruijn undirected graph.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Generalized Kneser coloring theorems with combinatorial proofs

The Kneser conjecture (1955) was proved by Lovász (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matoušek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization by (hyper)graph coloring theorems of Dol’nikov, Alon-Frankl-Lovász, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver’s theorem. Oblatum 17-IV-2001 & 12-IX-2001?Published online: 19 November 2001 An erratum to this article is available at .     

On dynamics of fluids in astrophysics

The object of this article is to show the existence of weak solutions to the Navier–Stokes–Fourier Poisson system on (in general) unbounded domains. The topic is a natural continuation of the author’s results on the existence of weak solutions to the problem on Lipschitz domains and to the Oxenius system on unbounded domains. Technique of the proof is based on the tools developed in a series of works by Feireisl (Oxford lecture series in mathematics and its applications, 26, Oxford University Press, Oxford) and others during the recent years. The weak solution’s sensitivity to a change of the domain is discussed as well.     

Nodal lines of eigenfunctions of the fixed membrane problem in general convex domains

We describe the boundary behavior of the nodal lines of eigenfunctions of the fixed membrane problem in convex, possibly nonsmooth, domains. This result is applied to the proof of Payne’s conjecture on the nodal line of second eigenfunctions [P1], by removing theC ^∞ smoothness assumption which is present in the original proof of Melas [M].     

A short proof of Halin’s grid theorem

We give a short proof of Halin’s theorem that every thick end of a graph contains the infinite grid.     

A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.