Entropy splitting for antiblocking corners and perfect graphs |
| |
Authors: | I Csiszár J Körner L Lovász K Marton G Simonyi |
| |
Institution: | (1) Mathematical Institute of the Hungarian Academy of Sciences, H-1053 Budapest, Hungary;(2) Department of Computer Science, Eötvös University, H-1088 Budapest, Hungary;(3) Department of Computer Science, Princeton University, 08544 Princeton, N. J., USA;(4) Département Informatique, ENST, Paris, France |
| |
Abstract: | We characterize pairs of convex setsA, B in thek-dimensional space with the property that every probability distribution (p
1,...,p
k
) has a repsesentationp
i
=a
l
.b
i
, a A, b B.Minimal pairs with this property are antiblocking pairs of convex corners. This result is closely related to a new entropy concept. The main application is an information theoretic characterization of perfect graphs.Research was partially sponsored by the Hungarian National Foundation, Scientific Research Grants No 1806 and 1812. |
| |
Keywords: | 05C15 |
本文献已被 SpringerLink 等数据库收录! |
|