Abstract
Abstract: A hypergraph H=(V,E) has property Bk if there exists a 2-coloring of the set V such that each edge contains at least k vertices of each color. We let mk, g(n) and mΔ(k,b)(n), respectively, denote the least number of edges of an n-homogeneous hypergraph without property BΔk which contains either no cycles of length at least g or no two edges intersecting in more than b vertices. In the paper, upper bounds for these quantities are given. As a consequence, we obtain results for m*k(n), i.e., for the least number of edges of an n-homogeneous simple hypergraph without property Bk. Let Δ(H) be the maximal degree of vertices of a hypergraph H. By Δk(n,g) we denote the minimal degree Δ such that there exists an n-homogeneous hypergraph H with maximal degree Δ and girth at least g but without property Bk. In the paper, an upper bound for Δk(n,g) is obtained.
Original language | English (US) |
---|---|
Pages (from-to) | 188-200 |
Number of pages | 13 |
Journal | Mathematical Notes |
Volume | 108 |
Issue number | 1-2 |
DOIs | |
State | Published - Jul 1 2020 |
Bibliographical note
Funding Information:This work was supported by the Russian Foundation for Basic Research under grant 18-01-00355 and by the program “Leading Scientific Schools” (project no. NSh-2540.2020.1).
Publisher Copyright:
© 2020, Pleiades Publishing, Ltd.
Keywords
- girth
- hypergraphs
- property B
- simple hypergraphs
ASJC Scopus subject areas
- General Mathematics