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 条
  • [1] On Scattered Convex Geometries
    Adaricheva, Kira
    Pouzet, Maurice
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2017, 34 (03): : 523 - 550
  • [2] Geometry of Convex Geometries
    Chalopin, Jeremie
    Chepoi, Victor
    Knauer, Kolja
    DISCRETE & COMPUTATIONAL GEOMETRY, 2025,
  • [3] Resolutions of Convex Geometries
    Cantone, Domenico
    Doignon, Jean-Paul
    Giarlotta, Alfio
    Watson, Stephen
    ELECTRONIC JOURNAL OF COMBINATORICS, 2021, 28 (04): : 1 - 39
  • [4] On Scattered Convex Geometries
    Kira Adaricheva
    Maurice Pouzet
    Order, 2017, 34 : 523 - 550
  • [5] Resolutions of convex geometries
    Cantone, Domenico
    Doignon, Jean-Paul
    Giarlotta, Alfio
    Watson, Stephen
    arXiv, 2021,
  • [6] COMBINATORIAL REPRESENTATION AND CONVEX DIMENSION OF CONVEX GEOMETRIES
    EDELMAN, PH
    SAKS, ME
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1988, 5 (01): : 23 - 32
  • [7] Convex dimension of locally planar convex geometries
    Morris, WD
    DISCRETE & COMPUTATIONAL GEOMETRY, 2001, 25 (01) : 85 - 101
  • [8] Embedding convex geometries and a bound on convex dimension
    Richter, Michael
    Rogers, Luke G.
    DISCRETE MATHEMATICS, 2017, 340 (05) : 1059 - 1063
  • [9] Convex Dimension of Locally Planar Convex Geometries
    W. D. Morris
    Discrete & Computational Geometry, 2001, 25 : 85 - 101
  • [10] On the representation of finite convex geometries with convex sets
    Kincses J.
    Acta Scientiarum Mathematicarum, 2017, 83 (1-2): : 301 - 312
12345