Pruning processes and a new characterization of convex geometries
| Autor: | Elitza Maneva, Federico Ardila |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
FOS: Computer and information sciences
Antimatroid Discrete Mathematics (cs.DM) Identity (music) Theoretical Computer Science 06A07 52B40 60C05 68R05 68W40 FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Pruning (decision trees) Special case k-SAT Mathematics Discrete mathematics Convex geometry Probability (math.PR) Regular polygon Removal process Connection (mathematics) Combinatorics (math.CO) Boolean satisfiability problem Mathematics - Probability Pruning process Computer Science - Discrete Mathematics |
| Zdroj: | Discrete Mathematics. 309(10):3083-3091 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2008.08.020 |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect