General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions
type: Item
instance of: scholarly article
title: General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions
zbMATH Open document ID: 0878.05050
author: Ning Cai
author: Rudolf Ahlswede
published in: European Journal of Combinatorics
publication date: 1997-11-25T00:00:00Z
review text: The lexicographic order \({\mathcal L}\) on a sequence space \({\mathcal H}^n=\{0,1,\ldots,\alpha\}\) is defined by \(x^n<y^n\) iff there exists a \(t\) such that \(x_t<y_t\) and \(x_s=y_s\) for \(s<t\). There are two kinds of edge-isoperimetric problems (EIP) that can be represented as extremal problems in graph theory. For a graph \(G=(V,E)\), for any \(A\subset V\) the sets of all boundary and inner edges are defind by \({\mathcal B}(A)=\{xy\in E:|\{x,y\}\cap A|=1\}\) and \({\mathcal I}(A)=\{xy\in E:x,y\in A\}\), respectively. The boundary-edge-isoperimetric problem (BEIP) and inner-edge-isoperimetric problem (IEIP) are defined as follows: for a given graph and positive integer \(m\), find a set \(A\subset V\) of cardinality \(m\) with minimal (maximal) possible value of \(|{\mathcal B}(A)|\) (\(|{\mathcal I}(A)|\)). In this paper the following problem is considered: ``Is \({\mathcal L}\) optimal for an EIP in \(G^n\)?'' (\(G^n\) denotes the \(n\)th power of \(G\) relatively to the Cartesian sum of graphs.) If \(N=\{1,2,\ldots,n\}\), for any \(A\subset{\mathcal H}^n={\mathcal H}^N\), \(A_T(x^{N\setminus J})\) is defined as \(\{x^J\in{\mathcal H}^J:x^N\in A\}\) for \(x^{N\setminus J}\in{\mathcal H}^{N\setminus J}\) and for any set function \(\phi\) on \(2^{{\mathcal H}}\), \(\phi^n(A)=\sum_{t=1}^n\sum_{x^{N\setminus\{t\}}\in{\mathcal H}^{N\setminus\{t\}}}\phi(A_t(x^{N\setminus\{t\}}))\). The main result of the paper is the following one: Let \(|{\mathcal H}|\geq 3\), \(n\) be any integer \(\geq 2\) and \(\phi\) be any set function \(\phi:2^{{\mathcal H}}\rightarrow\mathbb{R}\) satisfying: I (nestedness): for all \(k\in{\mathcal H}=\{0,1,\ldots,\alpha\}\), \(A\subset{\mathcal H}\) with \(|A|=k+1\) implies \(\phi(A)\leq\phi(\{0,1,\ldots,k\})\); II (submodularity): for \(A,B\subset{\mathcal H}\), \(\phi(A)+\phi(B)\leq\phi(A\cup B)+\phi(A\cap B)\); III: \(\phi(\varnothing)=0\). Then \({\mathcal L}\) on \(X^n\) is optimal for \(\phi^n\) iff \({\mathcal L}\) on \({\math…
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1045830
zbMATH Keywords: lexicographical order
zbMATH Keywords: boundary edges
zbMATH Keywords: inner edges
zbMATH Keywords: Cartesian sum
zbMATH Keywords: set function
zbMATH Keywords: submodularity
zbMATH Keywords: edge-isoperimetric problems
MaRDI profile type: Publication
full work available at URL: eujc.1996.0106
OpenAlex ID: W2100449986
DOI: 10.1006/EUJC.1996.0106
description: scientific article; zbMATH DE number 1045830