Vol. 8, No. 4, 2019

Download this article
Download this article For screen
For printing
Recent Issues
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Previously Published
To Appear
founded and published with the
scientific support and advice of the
Moscow Institute of
Physics and Technology
 
Other MSP Journals
On the domination number of a graph defined by containment

Peter Frankl

Vol. 8 (2019), No. 4, 379–384
Abstract

Let n > k > 2 be integers. Define a bipartite graph between all k-element and all 2-element subsets of an n-element set by drawing an edge if and only if the first one contains the second. The domination number of this graph is determined up to a factor of 1 + o(1). The short proof relies on some extremal results concerning hypergraphs.

Keywords
finite sets, graphs, hypergraphs, Turán's theorem
Milestones
Received: 29 April 2019
Revised: 1 August 2019
Accepted: 15 August 2019
Published: 11 October 2019
Authors
Peter Frankl
Rényi Institute
Budapest
Hungary