On a problem of Erdős and Moser
A set A of vertices in an r-uniform hypergraph HH is covered in HH if there is some vertex u∉Au∉A such that every edge of the form {u}∪B{u}∪B , B∈A(r−1)B∈A(r−1) is in HH . Erdős and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices s...
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Journal article |
| Foilsithe / Cruthaithe: |
Springer Berlin Heidelberg
2017
|
| Achoimre: | A set A of vertices in an r-uniform hypergraph HH is covered in HH if there is some vertex u∉Au∉A such that every edge of the form {u}∪B{u}∪B , B∈A(r−1)B∈A(r−1) is in HH . Erdős and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs. |
|---|