Combinatorics of lopsided sets
SCIE
SCOPUS
- Title
- Combinatorics of lopsided sets
- Authors
- Bandelt, HJ; Chepoi, V; Dress, A; Koolen, J
- Date Issued
- 2006-07
- Publisher
- ACADEMIC PRESS LTD ELSEVIER SCIENCE L
- Abstract
- We develop a theory of isometric subgraphs of hypercubes for which a certain inheritance of isometry plays a crucial role. It is well known that median graphs and closely related graphs embedded in hypercubes bear geometric features that involve realizations by solid cubical complexes or are expressed by Euler-type counting formulae for cubical faces. Such properties can also be established for antimatroids, and in fact, a straightforward generalization ("conditional antimatroid") captures this concept as well as median convexity. The key ingredient for the cube counting formulae that work in conditional antimatroids is a simple cube projection property, which, when letting sets be encoded by sign vectors, is seen to be invariant under sign switches and guarantees linear independence of the corresponding sign vectors. It then turns out that a surprisingly elementary calculus of projection and lifting gives rise to a plethora of equivalent characterizations of set systems bearing these properties, which are not necessarily closed under intersections (and thus are more general than conditional antimatroids). One of these descriptions identifies these particular set systems alias sets of sign vectors as the lopsided sets originally introduced by Lawrence in order to investigate the subgraphs of the n-cube that encode the intersection pattern of a given convex set K with the closed orthants of the n-dimensional Euclidean space. This demonstrates that the concept of lopsidedness in its various disguises is most natural and versatile in combinatorics. (C) 2005 Elsevier Ltd. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29612
- DOI
- 10.1016/j.ejc.2005.03.001
- ISSN
- 0195-6698
- Article Type
- Article
- Citation
- EUROPEAN JOURNAL OF COMBINATORICS, vol. 27, no. 5, page. 669 - 689, 2006-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.