Complete \(r\)-partite subgraphs of dense \(r\)-graphs (Q1043950): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2018301625 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0711.1185 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of linear graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On extremal problems of graphs and generalized graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with many <i>r</i> -cliques have large complete <i>r</i> -partite subgraphs / rank | |||
Normal rank |
Latest revision as of 07:24, 2 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete \(r\)-partite subgraphs of dense \(r\)-graphs |
scientific article |
Statements
Complete \(r\)-partite subgraphs of dense \(r\)-graphs (English)
0 references
10 December 2009
0 references
Let \(U1, \dots, Ur\) be sets of size \(n\) and \(U\) their Cartesian product. Let \(M\) be a fixed subset of \(U\) of relative size at least a. Let \(V1, \dots, Vr\) be subsets of \(U1, \dots, Ur\) and \(V\) their Cartesian product. Assume that the size of \(V\) is at most \(ln(n)\). By specifying a lower bound to a in terms of \(n\) and \(r\) it is possible to find a lower bound to the number of sets \(V\) contained in \(M\). For \(r\) larger than 2 this extends a classical result of Erdős on complete bipartite graphs.
0 references
hypergraph
0 references
directed hypergraph
0 references
complete multipartite subgraph
0 references