Complete \(r\)-partite subgraphs of dense \(r\)-graphs (Q1043950): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| 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
