On a problem of Erdős and Moser

A set A of vertices in an r-uniform hypergraph $$\mathcal H$$H is covered in$$\mathcal H$$H if there is some vertex $$u\not \in A$$u∉A such that every edge of the form $$\{u\}\cup B$${u}∪B, $$B\in A^{(r-1)}$$B∈A(r-1) is in $$\mathcal H$$H. 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 year

  2015

• Venue

  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg

• Publication date

  2015-02-24

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1007/S12188-016-0162-1arXiv 1502.06832
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The existence of designs

  2014cited by this paper
• A theorem of finite sets

  2009cited by this paper
• AN EXTREMAL PROBLEM IN GRAPH THEORY

  2001cited by this paper
• Projections of Bodies and Hereditary Properties of Hypergraphs

  1995cited by this paper
• On a Packing and Covering Problem

  1985cited by this paper
• Combinatorial problems and exercises

  1979cited by this paper
• A Problem on Tournaments

  1964cited by this paper
• An inequality related to the isoperimetric inequality

  1949cited by this paper

• Some Famous Problems of Discrete Geometry

  2015cites this paper
• On Sets Defining Few Ordinary Lines

  2013cites this paper
• On Sets Defining Few Ordinary Lines

  2012cites this paper