×

Random coloring method in the combinatorial problem of Erdős and Lovász. (English) Zbl 1241.05104

Summary: The work deals with a combinatorial problem of P. Erdős and L. Lovász [Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 609-627 (1975; Zbl 0315.05117)] concerning simple hypergraphs. Let \(m^*(n,r)\) denote the minimum number of edges in an \(n\)-uniform simple hypergraph with chromatic number at least \(r+1\). The main result of the work is a new asymptotic lower bound for \(m^*(n,r)\). We prove that for large \(n\) and \(r\) satisfying \(r\leq n^{1/9}\) the following inequality holds \[ m^*(n+ 1,r)\geq {1\over 2} r^{2n-2} n^{-6/t}, \] where \(t= \lfloor\sqrt{\min({\ln n\over\ln r}, {\ln n\over 2\ln(4/3)\ln n)})}\rfloor\). This bound improves previously known bounds for \(r< n^{1/36}\). The proof is based on a method of random coloring. We have also obtained results concerning colorings of \(h\)-simple hypergraphs.

MSC:

05C65 Hypergraphs
05C35 Extremal problems in graph theory
05C07 Vertex degrees
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0315.05117
Full Text: DOI

References:

[1] Alon, Hypergraphs with high chromatic number, Graphs Combin 1 pp 387– (1985) · Zbl 0609.05054 · doi:10.1007/BF02582966
[2] Alon, Probabilistic method (2002)
[3] Beck, On 3-chromatic hypergraphs, Discrete Math 24 pp 127– (1978) · Zbl 0429.05055 · doi:10.1016/0012-365X(78)90191-7
[4] Bohman, Coloring H-free hypergraphs, Random Struct Algorithms 36 pp 11– (2010) · Zbl 1205.05082 · doi:10.1002/rsa.20298
[5] Erdos, On a combinatorial problem, II, Acta Math Acad Sci, Hung 15 pp 445– (1964) · Zbl 0201.33704 · doi:10.1007/BF01897152
[6] Erdos, On a property of families of sets, Acta Math Acad Sci, Hung 12 pp 87– (1961) · Zbl 0201.32801 · doi:10.1007/BF02066676
[7] P. Erdos L. Lovász Problems and results on 3-chromatic hypergraphs and some related questions 1973 609 627
[8] A. V. Kostochka Color-critical graphs and hypergraphs with few edges: a survey 2006 175 198
[9] Kostochka, Coloring uniform hypergraphs with few colors, Random Struct Algorithms 24 pp 1– (2004) · Zbl 1031.05051 · doi:10.1002/rsa.10109
[10] Kostochka, Coloring uniform hypergraphs with few edges, Random Struct Algorithms 35 pp 348– (2009) · Zbl 1205.05092 · doi:10.1002/rsa.20284
[11] Kostochka, On the chromatic number of set systems, Random Struct Algorithms 19 pp 87– (2001) · Zbl 0984.05073 · doi:10.1002/rsa.1020
[12] Kostochka, Constructions of sparse uniform hypergraphs with high chromatic number, Random Struct Algorithms 36 pp 46– (2010) · Zbl 1208.05094 · doi:10.1002/rsa.20293
[13] Radhakrishnan, Improved bounds and algorithms for hypergraph two-coloring, Random Struct Algorithms 16 pp 4– (2000) · Zbl 0942.05024 · doi:10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2
[14] Rozovskaya, On the problem of Erdos and Hajnal in the case of list colorings, Electron Notes Discrete Math 34 pp 387– (2009) · Zbl 1273.05196 · doi:10.1016/j.endm.2009.07.064
[15] Shabanov, On the chromatic number of finite systems of subsets, Math Notes 85 pp 902– (2009) · Zbl 1191.05044 · doi:10.1134/S0001434609050332
[16] Shabanov, Improvement of the lower bound in the Erdos -Hajnal combinatorial problem, Doklady Math 79 pp 349– (2009) · Zbl 1281.05099 · doi:10.1134/S1064562409030132
[17] Shabanov, Lower bounds in the combinatorial problem of Erdos and Lovász, Doklady Math 81 pp 286– (2010) · Zbl 1292.05149 · doi:10.1134/S1064562410020341
[18] Spencer, Coloring n-sets red and blue, J Combin Theory Ser A 30 pp 112– (1981) · Zbl 0448.05032 · doi:10.1016/0097-3165(81)90045-5
[19] Szabó, An application of Lovasz Local Lemma -a new lower bound for the van der Waerden number, Random Struct Algorithms 1 pp 343– (1990) · Zbl 0723.05115 · doi:10.1002/rsa.3240010307
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.