Pruning Processes and a New Characterization of Convex Geometries

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We provide a new characterization of convex geometries via a multivariate version of an identity that was originally proved by Maneva, Mossel and Wainwright for certain combinatorial objects arising in the context of the k-SAT problem. We thus highlight the connection between various characterizations of convex geometries and a family of removal processes studied in the literature on random structures.
14 pages, 3 figures; the exposition has changed significantly from previous version

Keywords

Combinatorics, Discrete Mathematics, Probability, 06A07; 52B40; 60C05; 68R05; 68W40

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/167954

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0706.3750
 http://arxiv.org/abs/0706.3750

Collections

arXiv