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 条

[31] Some properties of the core on convex geometries
Yoshio Okamoto
Mathematical Methods of Operations Research, 2003, 56 : 377 - 386
[32] Some properties of the core on convex geometries
Okamoto, Y
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2003, 56 (03) : 377 - 386
[33] Impartial achievement games on convex geometries
McCoy, Stephanie
Sieben, Nandor
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2021, 98
[34] Choice functions and abstract convex geometries
Koshevoy, GA
MATHEMATICAL SOCIAL SCIENCES, 1999, 38 (01) : 35 - 44
[35] ALMOST CONVEX GROUPS AND THE 8 GEOMETRIES
SHAPIRO, M
STEIN, M
GEOMETRIAE DEDICATA, 1995, 55 (02) : 125 - 140
[36] Fast Convex Pruning of Deep Neural Networks
Aghasi, Alireza
Abdi, Afshin
Romberg, Justin
SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE, 2020, 2 (01): : 158 - 188
[37] Convex object Yee cell model building based on convex geometries
Gong, Yanjun
Wu, Zhensen
Dai, Zhenhong
Qinghua Daxue Xuebao/Journal of Tsinghua University, 2007, 47 (09): : 1521 - 1525
[38] A NEW CHARACTERIZATION OF CONVEX PLATES OF CONSTANT WIDTH
MAKAI, E
MARTINI, H
GEOMETRIAE DEDICATA, 1990, 34 (02) : 199 - 209
[39] Chromatic numbers of copoint graphs of convex geometries
Beagley, Jonathan E.
Morris, Walter
DISCRETE MATHEMATICS, 2014, 331 : 151 - 157
[40] A Factorization Theorem of Characteristic Polynomials of Convex Geometries
M. Hachimori
M. Nakamura
Annals of Combinatorics, 2007, 11 : 39 - 46

← 1 2 3 4 5 →