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 条
  • [41] Orders on Subsets Rationalised by Abstract Convex Geometries
    Bossert, Walter
    Ryan, Matthew J.
    Slinko, Arkadii
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2009, 26 (03): : 237 - 244
  • [42] Matroids on convex geometries (cg-matroids)
    Fujishige, Satoru
    Koshevoy, Gleb A.
    Sano, Yoshio
    DISCRETE MATHEMATICS, 2007, 307 (15) : 1936 - 1950
  • [43] Cooperative games on convex geometries with a coalition structure
    Meng, Fanyong
    Zhang, Qiang
    JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 2012, 25 (05) : 909 - 925
  • [44] Efficient knowledge assessment based on convex geometries
    Encheva, Sylvia
    Tumin, Sharil
    INTELLIGENT INFORMATION PROCESSING III, 2006, 228 : 187 - +
  • [45] GEODESIC FLOW OF NONSTRICTLY CONVEX HILBERT GEOMETRIES
    Bray, Harrison
    ANNALES DE L INSTITUT FOURIER, 2020, 70 (04) : 1563 - 1593
  • [46] COMBINATORIAL GEOMETRIES, CONVEX POLYHEDRA, AND SCHUBERT CELLS
    GELFAND, IM
    GORESKY, RM
    MACPHERSON, RD
    SERGANOVA, VV
    ADVANCES IN MATHEMATICS, 1987, 63 (03) : 301 - 316
  • [47] Subicular neurons encode concave and convex geometries
    Yanjun Sun
    Douglas A. Nitz
    Xiangmin Xu
    Lisa M. Giocomo
    Nature, 2024, 627 : 821 - 829
  • [48] Join-semidistributive lattices and convex geometries
    Adaricheva, KV
    Gorbunov, VA
    Tumanov, VI
    ADVANCES IN MATHEMATICS, 2003, 173 (01) : 1 - 49
  • [49] Realization of abstract convex geometries by point configurations
    Adaricheva, Kira
    Wild, Marcel
    EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (01) : 379 - 400
  • [50] Orders on Subsets Rationalised by Abstract Convex Geometries
    Walter Bossert
    Matthew J. Ryan
    Arkadii Slinko
    Order, 2009, 26 : 237 - 244
12345