2-Colorings of Hypergraphs with Large Girth

A hypergraph has property if there exists a 2-coloring of the set such that each edge contains at least vertices of each color. We let and , respectively, denote the least number of edges of an -homogeneous hypergraph without property which contains either no cycles of length at least or no two edge...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical Notes 2020-07, Vol.108 (1-2), p.188-200
Main Author: Demidovich, Yu. A.
Format: Article
Language:English
Subjects:
14/34
639/766/189
639/766/530
639/766/747
Apexes
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A hypergraph has property if there exists a 2-coloring of the set such that each edge contains at least vertices of each color. We let and , respectively, denote the least number of edges of an -homogeneous hypergraph without property which contains either no cycles of length at least or no two edges intersecting in more than vertices. In the paper, upper bounds for these quantities are given. As a consequence, we obtain results for , i.e., for the least number of edges of an -homogeneous simple hypergraph without property . Let be the maximal degree of vertices of a hypergraph . By we denote the minimal degree such that there exists an -homogeneous hypergraph with maximal degree and girth at least but without property . In the paper, an upper bound for is obtained.
ISSN:0001-4346
1067-9073
1573-8876
DOI:10.1134/S0001434620070202