Geodesic
Van der Waerden's function and colourings of hypergraphs
Izvestiya. Mathematics , Tome 75 (2011) no. 5, pp. 1063-1091.

Voir la notice de l'article provenant de la source Math-Net.Ru

A classical problem of combinatorial number theory is to compute van der Waerden's function $W(n,r)$. Using random colourings of hypergraphs, we get a new asymptotic lower bound for $W(n,r)$ which improves previous results for a wide range of values of $n$ and $r$.
Keywords: van der Waerden's theorem, arithmetic progressions, hypergraph, chromatic number. 
@article{IM2_2011_75_5_a8,
     author = {D. A. Shabanov},
     title = {Van der {Waerden's} function and colourings of hypergraphs},
     journal = {Izvestiya. Mathematics },
     pages = {1063--1091},
     publisher = {mathdoc},
     volume = {75},
     number = {5},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a8/}
}
TY  - JOUR
AU  - D. A. Shabanov
TI  - Van der Waerden's function and colourings of hypergraphs
JO  - Izvestiya. Mathematics 
PY  - 2011
SP  - 1063
EP  - 1091
VL  - 75
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a8/
LA  - en
ID  - IM2_2011_75_5_a8
ER  - 
%0 Journal Article
%A D. A. Shabanov
%T Van der Waerden's function and colourings of hypergraphs
%J Izvestiya. Mathematics 
%D 2011
%P 1063-1091
%V 75
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a8/
%G en
%F IM2_2011_75_5_a8
D. A. Shabanov. Van der Waerden's function and colourings of hypergraphs. Izvestiya. Mathematics , Tome 75 (2011) no. 5, pp. 1063-1091. http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a8/

[1] B. L. van der Waerden, “Beweis einer Baudetschen Vermutung”, Nieuw Archief voor Wiskunde, 15 (1927), 212–216 | Zbl

[2] R. L. Graham, Rudiments of Ramsey theory, CBMS Regional Conf. Ser. in Math., 45, Amer. Math. Soc., Providence, RI, 1981 | MR | MR | Zbl | Zbl

[3] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1990 | MR | Zbl

[4] I. D. Shkredov, “Szemeredi's theorem and problems on arithmetic progressions”, Russian Math. Surveys, 61:6 (2006), 1101–1166 | DOI | MR | Zbl

[5] S. Shelah, “Primitive recursive bounds for van der Waerden numbers”, J. Amer. Math. Soc., 1:3 (1988), 683–697 | DOI | MR | Zbl

[6] W. T. Gowers, “A new proof of Szemerédi's theorem”, Geom. Funct. Anal., 11:3 (2001), 465–588 | DOI | MR | Zbl

[7] R. Graham, J. Solymosi, “Monochromatic equilateral right triangles on the integer grid”, Topics in discrete mathematics, Algorithms Combin., 26, Springer-Verlag, Berlin, 2006, 129–132 | DOI | MR | Zbl

[8] P. Erdős, R. Radó, “Combinatorial theorems on classifications of subsets of a given set”, Proc. London Math. Soc. (3), 2 (1952), 417–439 | DOI | MR | Zbl

[9] L. Moser, “Notes on number theory. II. On a theorem of van der Waerden”, Canad. Math. Bull., 3 (1960), 23–25 | DOI | MR | Zbl

[10] W. M. Schmidt, “Two combinatorial theorems on arithmetic progressions”, Duke Math. J., 29:1 (1962), 129–140 | DOI | MR | Zbl

[11] E. R. Berlekamp, “A construction for partitions which avoid long arithmetic progressions”, Canad. Math. Bull., 11 (1968), 409–414 | DOI | MR | Zbl

[12] P. Erdős, L. Lovász, “Problems and results on $3$-chromatic hypergraphs and some related questions”, Infinite and finite sets (Keszthely, 1973), North Holland, Amsterdam, 1973, 609–627 | MR | Zbl

[13] Z. Szabó, “An application of Lovasz' local lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360 | DOI | MR | Zbl

[14] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[15] D. A. Shabanov, “On the chromatic number of finite systems of subsets”, Math. Notes, 85:5–6 (2009), 902–905 | DOI | MR | Zbl

[16] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 2000 | MR | Zbl