General edge-isoperimetric inequalities. I: Information-theoretical methods
type: Item
instance of: scholarly article
title: General edge-isoperimetric inequalities. I: Information-theoretical methods
zbMATH Open document ID: 0940.05067
author: Ning Cai
author: Rudolf Ahlswede
published in: European Journal of Combinatorics
publication date: 1997-07-27T00:00:00Z
review text: The authors consider extremal problems on subsets of finite sets and their Cartesian products. A typical example of such a problem is the edge-isoperimetric problem. Given a graph \(G= (V,E)\) and an integer \(m\) the problem is to find a set \(A\subseteq V\) with \(|A|= m\) such that the induced subgraph \(G[A]\) has a maximum number of edges. Very often a solution of this problem for the underlying graph \(G\) is not difficult and the main question is how this information helps to derive a solution for the Cartesian product \(G\times\cdots\times G\) (\(n\) times). If we assume additionally that the extremal subsets for \(G\) are nested, then the standard approach to this problem on \(G\times G\) is to use compressions and to get a downset in some partial order with no decrease in the number of induced edges. It is observed that this technique is applied to the maximization of more general functions if these functions defined on the Cartesian products of the domains are submodular and in a sense additive. Under such assumptions the authors derive a closed formula for the value of such a function of a downset and, using some facts from information theory, obtain an upper bound for this function. The derived upper bounds are compared with one for the edge-isoperimetric problem on the Cartesian product of paths and cycles, where an exact solution is known. Moreover, an asymptotically optimal solution of this problem for the Shannon product of graphs is obtained. To get the Shannon product of two graphs one has to complete the graphs with a loop in each vertex and then take the Cartesian products of the resulting graphs. The proofs use the powerful technique of probability theory and involve some strong information-theoretic results obtained by one of the authors.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1022845
zbMATH Keywords: extremal problems
zbMATH Keywords: edge-isoperimetric problem
zbMATH Keywords: extremal subsets
zbMATH Keywords: paths
zbMATH Keywords: cycles
zbMATH Keywords: probability
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
full work available at URL: eujc.1996.0105
OpenAlex ID: W2811317572
DOI: 10.1006/EUJC.1996.0105
Recommended article: General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions
Recommended article: Edge-Isoperimetric Inequalities and Influences
Recommended article: A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
Recommended article: Approximate convexity and an edge-isoperimetric estimate
Recommended article: Edge-isoperimetric inequalities and ball-noise stability: linear programming and probabilistic approaches
Recommended article: Edge-isoperimetric inequalities in the grid
Recommended article: Remarks on an Edge Isoperimetric Problem
Recommended article: Refinement of analogs of the generalized isoperimetric inequality
Recommended article: Q5694918
Recommended article: The quantitative isoperimetric inequality and related topics
description: scientific article; zbMATH DE number 1022845