The sandwich theorem
type: Item
instance of: scholarly article
title: The sandwich theorem
zbMATH Open document ID: 0810.05065
author: Donald E. Knuth
published in: The Electronic Journal of Combinatorics
publication date: 1995-02-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/9312214
full work available at URL: https://eudml.org/doc/118559
full work available at URL: A1
review text: Summary: This report contains expository notes about a function \(\theta(G)\) that is popularly known as the Lovász number of a graph \(G\). There are many ways to define \(\theta(G)\), and the surprising variety of different characterizations indicates in itself that \(\theta(G)\) should be interesting. But the most interesting property of \(\theta(G)\) is probably the fact that it can be computed efficiently, although it lies ``sandwiched'' between other classic graph numbers whose computation is NP-hard. I have tried to make these notes self-contained so that they might serve as an elementary introduction to the growing literature on Lovász's fascinating function.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 721219
zbMATH Keywords: sandwich theorem
zbMATH Keywords: Lovász number
zbMATH Keywords: graph numbers
zbMATH Keywords: Lovász function
MaRDI profile type: Publication
arXiv ID: math/9312214
description: scientific article