2-Colorings of Hypergraphs with Large Girth

Yu A. Demidovich*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)188-200
Number of pages13
JournalMathematical Notes
Volume108
Issue number1-2
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of '2-Colorings of Hypergraphs with Large Girth'. Together they form a unique fingerprint.

Cite this