Open Access. Powered by Scholars. Published by Universities.®
![Digital Commons Network](http://assets.bepress.com/20200205/img/dcn/DCsunburst.png)
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Submodular Percolation, Graham R. Brightwell, Peter Winkler
Submodular Percolation, Graham R. Brightwell, Peter Winkler
Dartmouth Scholarship
Let $f:{\cal L}\to\mathbb{R}$ be a submodular function on a modular lattice ${\cal L}$; we show that there is a maximal chain ${\cal C}$ in ${\cal L}$ on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of ${\cal L}$, in a certain well-behaved partial order on sequences of reals. One consequence is that the maximum value of f on ${\cal C}$ is minimized over all such paths—i.e., if one can percolate from 0 to 1 on lattice points X with $f(X)\le b$, then one can do so along a …