978-5-4439-2489-2 Райгородский Линейно алгебраический метод в комбинаторике


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
..
-

,



2016
519.1
22.15
18
..
-

.:,2015
144.
ISBN978-5-4439-2489-2
-
.XX
-
,

.

-.

,,,
-
.


.


-
.,
-
,

.
:
..
-.
.:,2015.2-.,.144.ISBN978-5-4439-02
75-3


119002,,.,11,
.(499)2410804.
http://www.mccme.ru
ISBN978-5-4439-2489-2
c
\r
..,2016.
c
\r
,2016.

1.
5
2.
8
2.1.
.............................8
2.2.........10
2.3.1
5
2.4..............18
2.5.3................25
3.
30
3.1.
...........................30
3.2.11..................33
3.3.11.................36
3.4.11?......................42
3.5.11.......................52
3.6.12...............59
4.

61
4.1...................61
4.2.............65
4.3..........................74
4.4.....82
4.5.....86
4.6........92
5.
100
5.1............100
5.2.20..................108
6.
111
6.1....1
11
4

6.2.23..................114
6.3.24..................117
6.4.1.B............121
6.5.2...123
7.
131
7.1.....................131
7.2.....................133
7.3.
f
(
n
,2)
6
4
n

2
......135
7.4.
f
(
n
,2)
6
4
n

3
......137

141
1

,

.

,,
-
,-,

.
-
,

,
-
.,

,
.
,

(..)
,-
,,,.
,
,,
-
,,

,

.,


-
.,

,
-
,.,,
-
,

-,
-
,
-
,


.-
,

,
(
).
,

.XX
-

-
(,

.),

.
6
1.

-

-
,,,
-
,.
-
,
-
,
-
,.
,
?
,
.,-
-

,
.,

.,

-,

.
,
-


,,,

.,
,
,,(

)1998(.[35]),

,(.[1]),

(!)(.[36]).,

,.


,

.,
-
,.
-
,
-
.,




.,-
.
,
.
,-
-
,
-
-.

;

,,
-
().
,

.
-
1.
7
,(
,
).

.,
,
,,

,..
-
.

.
2


2.1.


.
R
n
-
,
n
.,-
,
R
n
=
f
1,
:::
,
n
g
.
R
n
-
()
M
=
f
M
1
,
:::
,
M
s
g
,
:


M
i
\
M
j


=1
-

i
,
j
2f
1,
:::
,
s
g
.
,,,
j
M
i
j
=3

i
2f
1,
:::
,
s
g
,

jMj
=
s
(,

M
i
).,
s
6
C
3
n
.

M
(3-
R
n
)-
,,

.
,

M
-
,,,:


s
=
jMj
?

-

(
),

.,,

,

.
,,

.,,

.
,
.,


-
.,

,,-,
-
,60-.
2.1.

9
1(.,[48]).

M
,


R
n
,
-
,
s
=
jMj
6
n
0
,

n
0
=
n

n
=4
k
,
n
0
=
n

1

n
=4
k
+1,
n
0
=
n

2

n
=4
k
+2

n
=4
k
+3
:
,
k
.
,
n
4
,,.

.

,
:
n

i
(mod
p
)
(
n

i

p
),
n

i

p
,1,
n
=
pk
+
i
(
i


n

p
).
,,.
,
n
-

M
,,,

n
0
(!).
,,
:
,,


,;

,,1

.,-
,
,

,.,
,
1,,

.
-,
M
=
f
M
1
,
:::
,
M
s
g
-
()
R
n
.
,
j
M
i
j
=
k
,
i
=1,
:::
,
s
,
k
-
.,,-


t
,
0
6
t
6
k
,


M
i
\
M
j


=
t
,
i
=
j
,
i
,
j
2f
1,
:::
,
s
g
.
m
(
n
,
k
,
t
)

max
jMj
,

M
-
.,
m
(
n
,3,1)
,1.-
,
m
(
n
,
k
,
t
)

.
10
2.
-,
m
(
n
,
k
,
t
)
,
,.
,,


m
(
n
,
k
,
t
)

.,

.
,
,,
k
=5
,
t
=2
.
,
k
=
k
(
n
)

t
=
t
(
n
)
,,
k
=[
n=
2]
,
t
=[
n=
4]
!:
XX
-
...
-
-,
m
(
n
,
k
,
t
)

n
,
k
,
t
.
.

.

,,-


,-
.2.2..2.3
,,,
,
.,

.,.2.4
-


,

()

-.,.2.5

.2.4.
,
2(...,[42]).

p


,
n
=4
p
,
k
=2
p
,
t
=
p
.
m
(
n
,
k
,
t
)
6
2
C
p

1
n

1
:
,-
.

(..2.3).,
-
,,

.
2.2.
.

M
=
f
M
1
,
:::
,
M
s
g

k
-
R
n
,
k
=2
p
,
n
=4
p
,
2.2.
11

M
i
,
M
j
2M

p

R
n
..

M
,
1
2R
n
,,
.
,
M

,
M
1
=
f
M
2M
:1
2
M
g

M
2
=
f
M
2M
:1
62
M
g
:
,
jM

j
6
C
p

1
n

1
,

=1,2
,
2.,

.

,


M
2
.
M
1
.
..
,,
N
=
M
2
=
f
N
1
,
:::
,
N
s
g

k
-
R
n
nf
1
g
,

R
n

1
=
f
1,
:::
,
n

1
g
.


N
i
\
N
j


=
p

i
,
j
2f
1,
:::
,
s
g
:
,,

,
k
-
R
n

1
-


C
p

1
n

1
,
.

,,


N

,,,

,..

C
p

1
n

1
.-,
-
?.

A
1
,
:::
,
A
C
j
n

1

j
--
,
B
1
,
:::
,
B
C
i
n

1

i
--

R
n

1
.,
0
6
i
6
j
6
n

1
,

i

j
:-
-

,
-
,()
C
0
m
=
m
!
m
!0!
=1
,
12
2.
,
C
l
m
=0
,
l�m
,
m

0
(,
C
0
0
=1
,
,,
C
5
3
=0
).

(
i
,
j
)

C
i
n

1
(
)
C
j
n

1
(),
(
u
,
v
)
-

u
,
v
(
i
,
j
)
,
B
u

A
v
,.

u

v
:
1
6
u
6
C
i
n

1
,1
6
v
6
C
j
n

1
:
,
(
i
,
j
)

i
=
j
:
,..
(
i
,
j
)=
E
(
i
,
j
)=
E
=
0
B
B
B
B
B
@
10
:::
0
01
:::
0
.
.
.
.
.
.
.
.
.
.
.
.
00
:::
1
1
C
C
C
C
C
A
,
.,
i
6
j
,
.,,

,
(0,1)
-.

i
=
p

1
,
j
=
k
.
x
1
,
:::
,
x
C
p

1
n

1
,-

(
p

1,
k
)
.
C
k
n

1
-,
R
C
k
n

1
.

x
1
,
:::
,
x
C
p

1
n

1


R
C
k
n

1
.

,,
,,..

C
p

1
n

1
.
.
-

1)
.
1.

i
2f
0,
:::
,
p

1
g

(
i
,
p

1)(
p

1,
k
)=
C
p

1

i
k

i
(
i
,
k
)
:
1.
-,,-
,,
,-
:
(
i
,
p

1)

1)
,

,,...
.-
2013

,

.

,.-

!
2.2.
13
B
u
A
v
.1

(
p

1,
k
)
.,-

(
i
,
k
)
,..-

C
i
n

1

C
k
n

1
.-
.
u
-
i
-
B
u

v
-
k
-
A
v

R
n

1
,
(
u
,
v
)
-

u
,
v
(
i
,
k
)

(
i
,
k
)
.

(
p

1)
-
R
n

1
,
B
u
,

A
v
(..1).,

(
u
,
v
)
-
.(
u
-
i
-
B
u

v
-
k
-
A
v

R
n

1
)-
,


(
p

1)
-
R
n

1
,,-
,
B
u

A
v
(..2).,

C
p

1

i
k

i
,1.
B
u
A
v
.2
1-
-

(
i
,
k
)
,
i
=0,
:::
,
p

1
,

.
2.

i
2f
0,
:::
,
p

1
g

(
i
,
k
)
T
(
i
,
k
)=(
i
,
k
)
:

T
,
(
i
,
k
)

C
k
n

1

C
k
n

1
,-

\r
u
,
v
(
i
,
k
)=
C
i
j
A
u
\
A
v
j
,1
6
u
,
v
6
C
k
n

1
(
j
A
u
j
=
j
A
v
j
=
k
)
:
14
2.
2
-
1,.,
-
-
,

k
-
A
u
,
A
v

i
.,-

(
i
,
k
)

i
2f
0,
:::
,
p

1
g

-
(
i
,
k
)
,,
1,

.,
(
i
,
k
)
,
i
=0,
:::
,
p

1
,
.
3.

x
-

p

1
Y
i
=1
(
i

x
)

p

1
X
j
=0
(

1)
j
+1
C
j
x
(mod
p
)
:
3.

x
=0
-

(
p

1)!
.
(.[3],)
(
p

1)!

1(mod
p
)
.


C
0
0
=

1
,
.
x
2f
1,
:::
,
p

1
g
,.

x
X
j
=0
(

1)
j
+1
C
j
x
=

(1

1)
x
=0,
,.


x

p
(,

p
).(.[3]),,
,.3.

=
P
p

1
i
=0
(

1)
i
+1
(
i
,
k
)
(-
).
(
u
,
v
)
-
\r
u
,
v


:
\r
u
,
v
=
p

1
X
i
=0
(

1)
i
+1
C
i
j
A
u
\
A
v
j
:


,,-


.,
rank

6
dim

6
C
p

1
n

1
:

(
N
)
,
\r
u
,
v
,-

A
u
,
A
v
2N
(,,,
2.3.
15
A
u
,
A
v
,
N

k
).-
3
\r
u
,
v
=
p

1
X
i
=0
(

1)
i
+1
C
i
j
A
u
\
A
v
j

p

1
Y
j
=1
(
j
j
A
u
\
A
v
j
)
:

A
u
,
A
v

N
,

k
=2
p
(
,

R
n

1
).
p
.
,
j
A
u
\
A
v
j
0(mod
p
)
,
A
u
=
A
v
(..
u
=
v
).,(

p
),
\r
u
,
u
6
0(mod
p
)
,
\r
u
,
v

0(mod
p
)

u
=
v
(,).,
-
p
,
det(
N
)
6
0
(mod
p
)
,
det(
N
)
=0
.,

jNj
=
rank
(
N
)
6
rank

6
C
p

1
n

1
,
.
2.3.

,-
.
,
,
-
,

.

,,
n
!

p
2
n

n
e

n
:


=3,1415
:::
,
e
=2,7182
:::
,


,
,..
n
!
p
2
n
n
e
n
!
1

n
!1
:
,,
-
,,
2
C
p

1
n

1
.,
16
2.
p
=
n=
4
.,
2
C
p

1
n

1
=2
(
n

1)!
n
4

1
!
3
n
4
!
=2
n=
4
n
n
!
n
4
!
3
n
4
!


1
2
p
2
nn
n
e

n
2

n
4
n
4
n=
4
e

n=
4
2

3
n
4
3
n
4
3
n=
4
e

3
n=
4
:
,(
e
),-

n
\rn
.
p
2
p
3
n

4
3
3
=
4

n
=

4
3
3
=
4
+
o
(1)

n
=(1,754
:::
+
o
(1))
n
:
,
2
p
--

4
p
-,
(


p
),
(1,754
:::
+
o
(1))
n
.
,

C
n=
2
n
=
n
!
n
2
!
2

p
2
nn
n
e

n
r
2

n
2
n
2
n=
2
e

n
2
2
=(2+
o
(1))
n
:
:-
.

,-
,,
-
.,
,
,
-
.
.
,.,


M
,,
,
jMj
=(1,754
:::
+
o
(1))
n
.,

jMj
,
.
R
n


R
n
=
R
1
tR
2
,
R
1
=
n
1,
:::
,
n
2
o
,
R
2
=
n
n
2
+1,
:::
,
n
o
,

t
,


,.
2.3.
17

N
=
C
[3
n=
8]+1
n=
2
,
M
1
=
f
M
1
1
,
:::
,
M
1
N
g

([3
n=
8]+1)
-

R
1
,
M
2
=
f
M
2
1
,
:::
,
M
2
N
g
(
n=
2

[3
n=
8]

1
)--

R
2
.,
jM
1
j
=
jM
2
j
=
N:

3
n=
8
:
n

8.,
n=
4=
p
,
p
,-
8,,

n=
4
:
-
,,,

.

M
1
i
t
M
2
j
,
i
,
j
=1,
:::
,
N:

s
=
N
2

M
1
,
:::
,
M
s
,
n=
2
.
,


M
i
\
M
j



n
4

i
,
j
2f
1,
:::
,
s
g
,.,

s
=(1,754
:::
+
o
(1))
n
.-
,
h
3
n
8
i
=
3
n
8

"
,

"
2
[0,1)
:


=1

"
.
jMj
=
N
2
=

C
[3
n=
8]+1
n=
2

2


0
B
B
@
2

n
2
n
2
n=
2
e

n=
2
2

3
n
8
+

3
n
8
+

3
n
8
+

e

3
n
8


2

n
8


n
8


n
8


e

n
8
+

1
C
C
A
2
:


3
n
8
+


3
n
8
+

.

3
n
8

3
n
8
+


1+

3
n=
8

3
n
8
+

:
18
2.
,
-
(,


n
,
n
)

(3
n=
8)
3
n=
8
.-
.,
P
(
n
)
,
,

jMj
P
(
n
)
0
B
@
n
2
n=
2
3
n
8
3
n=
8
n
8
n=
8
1
C
A
2
=(1,754
:::
+
o
(1))
n
:

M
.-
,,
-
,:
-

n=
4
,.
,
n=
4


n=
4
,,
?,
n=
4
-
?,,,

m
(
n
,
k
,
t
)

t
,
.


,,,
-
.
2.4.
.
3(...,[42]).

k
6
n
2

k

t
.
k

2
t
+1
,

m
(
n
,
k
,
t
)
6
6
C
k

t

1
n
.,
d
=2
t

k
+1
,

m
(
n
,
k
,
t
)
6
C
d
n
C
t

d
n

d
C
d
k
:
,
-
3.-,,2
-
.,
n
=4
p
,
k
=2
p
,
t
=
p
,,
,
k

t
=
p
(),
,32:,
,
2.4.
19
.,
k
=2
p
2
t
+1=2
p
+1
,
,,

3.
d
=1
,
m
(
n
,
k
,
t
)
6
n
k
C
t

1
n

1
=2
C
p

1
n

1
,
.,3
.,,,

,

k
,
t
,

2.
-
.

-,,

.2.2.
,.-
3,-.
-
,
k
=3
,
t
=1
,,,
k

t
=2
.

k
=3
6
2
t
+1=3
,
m
(
n
,3,1)
6
C
1
n
=
n
.
,


n

4
,
.,,
m
(
n
,5,2)
?:
-
,
m
(
n
,5,2)
6
C
2
n
,-
.,

.,,
-

R
n
,
R
n
(
1,2,3
),
C
2
n

3

C
2
n
-
:,.2.3,
.
,
-
,

.2.5.

.,

.,

.,
-
(),
,
.
,
,
x

2
x
.
,

.


,-
,,
-
,

20
2.

f
(
x
)
,
x

x
0

x

x
+
f
(
x
)
.-
,
f
(
x
)

O
(
p
x
(log
x
)
\r
)

\r�
0
.

f
(
x
)=
O
(
x

),

�
1
2
:
,

=0,525
(.[38]),


.
f
(
x
)=
O
(
x
0,525
)

,,,.

,
f
(
x
)=
o
(
x
)
,-


,-
1896...
(.[4]):


(
x
)
,
x
,


(
x
)=(1+
o
(1))
x
ln
x
:
,
-
,
.
,

(),,


-
.

,
-
-.

.
,

.
4(...,[42]).

q
=
p


.
-

M
=
f
M
1
,
:::
,
M
s
g
,

k
--

R
n

:


M
i
\
M
j


6
k
(mod
q
)

i
=
j
,
i
,
j
2f
1,
:::
,
s
g
.
s
=
jMj
6
C
q

1
n
.
5(...,[42]).

0
6
l
1
l
2

:::l
r
6
n
.
M
=
f
M
1
,
:::
,
M
s
g
,
-

R
n

:


M
i
\
M
j


2f
l
1
,
:::
,
l
r
g

[1]
.
,
.
.-
.,2006.
[2]
.
,
.
..:.-
,2007.
[3]
..
..;:־-
,2003.
[4]
..
,
..
,
..

..:-,1995.
[5]
..

(0,1)
-
(

1,0,1)
-
//
.2012..4.,.1..91

110.
[6]
..
,
..
,
..
,
-
..

//..2009..200
,
.6..3

22.
[7]
.
..:,1984.
[8]
..
,
..
,
..
,
-
..
м-
//.2014.
.457,.2..144

146.
[9]
.
,
.
..:,1988.
[10]
-..
,
...
,-
..:,1979.
[11]
..
,
..

//

.2013..49,.4.C.98

104.
[12]
..
,
..

//.2
013.
.68,.5..183

184.
142

[13]
..
,
..


f
1,0,1
g
n


//..2014..96,1.C.138

147.
[14]
..
//.
1999..54,.2..185

186.
[15]
..

//.2001..56,.
1.
.107

146.
[16]
..
..:,2015.
[17]
..
-
//.2004..59,.3..177

178.
[18]
..

l
q
-//.2004..59,.5..161

162.
[19]
..
..:,2015.
[20]
..
,
..
-

R
n

k


l
1
//.2006..7,.4(20).
.105

113.
[21]
..
//
.2007.(;.23)..147

164.
[22]
..
--
..:,2007.136.
[23]
.,.
,
..()
-

-
//
..2008..199,.4.C.107

142.
[24]
.,.
,
..()
-
//
..2008..83,.4..636

639.
[25]
..
,
..()
-

-
//
..2008..199,.4..107

142.
[26]
..
,
..
,-
//
..2008..84,.2.C.254

272.

143
[27]
..
,
..

,//
.2011..66,.5..109

182.
[28]
..
,
..

(

1,0,1)
-

-
//..29..:
-,2013..130

146.
[29]
..
..:,
2002.
[30]
..

..;:,2003.
[31]
.
..:,1973.
[32]
..
..:
,2004.
[33]
.
..:,1970.
[34]
.
,
.
.
.:,1976.
[35]
AignerM.
,
ZieglerG.M.
ProofsfromTHEBOOK.Berlin:Springer-
Verlag,1998.
[36]
AignerM.
,
ZieglerG.M.
ProofsfromTHEBOOK.4ed.Berlin:
Springer-Verlag,2010.
[37]
AhlswedeR.
,
KhachatrianL.H.
Thecompleteintersectiontheoremfor
systemsoffinitesets//Europ.J.Combin.1997.Vol.18.P.1
25

136.
[38]
BakerR.C.
,
HarmanG.
,
PintzJ.
Thedierencebetweenconsecutive
primes,II//ProceedingsoftheLondonMathematicalSociet
y.2001.
Vol.83.P.532

562.
[39]
CherkashinD.D.
,
KozikJ.
Anoteonrandomgreedycoloringof
uniformhypergraphs.RandomStructures&Algorithms,2014
.
[40]
ChevalleyC.
Demonstrationd'unehypothesedeM.Artin//Abhand-
lungenausdemMathematischenSeminarderUniversitatHamb
urg
(inFrench).1935.Vol.11.P.73

75.
[41]
ErdosP.
,
GinzburgA.
,
ZivA.
Theoremintheadditivenumber
theory//Bull.Res.CouncilIsrael.1961.Vol.10.P.41

43.
[42]
FranklP.
,
WilsonR.
Intersectiontheoremswithgeometricconsequen-
ces//Combinatorica.1981.Vol.1.P.357

368.
144

[43]
GrahamR.L.
,
RothschildB.L.
,
SpencerJ.H.
Ramseytheory.N.Y.:
JohnWilyandSons,1990.2nded.
[44]
HiltonA.J.W.
,
MilnerE.C.
Someintersectiontheoremsforsystems
ofnitesets//Quart.J.Math.OxfordSer.(2).1967.Vol.18
.
P.369

384.
[45]
KleitmanD.J.
Familiesofnon-disjointsubsets//J.ofCombin.
Theory.1966.Vol.1.P.153

155.
[46]
KupavskiiA.B.
Onthechromaticnumberof
R
n
withanarbitrary
norm//DiscreteMath.2011.Vol.311.P.437

440.
[47]
LarmanD.G.
,
RogersC.A.
Therealizationofdistanceswithinsets
inEuclideanspace//Mathematika.1972.Vol.19.P.1

24.
[48]
NagyZ.
AcertainconstructiveestimateoftheRamseynumber//
MatematikaiLapok.1972.Vol.23,301

302.P.26.
[49]
PeresY.
,
SchlagW.
TwoErdosproblemsonlacunarysequences:
ChromaticnumberandDiophantineapproximation//Bull.Lo
nd.
Math.Soc.2010.Vol.42,2.P.295

300.
[50]
RaigorodskiiA.M.
TheBorsukpartitionproblem:theseventieth
anniversary//MathematicalIntelligencer.Vol.26.2004.
4.P.4

12.
[51]
RaigorodskiiA.M.
ThreelecturesontheBorsukpartitionproblem//
LondonMathematicalSocietyLectureNoteSeries.2007.Vol
.347.
P.202

248.
[52]
RaigorodskiiA.M.
ColoringDistanceGraphsandGraphsofDiame-
ters//ThirtyEssaysonGeometricGraphTheory,J.Pached.
Springer,2013.P.429

460.
[53]
RaigorodskiiA.M.
Cliquesandcyclesindistancegraphsandgraphsof
diameters//DiscreteGeometryandAlgebraicCombinatoric
s.2014.
(AMS,ContemporaryMathematics;Vol.625).P.93

109.
[54]
WarningE.
BemerkungzurvorstehendenArbeitvonHerrnChe-
valley//AbhandlungenausdemMathematischenSeminarderU
niver-
sitatHamburg(inGerman).1936.Vol.11.P.76

83.
[55]
ZieglerG.M.
ColoringHamminggraphs,optimalbinarycodes,and
the
0
=
1
Borsukprobleminlowdimensions//Lect.NotesComput.
Sci.2001.Vol.2122.P.159

171.
Новинки издательства МЦНМО:
http://biblio.mccme.ru/publications/b
ooks/status/novelties
Интернет
партнеры:
http://globalf5.com/search/founded/t
ype/book/area/publisher/stype/exten
ded/q/МЦНМО
http://www.litres.ru/mcnmo/
ага
зин «Математическая
книга» при издательстве:
http://biblio.mccme.ru/shop
Описания, обсуждения, ответы
на вопросы:
https://vk.com/matematura

Приложенные файлы

  • pdf 8930749
    Размер файла: 466 kB Загрузок: 0

Добавить комментарий