The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Default user image.

Timo Vilkas

Senior lecturer

Default user image.

Water transport on infinite graphs

Author

  • Olle Häggström
  • Timo Hirscher

Summary, in English

If the nodes of a graph are considered to be identical barrels – featuring different water levels – and the edges to be (locked) water-filled pipes in between the barrels, consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, that is, by opening and closing the locks in an elaborate succession. This model is related to an opinion formation process, the so-called Deffuant model. We consider the initial water profile to be given by i.i.d. unif(0,1) random variables, investigate the supremum of achievable water levels at a given node – or to be more precise, the support of its distribution – and ask in which settings it becomes degenerate, that is, reduces to a single value. This turns out to be the case for all infinite connected quasi-transitive graphs, with exactly one exception: the two-sided infinite path.

Publishing year

2019-05

Language

English

Pages

515-527

Publication/Series

Random Structures and Algorithms

Volume

54

Issue

3

Document type

Journal article

Publisher

John Wiley & Sons Inc.

Topic

  • Probability Theory and Statistics

Keywords

  • Deffuant model
  • graph algorithms
  • infinite path
  • optimization
  • water transport

Status

Published

ISBN/ISSN/Other

  • ISSN: 1042-9832