skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.


Search for: All records

Creators/Authors contains: "Lippner, Gabor"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier–Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.

     
    more » « less
  2. We compute the leading asymptotics of the logarithm of the number of $d$-regular graphs having at least a fixed positive fraction $c$ of the maximum possible number of triangles, and provide a strong structural description of almost all such graphs. When $d$ is constant, we show that such graphs typically consist of many disjoint $(d+1)$-cliques and an almost triangle-free part. When $d$ is allowed to grow with $n$, we show that such graphs typically consist of very dense sets of size $d+o(d)$ together with an almost triangle-free part. This confirms a conjecture of Collet and Eckmann from 2002 and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles. 
    more » « less
  3. null (Ed.)
  4. Abstract

    Population structure affects the outcome of natural selection. These effects can be modeled using evolutionary games on graphs. Recently, conditions were derived for a trait to be favored under weak selection, on any weighted graph, in terms of coalescence times of random walks. Here we consider isothermal graphs, which have the same total edge weight at each node. The conditions for success on isothermal graphs take a simple form, in which the effects of graph structure are captured in the ‘effective degree’—a measure of the effective number of neighbors per individual. For two update rules (death-Birth and birth-Death), cooperative behavior is favored on a large isothermal graph if the benefit-to-cost ratio exceeds the effective degree. For two other update rules (Birth-death and Death-birth), cooperation is never favored. We relate the effective degree of a graph to its spectral gap, thereby linking evolutionary dynamics to the theory of expander graphs. Surprisingly, we find graphs of infinite average degree that nonetheless provide strong support for cooperation.

     
    more » « less