Connectivity,graph minors,and subgraph multiplicity

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) times as a subgraph of the K_b,c-free graphs, b ≥ c and c ≤ 4, iff G is c-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.     

Harmonic functions of general graph Laplacians

We study harmonic functions on general weighted graphs which allow for a compatible intrinsic metric. We prove an \(L^{p}\) Liouville type theorem which is a quantitative integral \(L^{p}\) estimate of harmonic functions analogous to Karp’s theorem for Riemannian manifolds. As corollaries we obtain Yau’s \(L^{p}\) -Liouville type theorem on graphs, identify the domain of the generator of the semigroup on \(L^{p}\) and get a criterion for recurrence. As a side product, we show an analogue of Yau’s \(L^{p}\) Caccioppoli inequality. Furthermore, we derive various Liouville type results for harmonic functions on graphs and harmonic maps from graphs into Hadamard spaces.     

Normalized graph Laplacians for directed graphs

We consider the normalized Laplace operator for directed graphs with positive and negative edge weights. This generalization of the normalized Laplace operator for undirected graphs is used to characterize directed acyclic graphs. Moreover, we identify certain structural properties of the underlying graph with extremal eigenvalues of the normalized Laplace operator. We prove comparison theorems that establish a relationship between the eigenvalues of directed graphs and certain undirected graphs. This relationship is used to derive eigenvalue estimates for directed graphs. Finally we introduce the concept of neighborhood graphs for directed graphs and use it to obtain further eigenvalue estimates.     

Eulerian and even-face ribbon graph minors

In this paper, we introduce Eulerian and even-face ribbon graph minors. These minors preserve Eulerian and even-face properties of ribbon graphs, respectively. We then characterize Eulerian, even-face, plane Eulerian and plane even-face ribbon graphs using these minors.     

Symplectic packings and algebraic geometry

Oblatum 9-XI-1992 & 17-VI-1993     

Volume growth and spectrum for general graph Laplacians

We prove estimates relating exponential or sub-exponential volume growth of weighted graphs to the bottom of the essential spectrum for general graph Laplacians. The volume growth is computed with respect to a metric adapted to the Laplacian, and use of these metrics produces better results than those obtained from consideration of the graph metric only. Conditions for absence of the essential spectrum are also discussed. These estimates are shown to be optimal or near-optimal in certain settings and apply even if the Laplacian under consideration is an unbounded operator.     

Symplectic geometry and dissipative differential operators

Everitt and Markus characterized the domains of self-adjoint differential operators in terms of Lagrangian subspaces of complex symplectic spaces. In this paper we define Dissipative and strictly Dissipative subspaces for complex symplectic spaces and characterize the domains of dissipative and strictly dissipative differential operators in terms of these subspaces.     

On fixing edges in graph minors

An area of much recent research activity has been involved with tying the presence of certain minors in a matroid to specific elements of this matroid. The aim of this paper is to show that there are exactly two 3-connected simple graphsG with at least four edges and the property that ifH is a 3-connected simple graph havingG as a minor ande andf are edges ofH, thenH has a minor isomorphic toG which containse andf in its edge set. Some extensions of this result are also considered.     

Excluded checkerboard colourable ribbon graph minors

Motivated by the Eulerian ribbon graph minors, in this paper we introduce the notion of checkerboard colourable minors for ribbon graphs and its dual: bipartite minors for ribbon graphs. Motivated by the bipartite minors of abstract graphs, another bipartite minors for ribbon graphs, i.e. the bipartite ribbon graph join minors are also introduced. Using these minors then we give excluded minor characterizations of the classes of checkerboard colourable ribbon graphs, bipartite ribbon graphs, plane checkerboard colourable ribbon graphs and plane bipartite ribbon graphs.     

Continuum versus discrete networks,graph Laplacians,and reproducing kernel Hilbert spaces

Motivated by applications to machine learning, we construct a reversible and irreducible Markov chain whose state space is a certain collection of measurable sets of a chosen l.c.h. space $\mathfrak{X}$. We study the resulting network (connected undirected graph), including transience, Royden and Riesz decompositions, and kernel factorization. We describe a construction for Hilbert spaces of signed measures which comes equipped with a new notion of reproducing kernels and there is a unique solution to a regularized optimization problem involving the approximation of $L^2$ functions by functions of finite energy. The latter has applications to machine learning (for Markov random fields, for example).     

Symplectic geometry of constrained optimization

In this paper, we discuss geometric structures related to the Lagrange multipliers rule. The practical goal is to explain how to compute or estimate the Morse index of the second variation. Symplectic geometry allows one to effectively do it even for very degenerate problems with complicated constraints. The main geometric and analytic tool is an appropriately rearranged Maslov index. We try to emphasize the geometric framework and omit analytic routine. Proofs are often replaced with informal explanations, but a well-trained mathematician will easily rewrite them in a conventional way. We believe that Vladimir Arnold would approve of such an attitude.     

Symplectic geometry of semisimple orbits

Let G be a complex semisimple group, T G a maximal torus and B a Borel subgroup of G containing T. Let Ω be the Kostant-Kirillov holomorphic symplectic structure on the adjoint orbit O = Ad(G)c G/Z(c), where c Lie(T), and Z(c) is the centralizer of c in G. We prove that the real symplectic form Re Ω (respectively, Im Ω) on O is exact if and only if all the eigenvalues ad(c) are real (respectively, purely imaginary). Furthermore, each of these real symplectic manifolds is symplectomorphic to the cotangent bundle of the partial flag manifold G/Z(cc)B, equipped with the Liouville symplectic form. The latter result is generalized to hyperbolic adjoint orbits in a real semisimple Lie algebra.     

The geometry of products of minors

We consider the Newton polytope Σ(m,n) of the product of all minors of an m× n matrix of indeterminates. Using the fact that this polytope is the secondary polytope of the product Δ _m-1 ×Δ _n-1 of simplices, and thus has faces corresponding to coherent polyhedral subdivisions of Δ _m-1 ×Δ _n-1 , we study facets of Σ(m,n) , which correspond to the coarsest, nontrivial such subdivisions. We make use of the relation between secondary and fiber polytopes, which in this case gives a representation of Σ(m,n) as the Minkowski average of all m × n transportation polytopes. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p231.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received August 7, 1996, and in revised form April 4, 1997.     

An accessibility theorem for infinite graph minors

We prove the following recent conjecture of Halin. Let Γ₀ be the class of all graphs, and for every ordinal μ > 0 let Γ_μ be the class of all graphs containing infinitely many disjoint connected graphs from Γ_λ, for every λ < μ. Then a graph lies in all these classes Γ_μ if and only if it contains a subdivision of the infinite binary tree. Published by John Wiley & Sons, Inc., 2000 J Graph Theory 35: 273–277, 2000     

A characterization of some graph classes using excluded minors

In this article we present a structural characterization of graphs without K ₅ and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characterization in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown. Communicated by Attila Pethő