Ollivier–Ricci idleness functions of graphs

David P. Bourne; D. Cushing; S. Liu; F. Münch; N. Peyerimhoff

doi:10.1137/17M1134469

Ollivier–Ricci idleness functions of graphs

David P. Bourne, D. Cushing, S. Liu, F. Münch, N. Peyerimhoff

Research output: Contribution to journal › Article › peer-review

31 Citations (Scopus)

74 Downloads (Pure)

Abstract

We study the Ollivier–Ricci curvature of graphs as a function of the chosen idleness. We show that this idleness function is concave and piecewise linear with at most three linear parts, and at most two linear parts in the case of a regular graph. We then apply our result to show that the idleness function of the Cartesian product of two regular graphs is completely determined by the idleness functions of the factors.

Original language	English
Pages (from-to)	1408-1424
Number of pages	17
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	2
DOIs	https://doi.org/10.1137/17M1134469
Publication status	Published - 19 Jun 2018

Keywords

Idleness
Ollivier–Ricci
Optimal transport

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/17M1134469

Download pdfAccepted author manuscript, 292 KBLicence: All Rights Reserved

Cite this

@article{147520759b7a41ef9d86fc9c5a140baf,

title = "Ollivier–Ricci idleness functions of graphs",

abstract = "We study the Ollivier–Ricci curvature of graphs as a function of the chosen idleness. We show that this idleness function is concave and piecewise linear with at most three linear parts, and at most two linear parts in the case of a regular graph. We then apply our result to show that the idleness function of the Cartesian product of two regular graphs is completely determined by the idleness functions of the factors.",

keywords = "Idleness, Ollivier–Ricci, Optimal transport",

author = "Bourne, {David P.} and D. Cushing and S. Liu and F. M{\"u}nch and N. Peyerimhoff",

year = "2018",

month = jun,

day = "19",

doi = "10.1137/17M1134469",

language = "English",

volume = "32",

pages = "1408--1424",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Ollivier–Ricci idleness functions of graphs

AU - Bourne, David P.

AU - Cushing, D.

AU - Liu, S.

AU - Münch, F.

AU - Peyerimhoff, N.

PY - 2018/6/19

Y1 - 2018/6/19

N2 - We study the Ollivier–Ricci curvature of graphs as a function of the chosen idleness. We show that this idleness function is concave and piecewise linear with at most three linear parts, and at most two linear parts in the case of a regular graph. We then apply our result to show that the idleness function of the Cartesian product of two regular graphs is completely determined by the idleness functions of the factors.

AB - We study the Ollivier–Ricci curvature of graphs as a function of the chosen idleness. We show that this idleness function is concave and piecewise linear with at most three linear parts, and at most two linear parts in the case of a regular graph. We then apply our result to show that the idleness function of the Cartesian product of two regular graphs is completely determined by the idleness functions of the factors.

KW - Idleness

KW - Ollivier–Ricci

KW - Optimal transport

UR - http://www.scopus.com/inward/record.url?scp=85049561344&partnerID=8YFLogxK

U2 - 10.1137/17M1134469

DO - 10.1137/17M1134469

M3 - Article

AN - SCOPUS:85049561344

SN - 0895-4801

VL - 32

SP - 1408

EP - 1424

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Ollivier–Ricci idleness functions of graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

David Bourne

Cite this

Ollivier–Ricci idleness functions of graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Profiles

David Bourne

Cite this