Program

Time	January. 10
12:00-12:50	Registration
13:00-14:00	James R. Lee “Eigenvalues of the Laplacian, multi-flows, and metric uniformization”
14:10-15:10	James R. Lee “Multi-way spectral partitioning and higher-order Cheeger inequalities”
15:10-15:40	Tea break
15:40-16:40	Masato Mimura “Verifiable expander”
16:50-17:50	Atsushi Kasue “Kuramochi boundaries of transient networks”
18:00-	Banquet (5th floor)
Time	January. 11
9:30-10:30	Hiroki Sako “Sequence of finite metric spaces : amenability and connectivity”
10:40-11:40	Hiroshi Hirai “Some combinatorial optimization problems related to metric spaces of nonpositive curvature”
13:00-14:00	Konrad Polthier “Discrete Minimal Surfaces based on Catmull-Clark Finite Elements I”
14:10-15:10	Konrad Polthier “Discrete Minimal Surfaces based on Catmull-Clark Finite Elements II”
15:10-16:00	Tea break & Poster session
16:00-16:30	Masashi Yasumoto “Discretization of linear Weingarten surfaces with Weierstrass-type representations”
16:40-17:40	Wayne Rossman “Discretization of general linear Weingarten surfaces”
Time	January. 12
9:30-10:30	Kenji Kajiwara “Integrable Discrete Deformations of Discrete Curves”
10:40-11:40	Ken-ichi Maruno “Discretization of integrable systems and self-adaptive moving mesh schemes”
11:50-12:50	Shoichi Fujimori “Degenerate limits of triply periodic minimal surfaces of genus 3 ”

Program & Abstract (PDF)

Jan. 10

James R. Lee (University of Washington)

Title: Eigenvalues of the Laplacian, multi-flows, and metric uniformization

Abstract:

The study of eigenvalues of the Laplace operator on graphs and manifolds has a long and rich history.  In the Riemannian setting, conformal uniformization is a powerful tool for understanding the spectrum of the Laplace-Beltrami operator on surfaces.  Even though graphs do not have an inherent conformal structure, we will introduce a form of metric uniformization that allows one to deform the underlying geometry by variational methods.

The uniformization approach allows us to resolve conjectures of Spielman and Teng about the spectrum of planar graphs and their generalizations.  In particular, one can provide formal guarantees on the efficacy of widely-used spectral algorithms for graph partitioning.  This answers positively a question of Gromov on whether there is a generalization of conformal techniques to minor-closed families of graphs that recovers the separator theorem of Alon, Seymour, and Thomas.  One can show that the theorems for graphs actually imply corresponding results for surfaces.  Thus as a special case, we recover Korevaar's bounds on the spectrum of compact surfaces.

James R. Lee (University of Washington)

Title: Multi-way spectral partitioning and higher-order Cheeger inequalities

Abstract:

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph.  Cheeger’s inequality and its variants provide a robust version of this fact for multiplicity 2.  It has been conjectured that an analogous characterization holds for higher multiplicities:  There are k small eigenvalues if and only if the vertex set of the graph can be partitioned into k sets with small boundary.

In the setting of mathematical physics, Simon and Hoegh-Krohn (1972) asked whether every hyper-bounded Markov operator has a spectral gap.  Much later, Laurent Miclo showed that a positive answer to the first conjecture yields a positive answer to the second.  In joint work with Oveis-Gharan and Trevisan, we prove Miclo's higher-order Cheeger conjecture.  The proof is based on an eigenfunction localization method using random partitions of metric spaces.  The argument is constructive and yields an algorithm for multi-way spectral partitioning that appears to work well in practice.  Moreover, the study of higher-order Cheeger inequalities has some striking applications in computational complexity theory.

Masato Mimura (Tohoku University)

Title: Verifiable expander

Abstract:

We say an infinite connected graph Gamma is a verifiable expander if any finite connected graph Lambda which ``locally looks the same as Gamma" is an expander. That means, there exists a universal bound from below of the first positive Laplace eigenvalues of such Lambda. We will discuss a recent development on this notion.

Atsushi Kasue (Kanazawa University)

Title: Kuramochi boundaries of transient networks

Abstract:

We study functions of finite Dirichlet sum on a transient network and show that a family of the Dirichlet forms induced on the boundaries of finite subnetworks converges in a certain variational sense to the Dirichlet form induced by the random walk on the Kuramochi boundary of the network, if the subnetworks increase and exhaust the whole network.

Jan. 11

Hiroki Sako (Niigata University)

Title: Sequence of finite metric spaces : amenability and connectivity

Abstract:

I will give a talk on discrete metric spaces, especially paying attention on disjoint unions of finite metric spaces. Among them, one having high connectivity is called an expander sequence. The item attracts not only mathematicians but also computer scientists. The objects relate to construction of networks and error correcting codes. We will focus on mathematical structure of uniformly locally finite metric spaces. It has been already known that a space cannot satisfy both of the following:

i) Coarse amenability,

ii) Containing an expander sequence.

I would like to show that every uniformly locally finite metric space has exactly one of i) or a little weaker condition than ii). In the proof, a Banach space of continuous linear operators plays a key role.

Hiroshi Hirai (University of Tokyo)

Title: Some combinatorial optimization problems related to metric spaces of nonpositive curvature.

Abstract:

The max-flow min-cut theorem, due to Ford-Fulkerson, says that in a network with terminal pair s,t, the maximum value of an (s,t)-flow  is equal to the minimum capacity of an (s,t)-cut. This theorem is one of most fundamental theorems in combinatorial optimization and graph theory. In this talk, we will discuss some generalizations of this theorem, and explain interesting connections to nonpositively-curved metric spaces.

(i) Multicommodity flow problem:

There are several generalizations of the max-flow min-cut theorem to “multiflow” settings. For a class of multiflow problems, the dual problem, which corresponds to “min-cut” in the single flow setting, is formulated as a location problem on a CAT(0) B_2 complex, called a "folder complex". The study of this formulation has brought significant contributions to several unsolved problems in multiflow theory.

(ii) Multifacility location problem (0-extension problem):

Problems of locating several facilities on graphs (or metric spaces) have numerous applications in operation research, machine learning and computer vision. Multifaclity location problem (or 0-extension problem) is an important special case where the cost of a location is given by a linear function on distances between facilities. The computation complexity of this problem depends on the underlying graph G. Recently the following dichotomy theorem was established: 

If G is an "orientable modular graph", then the problem is polynomial time solvable (Hirai SODA13). Otherwise it is NP-hard (Karzanov 98).

The idea behind the proof of the polynomial time solvability is formulating the problem as an optimization problem on a certain metrized complex constructed from orientable modular graph G. It turned out that this complex is an "orthoscheme complex” introduced by Brady-McCammond in geometric group theory.

Joint with J. Chalopin, V. Chepoi, and D. Osajda, we showed that several non-positively curved complexes are constructed from orientable modular graphs. Examples include CAT(0)-cube complexes and Euclidean buildings of type C.

Konrad Polthier (Freie Universität Berlin)

Title: Discrete Minimal Surfaces based on Catmull-Clark Finite Elements I & II

Abstract:

We present a novel concept for discrete minimal surfaces based on Catmull-Clark finite elements. These surfaces are globally C1 though determined by a discrete control grid. We will report about the theoretical setup and provide several examples of these discrete minimal surfaces. A special advantage of this new discretization scheme is the uniform integration of discrete differential geometry, finite element analysis and computer aided design. Joint work with Anna Wawrzinek.

Masashi Yasumoto (Kobe University)

Title: Discretization of linear Weingarten surfaces with Weierstrass-type representations

Abstract:

In this talk we discretize linear Weingarten surfaces in non-Euclidean spaceforms given by Weierstrass-type representations. In particular, discretizations of maximal surfaces in Lorentz-Minkowski 3-space and linear Weingarten surfaces of Bryant and Bianchi type are introduced. Furthermore, we compare smooth, discrete and semi-discrete surfaces with the same curvature conditions. This talk is partly based on the joint work with Wayne Rossman, and will be highly related to the talk by Wayne Rossman that follows it.

Wayne Rossman (Kobe University)

Title: Discretization of general linear Weingarten surfaces

Abstract:

Continuing from the previous talk by Masashi Yasumoto, we will consider how to discretize a more general class of surfaces, including those that do not have Weierstrass-type representations. We will see how general discrete linear Weingarten surfaces can be defined using constant conserved quantities of associated flat connections as a tool. Then, since smooth linear Weingarten surfaces typically have singularities (such as cuspidal edges, swallowtails, cuspidal cross-caps, etc), we will examine how to define corresponding singularities in the discretized case.

Jan. 12

Kenji Kajiwara (Kyushu University)

Title: Integrable Discrete Deformations of Discrete Curves

Abstract:

We present some results on integrable discrete deformations of space/plane discrete curves in various settings, including: (i) isoperimetric deformation of plane curves (discrete mKdV equation) (ii) conformal deformation of plane curves (discrete Burgers equation) (iii) torsion-preserving deformation of space discrete curves of constant torsion (discrete mKdV and discrete sine-Gordon equation) (iv) curvature-preserving deformation of space discrete curves of constant curvature (discrete mKdV and discrete sine-Gordon equation).

Ken-ichi Maruno (Waseda University)

Title: Discretization of integrable systems and self-adaptive moving mesh schemes

Abstract:

In recent years, we have investigated integrable discretizations of integrable nonlinear partial differential equations (PDEs) whose solutions possess singularities. For PDEs in this class, we obtained various discrete integrable systems with self-adaptive moving mesh which can be powerful tools for numerical simulations of nonlinear PDEs. One of keys to construct self-adaptive moving mesh schemes is a discretization of hodograph transformations which are transformations between Lagrangian description and Eulerian description. In a geometric point of view, self-adaptive moving mesh schemes can be interpreted as Eulerian description of the motion of discrete curves. In this talk, I will review recent results of discrete integrable systems with self-adaptive moving mesh.

Shoichi Fujimori (Okayama University)

Title: Degenerate limits of triply periodic minimal surfaces of genus 3

Abstract:

We consider limits of triply periodic minimal surfaces in Euclidean 3-space. We prove that some important examples of singly or doubly periodic minimal surfaces can be obtained as limits of triply periodic minimal surfaces. This is joint work with Norio Ejiri and Toshihiro Shoda.