Different capacities of a digraph (Q1334937): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Anna Galluccio / rank | |||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Property / author | |||
Property / author: Anna Galluccio / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3680833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Sperner capacity of the cyclic triangle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Sperner capacity of linear and nonlinear codes for the cyclic triangle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3274165 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Qualitative independence and Sperner problems for directed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sperner capacities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Capacities: From information theory to extremal set theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Sperner-type theorem and qualitative independence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Shannon capacity of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3852128 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3708835 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 18:04, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Different capacities of a digraph |
scientific article |
Statements
Different capacities of a digraph (English)
0 references
26 September 1994
0 references
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.
0 references
clique number
0 references
chromatic number
0 references
independence graphs
0 references
Sperner power
0 references
digraph
0 references
Sperner products
0 references
capacity
0 references