Combinatorial extremum problems for 2-colorings of hypergraphs

被引：0

作者：

A. P. Rozovskaya

机构：

[1] Moscow State University,

来源：

Mathematical Notes | 2011年 / 90卷

关键词：

n-uniform hypergraph; 2-coloring; asymptotic lower bound;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We consider a generalization of the Erdős-Hajnal classical combinatorial problem. Let k be a positive integer. It is required to find the value of mk(n) equal to the minimum number of edges of an n-uniform hypergraph that does not admit 2-colorings of the set of its vertices such that each edge of the hypergraph contains exactly k vertices of each color. In the present paper, we obtain a new asymptotic lower bound for mk(n), which improves the preceding results in a wide range of values of the parameter k. We also consider some other generalizations of this problem.

引用

共 11 条

[1]

Erdős P.(1961)On a property of families of sets Acta Math. Acad. Sci. Hungar 12 87-123

[2]

Hajnal A.(1963)On a combinatorial problem Nordisk Mat. Tidskr. 11 5-10

[3]

Erdős P.(1964)On a combinatorial problem. II Acta Math. Acad. Sci. Hungar 15 445-447

[4]

Erdős P.(2000)Improved bounds and algorithms for hypergraph 2-coloring Random Structures Algorithms 16 4-32

[5]

Radhakrishnan J.(2004)On one combinatorial problem of Erdős Dokl. Ross. Akad. Nauk 396 166-169

[6]

Srinivasan A.(2007)Extremal problems for colorings of uniform hypergraphs Izv. Ross. Akad. Nauk Ser. Mat. 71 183-222

[7]

Shabanov D. A.(2008)Randomized algorithms for colorings of hypergraphs Mat. Sb. 199 139-160

[8]

Shabanov D. A.(2009)Greedy colorings for uniform hypergraphs Random Structures Algorithms 35 216-221

[9]

Shabanov D. A.(1990)An application of Lovász Local Lemma — a new lower bound for the van der Waerden number Random Structures Algorithms 1 343-360

[10]

Pluhár A.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →