Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

Elliptic grids, rational functions, and the Padé interpolation

We consider rational functions with n prescribed poles for which there exists a divided difference operator transforming them to rational functions with n−1 poles. The poles of such functions are shown to lie on the elliptic grids. There is a one-to-one correspondence between this problem of admissible grids and the Poncelet problem on two quadrics. Additionally, we outline an explicit scheme of the Padé interpolation with prescribed poles and zeros on the elliptic grids. Dedicated to Richard Askey on the occasion of his seventieth birthday. 2000 Mathematics Subject Classification Primary—42C05; Secondary—39A13, 41A05, 41A21.     

Geodesic Embeddings and Planar Graphs

Schnyder labelings are known to have close links to order dimension and drawings of planar graphs. It was observed by Ezra Miller that geodesic embeddings of planar graphs are another class of combinatorial or geometric objects closely linked to Schnyder labelings. We aim to contribute to a better understanding of the connections between these objects. In this article we prove • a characterization of 3-connected planar graphs as those graphs admitting rigid geodesic embeddings, • a bijection between Schnyder labelings and rigid geodesic embeddings, • a strong version of the Brightwell–Trotter theorem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Derivatives with respect to metrics and applications: subgradient marching algorithm

This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N ² log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.     

Ramsey goodness and beyond

In a seminal paper from 1983, Burr and Erdős started the systematic study of Ramsey numbers of cliques vs. large sparse graphs, raising a number of problems. In this paper we develop a new approach to such Ramsey problems using a mix of the Szemerédi regularity lemma, embedding of sparse graphs, Turán type stability, and other structural results. We give exact Ramsey numbers for various classes of graphs, solving five — all but one — of the Burr-Erdős problems.     

Hypergeometric functions and elliptic curves

We provide uniform formulas for the real period and the trace of Frobenius associated to an elliptic curve in Legendre normal form. These are expressed in terms of classical and Gaussian hypergeometric functions, respectively. 2000 Mathematics Subject Classification Primary—11G05, 33C05 This research was supported by K. Ono’s NSF grant     

Telescoping partial fractions decompositions, the little q-Jacobi functions of complex order, and the nonterminating q-Saalschütz sum

We use telescoping partial fractions decompositions to give new proofs of the orthogonality property and the normalization relation for the little q-Jacobi polynomials, and the q-Saalschütz sum. In [20], we followed the development [19] of Schur functions for partitions with complex parts, and we showed that there exist natural little q-Jacobi functions of complex order which satisfy extensions of the orthogonality property and normalization relation of the little q-Jacobi polynomials, and that these two results follow from and together imply the nonterminating form of the q-Saalschütz sum. Writing the q-Pochhammer symbol of complex order as a ratio of infinite products in the usual way, we obtain new telescoping partial fractions decomposition proofs of our results [20] for the little q-Jacobi functions of complex order. We give several new proofs of the q-Saalschütz sum and its nonterminating form. For our friends Dick and Liz 2000 Mathematics Subject Classification Primary—42C05; Secondary—33C45, 33C47     

An extension of Vietoris's inequalities

We establish a best possible extension of a famous Theorem of Vietoris about the positivity of a general class of cosine sums. Our result refines and sharpens several earlier generalizations of this Theorem, and settles some open questions regarding the possibility of further improvement of it. Some new inequalities for trigonometric sums are given. We show that our results have applications within the context of positive sums of Gegenbauer polynomials and quadrature methods. We also obtain some existing estimates for the location of zeros of certain trigonometric polynomials under a weakened condition on their coefficients. 2000 Mathematics Subject ClassificationPrimary—42A05; Secondary—42A32,26D05, 26D15, 33B15, 33C45 Dedicated to Richard Askey on the occasion of his 70th birthday     

On the Mean Distance in Scale Free Graphs

We consider a graph, where the nodes have a pre-described degree distribution F, and where nodes are randomly connected in accordance to their degree. Based on a recent result (R. van der Hofstad, G. Hooghiemstra and P. Van Mieghem, “Random graphs with finite variance degrees,” Random Structures and Algorithms, vol. 17(5) pp. 76–105, 2005), we improve the approximation of the mean distance between two randomly chosen nodes given by M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Random graphs with arbitrary degree distribution and their application,” Physical Review. E vol. 64, 026118, pp. 1–17, 2001. Our new expression for the mean distance involves the expectation of the logarithm of the limit of a super-critical branching process. We compare simulations of the mean distance with the results of Newman et al. and with our new approach. AMS 2000 Subject Classification: 05C80, 60F05     

The edmonds—Gallai decomposition for matchings in locally finite graphs

We show that the Edmonds—Gallai decomposition theorem for matchings in finite graphs generalizes to all locally finite graphs. C.N.R.S. Dedicated to Tibor Gallai on his seventieth birthday     

$$\varvec{}$$-Polar Fuzzy Labeling Graphs with Application

In this article, we apply the concept of m-polar fuzzy sets in labeling graphs and introduce the concept of m-polar fuzzy labeling graphs. We present properties of m-polar fuzzy labeling cycle and m-polar fuzzy labeling with bridge and cut nodes. We introduce several different types of distances, including w-distance, strongest strong distance, strong geodesic distance, \(\delta \)-distance in m-polar fuzzy labeling graph and investigate some of their properties. We also present an application of m-polar fuzzy labeling graphs in image processing.     

A new family of Geodesic transitive graphs

We present a new family of locally geodesic transitive graphs with arbitrarily large diameter and valencies, containing a particular case to be geodesic transitive. We also prove that it is a unique family in some generalised family of graphs.     

The Patterson–Sullivan Embedding and Minimal Volume Entropy for Outer Space

Motivated by Bonahon’s result for hyperbolic surfaces, we construct an analogue of the Patterson–Sullivan–Bowen–Margulis map from the Culler–Vogtmann outer space CV (F _k ) into the space of projectivized geodesic currents on a free group. We prove that this map is a continuous embedding and thus obtain a new compactification of the outer space. We also prove that for every k ≥ 2 the minimum of the volume entropy of the universal covers of finite connected volume-one metric graphs with fundamental group of rank k and without degree-one vertices is equal to (3k − 3) log 2 and that this minimum is realized by trivalent graphs with all edges of equal lengths, and only by such graphs. Received: December 2005, Accepted: March 2006     

The Pfaff/Cauchy derivative identities and Hurwitz type extensions

More than 200 years ago, Pfaff found two generalizations of Leibniz’s rule for the nth derivative of a product of two functions. Thirty years later Cauchy found two similar identities, one equivalent to one of Pfaff’s and the other new. We give simple proofs of these little-known identities and some further history. We also give applications to Abel-Rothe type binomial identities, Lagrange’s series, and Laguerre and Jacobi polynomials. Most importantly, we give extensions that are related to the Pfaff/Cauchy theorems as Hurwitz’s generalized binomial theorems are to the Abel-Rothe identities. We apply these extensions to Laguerre and Jacobi polynomials as well. Dedicated to Dick Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—05A19; Secondary—33C45     

A New Class of Infinite Products Generalizing Viète's Product Formula for π

We show how functions F(z) which satisfy an identity of the form F(α z) = g(F(z)) for some complex number α and some function g(z) give rise to infinite product formulas that generalize Viète's product formula for π. Specifically, using elliptic and trigonometric functions we derive closed form expressions for some of these infinite products. By evaluating the expressions at certain points we obtain formulas expressing infinite products involving nested radicals in terms of well-known constants. In particular, simple infinite products for π and the lemniscate constant are obtained. 2000 Mathematics Subject Classification: Primary—40A20; Secondary—33E05     

Unbalanced optimal transport: Dynamic and Kantorovich formulations

This article presents a new class of distances between arbitrary nonnegative Radon measures inspired by optimal transport. These distances are defined by two equivalent alternative formulations: (i) a dynamic formulation defining the distance as a geodesic distance over the space of measures (ii) a static “Kantorovich” formulation where the distance is the minimum of an optimization problem over pairs of couplings describing the transfer (transport, creation and destruction) of mass between two measures. Both formulations are convex optimization problems, and the ability to switch from one to the other depending on the targeted application is a crucial property of our models. Of particular interest is the Wasserstein–Fisher–Rao metric recently introduced independently by [7], [15]. Defined initially through a dynamic formulation, it belongs to this class of metrics and hence automatically benefits from a static Kantorovich formulation.     

The planar algebra associated to a Kac algebra

We obtain (two equivalent) presentations — in terms of generators and relations — of the planar algebra associated with the subfactor corresponding to (an outer action on a factor by) a finite-dimensional Kac algebra. One of the relations shows that the antipode of the Kac algebra agrees with the ‘rotation on 2-boxes’.     

On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

Abstract. We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the primal—dual central path are in some sense close to optimal. The same is true for methods that follow the shifted primal—dual central path among certain infeasible-interior-point methods. We also compute the geodesics in several simple sets.     

Adapted complex structures and the geodesic flow

In this paper, we give a new construction of the adapted complex structure on a neighborhood of the zero section in the tangent bundle of a compact, real-analytic Riemannian manifold. Motivated by the “complexifier” approach of T. Thiemann as well as certain formulas of V. Guillemin and M. Stenzel, we obtain the polarization associated to the adapted complex structure by applying the “imaginary-time geodesic flow” to the vertical polarization. Meanwhile, at the level of functions, we show that every holomorphic function is obtained from a function that is constant along the fibers by “composition with the imaginary-time geodesic flow.” We give several equivalent interpretations of this composition, including a convergent power series in the vector field generating the geodesic flow.     

Geodesic subgraphs

Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs K_n' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs.