Don't take life too seriously: it's just a temporary situation

Van der Waerden (numeri di)

Matematica combinatoria  Vari 

Indice

  1. 1. Pagina principale
  2. 2. Numeri di Van der Waerden per piĆ¹ sottoinsiemi

I numeri di Van der Waerden sono stati generalizzati al caso di più sottoinsiemi; il numero W(r; k1, k2, …kr) è il minimo intero tale che se suddividiamo gli interi da 1 a W(r; k1, k2, …kr) in r insiemi (non necessariamente disgiunti), il primo insieme contiene una progressione aritmetica di lunghezza k1, oppure il secondo ne contiene una di lunghezza k2, ... , oppure l’ultimo ne contiene una di lunghezza kr.

 

Si conoscono solo pochi limiti superiori e inferiori generali per questi numeri:

W(2; 3, n) > nclogn, per una costante c (R.Graham, 2006);

W(2; 3, n) ≤ ncn2, per una costante c (J. Bourgain, 1999);

W(2; 4, n) < enclogn, per una costante c (Tom Brown, Bruce M. Landman e Aaron Robertson, 2008);

Limite inferiore per W(2; m, n), (Tom Brown, Bruce M. Landman e Aaron Robertson, 2008);

Limite inferiore per W(2; m, n), per una costante c e n abbastanza grande (Yusheng Li e Jinlong Shu, 2008);

W(r; 4, 4, 4, ..., 4) < erclogr, per una costante c (Tom Brown, Bruce M. Landman e Aaron Robertson, 2008);

W(r; k, k, k, ..., k) > rclog2r, per una costante c, k > 3, e r abbastanza grande (Tom Brown, Bruce M. Landman e Aaron Robertson, 2008).

 

Si conoscono alcuni di questi numeri, tutti ricavati esaminando un gran numero di combinazioni. La tabella seguente riassume i principali risultati noti.

Numero

Valore

Autore della dimostrazione

W(2; 3, 3)

9

V. Chvátal, 1970

W(2; 3, 4)

18

V. Chvátal, 1970

W(2; 3, 5)

22

V. Chvátal, 1970

W(2; 3, 6)

32

V. Chvátal, 1970

W(2; 3, 7)

46

V. Chvátal, 1970

W(2; 3, 8)

57

M. Beeler e P. O’Neil, 1979

W(2; 3, 9)

77

M. Beeler e P. O’Neil, 1979

W(2; 3, 10)

97

M. Beeler e P. O’Neil, 1979

W(2; 3, 11)

114

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(2; 3, 12)

135

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(2; 3, 13)

160

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(2; 3, 14)

186

Michal Kouril, 2006

W(2; 3, 15)

218

Michal Kouril, 2006

W(2; 3, 16)

238

Michal Kouril, 2006

W(2; 3, 17)

279

Tanbir Ahmed, 2010

W(2; 3, 18)

312

Tanbir Ahmed, 2010

W(2; 3, 19)

349

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 20)

≥ 389

Oliver Kullmann, 2009

W(2; 3, 21)

≥ 416

Oliver Kullmann, 2009

W(2; 3, 22)

≥ 464

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 23)

≥ 516

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 24)

≥ 593

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 25)

≥ 656

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 26)

≥ 727

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 27)

≥ 770

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 28)

≥ 827

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 29)

≥ 868

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 30)

≥ 903

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 31)

> 930

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 32)

> 1006

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 33)

> 1063

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 34)

> 1143

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 35)

> 1204

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 36)

> 1257

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 37)

> 1338

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 38)

> 1378

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 3, 39)

> 1418

Tanbir Ahmed, Oliver Kullmann, e Hunter Snevily, 2011

W(2; 4, 4)

35

V. Chvátal, 1970

W(2; 4, 5)

55

V. Chvátal, 1970

W(2; 4, 6)

73

M. Beeler e P. O’Neil, 1979

W(2; 4, 7)

109

M. Beeler, 1983

W(2; 4, 8)

146

Michal Kouril, 2006

W(2; 4, 9)

309

Tanbir Ahmed, 2011

W(2; 5, 5)

178

R. Stevens e R. Shantaram, 1978

W(2; 5, 6)

206

Michal Kouril, 2006

W(2; 5, 7)

260

Tanbir Ahmed, 2013

W(2; 5, 8)

> 331

Tanbir Ahmed, 2011

W(2; 5, 9)

> 473

Tanbir Ahmed, 2011

W(2; 5, 10)

> 557

Tanbir Ahmed, 2011

W(2; 5, 11)

> 736

Tanbir Ahmed, 2011

W(2; 6, 6)

1132

Michal Kouril e Jerome L. Paul, 2000

W(3; 2, 3, 3)

14

T.C. Brown, 1974

W(3; 2, 3, 4)

21

T.C. Brown, 1974

W(3; 2, 3, 5)

32

T.C. Brown, 1974

W(3; 2, 3, 6)

40

T.C. Brown, 1974

W(3; 2, 3, 7)

80

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(3; 2, 3, 8)

72

Michal Kouril, 2006

W(3; 2, 3, 9)

90

Tanbir Ahmed, 2009

W(3; 2, 3, 10)

108

Tanbir Ahmed, 2009

W(3; 2, 3, 11)

129

Tanbir Ahmed, 2009

W(3; 2, 3, 12)

150

Tanbir Ahmed, 2009

W(3; 2, 3, 13)

171

Tanbir Ahmed, 2009

W(3; 2, 3, 14)

202

Michal Kouril e Jerome L. Paul, 2000

W(3; 2, 4, 4)

40

T.C. Brown, 1974

W(3; 2, 4, 5)

71

T.C. Brown, 1974

W(3; 2, 4, 6)

83

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(3; 2, 4, 7)

119

Michal Kouril, 2006

W(3; 2, 4, 8)

157

Michal Kouril, 2012

W(3; 2, 5, 5)

180

Tanbir Ahmed, 2009

W(3; 2, 5, 6)

246

Michal Kouril, 2012

W(3; 3, 3, 3)

27

V. Chvátal, 1970

W(3; 3, 3, 4)

51

M. Beeler e P. O’Neil, 1979

W(3; 3, 3, 5)

80

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(3; 3, 3, 6)

107

Tanbir Ahmed, 2011

W(3; 3, 3, 7)

> 149

Tanbir Ahmed, 2011

W(3; 3, 3, 8)

> 185

Tanbir Ahmed, 2011

W(3; 3, 3, 9)

> 221

Tanbir Ahmed, 2011

W(3; 3, 3, 10)

> 265

Tanbir Ahmed, 2011

W(3; 3, 4, 4)

89

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(3; 3, 4, 5)

> 163

Tanbir Ahmed, 2011

W(3; 3, 5, 5)

> 243

Tanbir Ahmed, 2011

W(3; 4, 4, 4)

293

Michal Kouril, 2012

W(4; 2, 2, 3, 3)

17

T.C. Brown, 1974

W(4; 2, 2, 3, 4)

25

T.C. Brown, 1974

W(4; 2, 2, 3, 5)

43

T.C. Brown, 1974

W(4; 2, 2, 3, 6)

48

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(4; 2, 2, 3, 7)

65

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(4; 2, 2, 3, 8)

83

Tanbir Ahmed, 2009

W(4; 2, 2, 3, 9)

99

Tanbir Ahmed, 2009

W(4; 2, 2, 3, 10)

119

Tanbir Ahmed, 2009

W(4; 2, 2, 3, 11)

141

P. Schweitzer, 2009

W(4; 2, 2, 4, 4)

53

 

W(4; 2, 2, 3, 12)

163

Michal Kouril

W(4; 2, 3, 3, 3)

40

T.C. Brown, 1974

W(4; 2, 3, 3, 4)

60

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(4; 2, 3, 3, 5)

86

Tanbir Ahmed, 2009

W(4; 2, 3, 3, 6)

115

Michal Kouril

W(4; 3, 3, 3, 3)

76

M. Beeler e P. O’Neil, 1979

W(5; 2, 2, 2, 3, 3)

20

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(5; 2, 2, 2, 3, 4)

29

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 3, 5)

44

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 3, 6)

56

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 3, 7)

72

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 3, 8)

88

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 3, 9)

107

Michal Kouril, 2012

W(5; 2, 2, 2, 4, 4)

54

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 4, 5)

79

Tanbir Ahmed, 2009

W(5; 2, 2, 2, 4, 6)

101

Michal Kouril, 2012

W(5; 2, 2, 3, 3, 3)

41

Bruce M. Landman, Aaron Robertson e C. Culver, 2005

W(5; 2, 2, 3, 3, 4)

63

Tanbir Ahmed, 2009

W(5; 2, 2, 3, 3, 5)

95

Michal Kouril

W(5; 2, 3, 3, 3, 3)

77

Tanbir Ahmed, 2012

W(6; 2, 2, 2, 2, 3, 3)

21

Tanbir Ahmed, 2009

W(6; 2, 2, 2, 2, 3, 4)

33

Tanbir Ahmed, 2009

W(6; 2, 2, 2, 2, 3, 5)

50

Tanbir Ahmed, 2009

W(6; 2, 2, 2, 2, 3, 6)

60

Tanbir Ahmed, 2009

W(6; 2, 2, 2, 2, 4, 4)

56

Tanbir Ahmed, 2009

W(6; 2, 2, 2, 3, 3, 3)

42

Tanbir Ahmed, 2009

W(7; 2, 2, 2, 2, 2, 3, 3)

24

Tanbir Ahmed, 2009

W(7; 2, 2, 2, 2, 2, 3, 4)

36

Tanbir Ahmed, 2009

W(7; 2, 2, 2, 2, 2, 3, 5)

55

Tanbir Ahmed, 2009

W(7; 2, 2, 2, 2, 2, 3, 6)

65

Tanbir Ahmed, 2012

W(7; 2, 2, 2, 2, 2, 4, 4)

66

Tanbir Ahmed, 2012

W(7; 2, 2, 2, 2, 3, 3, 3)

45

Tanbir Ahmed, 2012

W(8; 2, 2, 2, 2, 2, 2, 3, 3)

25

Tanbir Ahmed, 2009

W(8; 2, 2, 2, 2, 2, 2, 3, 4)

40

Tanbir Ahmed, 2011

W(8; 2, 2, 2, 2, 2, 2, 3, 5)

61

Tanbir Ahmed, 2012

W(8; 2, 2, 2, 2, 2, 2, 3, 6)

71

Tanbir Ahmed, 2012

W(8; 2, 2, 2, 2, 2, 3, 3, 3)

49

Tanbir Ahmed, 2012

W(8; 2, 2, 2, 2, 2, 2, 4, 4)

67

Tanbir Ahmed, 2012

W(9; 2, 2, 2, 2, 2, 2, 2, 3, 3)

28

Tanbir Ahmed, 2009

W(9; 2, 2, 2, 2, 2, 2, 2, 3, 4)

42

Tanbir Ahmed, 2012

W(9; 2, 2, 2, 2, 2, 2, 2, 3, 5)

65

Tanbir Ahmed, 2012

W(9; 2, 2, 2, 2, 2, 2, 3, 3, 3)

52

Tanbir Ahmed, 2012

W(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

31

Tanbir Ahmed, 2012

W(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)

45

Tanbir Ahmed, 2012

W(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)

70

Tanbir Ahmed, 2012

W(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

33

Tanbir Ahmed, 2012

W(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)

48

Tanbir Ahmed, 2012

W(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

35

Tanbir Ahmed, 2012

W(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)

52

Tanbir Ahmed, 2012

W(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

37

Tanbir Ahmed, 2012

W(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)

55

Tanbir Ahmed, 2012

W(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

39

Tanbir Ahmed, 2012

W(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

42

Tanbir Ahmed, 2012

W(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

44

Tanbir Ahmed, 2012

W(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

46

Tanbir Ahmed, 2012

W(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

48

Tanbir Ahmed, 2012

W(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

50

Tanbir Ahmed, 2012

W(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)

51

Tanbir Ahmed, 2012

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.