Different capacities of a digraph
type: Item
instance of: scholarly article
title: Different capacities of a digraph
zbMATH Open document ID: 0804.05040
DOI: 10.1007/BF02986655
author: Luisa Gargano
author: János Körner
author: Gábor Simonyi
author: A. Galluccio
published in: Graphs and Combinatorics
publication date: 1994-09-26T00:00:00Z
review text: The \(n\)-th Sperner power \(G^ n\) of a digraph \(G\) with vertex set \(V\) has vertex set \(V^ n\) and contains edges \((x_ 1x_ 2 \cdots x_ n, y_ 1y_ 2 \cdots y_ n)\) if and only if \(G\) contains edge \((x_ i, y_ i)\) for at least one \(i\), \(1 \leq i \leq n\). If \(C\) is a class of digraphs closed under Sperner products, let \(F(G^ n)\) denote the cardinality of the largest subgraph from \(C\) contained as an induced subgraph of \(G^ n\); then \(\lim_{n \to \infty}n^{ - 1} \cdot \log F (G^ n)\) may be called the \(C\)-capacity of \(G\). The authors derive upper and lower bounds for various capacity functions and investigate the conditions under which they are tight.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 644728
zbMATH Keywords: clique number
zbMATH Keywords: chromatic number
zbMATH Keywords: independence graphs
zbMATH Keywords: Sperner power
zbMATH Keywords: digraph
zbMATH Keywords: Sperner products
zbMATH Keywords: capacity
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Q3680833
cites work: On the Sperner capacity of the cyclic triangle
cites work: The Sperner capacity of linear and nonlinear codes for the cyclic triangle
cites work: Q3274165
cites work: Qualitative independence and Sperner problems for directed graphs
cites work: Sperner capacities
cites work: Capacities: From information theory to extremal set theory
cites work: A Sperner-type theorem and qualitative independence
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: On the Shannon capacity of a graph
cites work: Q3852128
cites work: Q3708835
full work available at URL: https://doi.org/10.1007/bf02986655
OpenAlex ID: W2017752667
description: scientific article; zbMATH DE number 644728