Pruning processes and a new characterization of convex geometries

被引：3
|
作者：
Ardila, Federico [1 ]
Maneva, Elitza [2 ]
机构：
[1] San Francisco State Univ, Dept Math, San Francisco, CA 94132 USA
[2] IBM Corp, Almaden Res Ctr, San Jose, CA 95120 USA
来源：
DISCRETE MATHEMATICS | 2009年 / 309卷 / 10期
基金：
美国国家科学基金会;
关键词：
Antimatroid; Convex geometry; k-SAT; Pruning process; Removal process; SATISFIABILITY;
D O I：
10.1016/j.disc.2008.08.020
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We provide a new characterization of convex geometries via a multivariate version of an identity that was originally proved, in a special case arising from the k-SAT problem, by Maneva, Mossel and Wainwright. We thus highlight the connection between various characterizations of convex geometries and a family of removal processes studied in the literature on random structures. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：3083 / 3091
页数：9
相关论文
共 50 条
12345