Journal article icon

Journal article

On a problem of Erdős and Moser

Abstract:
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.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/s12188-016-0162-1

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Bollobas, B More by this author
Publisher:
Springer Berlin Heidelberg Publisher's website
Journal:
Abhandlungen des Mathematischen Seminars der Universität Hamburg Journal website
Volume:
87
Issue:
2
Pages:
213–222
Publication date:
2017-01-09
Acceptance date:
2016-02-23
DOI:
EISSN:
1865-8784
ISSN:
0025-5858
URN:
uuid:ead3e85a-741d-464c-8574-cd03e833768e
Source identifiers:
632958
Local pid:
pubs:632958
Keywords:

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP