WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА


   Добро пожаловать!


Pages:     | 1 |   ...   | 4 | 5 || 7 |

42 путями приходят к совершенно одинаковым оценкам, но то, что Теорема. Пусть p — простое число, m=4p, а n=m2. Тогда эти оценки остаются слабыми, вовсе не удивительно. Особенно ин- имеет место неравенство тересно тут, кстати сказать, что же Бургейн и Линденштраусс те C2p установили неравенство g1(n) 1,067+o(1) n. Это означает, что m f(n).

4Cp с проблемой Грюнбаума всё гораздо легче, чем с проблемой Борсуm ка, ведь если в случае с g1(n) мы знаем, что Выглядит теорема совершенно комбинаторно (биномиальные n коэффициенты); однако остаётся масса вопросов, и основной из 1,067+o(1) ng1(n) 3/2+o(1), них состоит даже не в том, откуда теорема взялась, но в том, почему из теоремы вытекает опровержение гипотезы. Вопрос абсот. е. что зазор между верхней и нижней оценками сравнительно лютно правомочный, и сперва мы обсудим именно его. Запишем невелик (всё упирается в подсчёт константы в основании экспоненбиномиальные коэффициенты по известной всем формуле, т. е. четы), то в случае с f(n) известно лишь, что рез факториалы. Получится выражение 1,2255+o(1) nf(n) 3/2+o(1) n.

C2p m! p!(m-p)! m = ·.

4Cp (2p)!(m-2p)! 4m! m 14. КОНТРПРИМЕРЫ К ГИПОТЕЗЕ БОРСУКА Теперь следует применить к факториалам замечательную формулу Стирлинга, которая гласит, что с ростом натурального числа k его В предыдущих главах мы постарались максимально подробно факториал ведет себя примерно так же, как функция изложить большинство из доказанных к настоящему времени по k k ложительных фактов относительно гипотезы Борсука. Очевидно, 2k.

что фактов много и что, более того, направлений для дальнейшей e деятельности предостаточно. Однако всему когда-нибудь приходит Здесь числа и e — это именно те числа, о которых все наверняка конец, и, хотя в нашем случае его наступление скорее <безвременподумали, а строгий смысл слов <примерно так же> заложен в записи но>, ибо обусловлено оно сравнительно невысоким уровнем нашей подготовки, всё же мы иссякли, и пора нам заняться отрица k k 1+o(1) k.

, тельными результатами — построением контрпримеров гипотезе k!= 2k nк e и доказательством нижних оценок вида f(n) c+o(1). И тут мы снова столкнёмся с нетривиальной комбинаторно-геометрической Иначе говоря, отношение факториала и упомянутой функции стреприродой нашей задачи: если прежде мы имели дело и с чистой мится к единице, коль скоро k стремится к бесконечности. Форгеометрией, и с комбинаторикой, то теперь комбинаторный аспект мула Стирлинга доказывается в курсе математического анализа проблемы раскроется, так сказать, по полной программе.

довольно сложно, и тем не менее кое-какие похожие результаты Мы однажды отмечали уже, что все отрицательные факты делаются <вручную> (см. задачи).

основаны на построении весьма любопытных конечных систем Итак, рутинные, но с использованием формулы Стирлинга совекторов в пространстве. С высоты наших новых знаний можно всем простые, выкладки показывают, что сказать, что, по сути, речь пойдёт о многогранниках (см. задачу из главы 8). Так оно звучит геометричнее, а впрочем, разницы ни- m C2p m =P(m) 1 m/42 3 3m/4 = 1,139...+o(1) m.

какой нет: главное — опровергнуть гипотезу. Правильно было бы 4Cp m сказать, что комбинаторика, которую мы начнём изучать вскоре, 4 · относится к так называемой экстремальной теории гиперграфов.

Конечно, звучит красиво, но понятнее не становится. Просто знать Здесь P(m) — это выражение, в которое входят только корни из ветерминологию никогда не вредно, а смысл будет ясен и так. личин вида 2k с тем или иным k, и мы не забываем, что p=m/4.

Дабы сделать метод более прозрачным, мы не станем При этом последнее равенство следует воспринимать на интуитив обосновывать самую <передовую> оценку f(n) 1,2255...+o(1) n. Вместо ном уровне, коль скоро теория пределов вызывает формальные этого мы обсудим следующую теорему. трудности: очевидно ведь, что как P(m), так и o(1) крайне мало 44 влияют на поведение экспоненты типа (1,139...)m. Таким образом, Лемма была доказана П. Франклом и Р. Уилсоном в 1981 году теорема утверждает, что с помощью весьма тонкого и красивого линейно-алгебраического метода в комбинаторике. Мы не имеем возможности изложить этот n f(n) 1,139...+o(1) m= 1,139...+o(1), метод здесь, но комментарии к лемме мы сейчас приведём.

Во-первых, если приглядеться, то можно узнать в лемме обоби всё в порядке. Здесь, кстати, можно и n подобрать, начиная щение довольно хорошо известной задачи. А именно: рассмотрим с которого в R не 2p-сочетания, но 3-сочетания, никакие два из которых не C2p m пересекаются по одному общему элементу. С помощью математи>n+1.

4Cp m ческой индукции легко показать, что, грубо говоря, количество таких 3-сочетаний не превосходит m (см. брошюру [1] и задаК сожалению, такое n огромно (оно куда больше, чем 2014), и мы чи). Тем самым, один запрет опять-таки даёт сильный результат:

предоставляем читателю отыскать его.

от C3 мы переходим сразу к m. Пафос подхода, предложенного m Здесь есть ещё один тонкий момент, который следует подчеркФранклом и Уилсоном, как раз в том и состоит, что в их синуть сразу. Дело в том, что фактически мы доказываем оценку туации никакая индукция уже не работает. Работает линейная н е д л я в с е х n, а лишь для тех, которые могут быть предалгебра, которая нам, к несчастью, недоступна. Вообще, похожие ставлены в виде n=m2 с m=4p, где p — простое. Эту проблему задачи рассматривались давно, и поначалу никому просто не приможно преодолеть за счёт весьма нетривиальной техники, которая ходило в голову использовать их в комбинаторной геометрии. Еще относится к аналитической теории чисел. Разумеется, мы не станем в 60-е годы XX века многие смежные вопросы были сформулировдаваться в подробности, но удержаться от упоминания некоторых ваны П. Эрдешем (ср. задачи и брошюру [1]), и именно их принято красивейших фактов мы не в силах. Они таковы: количество простых объединять термином <экстремальная теория гиперграфов> (гиперчисел, не превосходящих заданного числа k, ведёт себя примерно графом называют совокупности множеств (вершины — элементы, так же, как и величина k/ ln k (смысл слова <примерно> прежний);

а рёбра — сами множества)).

найдётся такая постоянная величина c, что между k и k+ck39/Во-вторых, оценка в лемме <почти точна>. Это значит, что есть хотя бы одно простое число при любом натуральном k. Вообможно подобрать такую совокупность M, удовлетворяющую всем ще, законы, которым подчиняется распределение простых чисел, условиям леммы, что в ней будет практически 2Cp элементов m крайне замысловаты, и многие задачи, связанные с ними, до сих (см. задачи). Остаётся некоторая странность, связанная с выбопор не решены. Однако нам хватит и упомянутых фактов.

ром параметров: отчего мы p берём простым Почему бы нам не Наконец-то мы готовы заняться собственно комбинаторикой.

взять абы какое число Это и впрямь непонятно. Метод ФранОсновной при доказательстве теоремы является следующая лемма.

кла—Уилсона работает только в предположении простоты, а ничеЛемма. Пусть R={1,..., m} — множество, состоящее из m элего лучшего никто пока не придумал.

ментов. Рассмотрим в R произвольную совокупность подмно Для наших дальнейших целей удобнее будет научиться мыжеств (сочетаний) M = M1,..., Ms, обладающую свойствами:

слить не в терминах сочетаний, а в терминах векторов. Пусть |Mj|=2p (то есть Mj — 2p-сочетание) для каждого j{1,..., s};

дано какое-то 2p-сочетание M в R. Сопоставим ему (0, 1)-век|MiMj|=p при любых i, j. Тогда тор x=(x1,..., xm), у которого xi=1, если iM, и xi=0 в про тивном случае. Понятно, что мощности пересечения множеств s=|M |2Cp-1<2Cp.

m m M, NR, которым сопоставлены векторы x, y, отвечает тогда На первый взгляд, лемма совершенно невероятна. Действи- величина (x, y)=x1y1+...+xmym. Эту величину называют скаляр тельно, мы взяли произвольную совокупность 2p-сочетаний в мно- ным произведением векторов. Отметим, что, в частности, жестве из вдвое большего числа элементов и наложили на MjM |x-y|2=(x, x)+(y, y)-2(x, y) всего одно ограничение, состоящее в том, что эти сочетания не могут пересекаться ровно по p общим элементам. Казалось бы, (проверьте это!), причём у нас и (x, x), и (y, y) (скалярные квадра ограничение очень слабое. Ан нет: если без него s вполне может ты) равны 2p. В конечном итоге имеем новую лемму.

оказаться равным C2p, то с ним s обязано быть в э к с п о н е н ц иm Лемма. Пусть а л ь н о е (как мы выяснили выше) число раз меньше. Один-един ственный запрет, и совокупность катастрофически <тощает>. V= (x1,..., xm): xi{0, 1}, i=1,..., m; x1+...+xm=2p.

46 Тогда каково бы ни было множество QV, в котором скалярное которых — нуль, а значит, diam Wi =diam W, что невозможно.

произведение любых двух векторов не совпадает с p, мощность Q Посему не превосходит 2Cp-1.

m C2p m f(n)f, Ей эквивалентна 4Cp m Лемма. Пусть и теорема доказана.

W= (x1,..., xm): xi{-1, 1}, i=1,..., m; x1+...+xm=0.

Стоит сказать несколько слов о том, как можно улучшать установленную нами оценку. Прежде всего, ясно, что пытаться Тогда каково бы ни было множество QW, в котором скалярное усиливать лемму бессмысленно. Вернее, её, конечно, удастся улучпроизведение любых двух векторов не равно нулю, мощность Q шить, но все подобные улучшения повлияют лишь на вид <о мане превосходит 2Cp-1.

m лого> (и на минимальную размерность контрпримера); константа Каждому вектору x=(x1,..., xm)W поставим в соответствие же (1,139) изменений не претерпит. Значит, нужны другие идеи.

вектор Во-первых, есть очень простое соображение, которое, впрочем, xx=(x2, x1x2,..., x1xm, x2x1,..., x2xm,..., xmx1,..., x2 ), не вполне элементарно. Дело в том, что, когда мы осуществляли 1 m переход от W к W, мы считали, что W m2. Так-то оно, безт. е. вектор, лежащий в пространстве размерности m2=n. В реусловно, так, да только, вообще-то, можно сказать гораздо больше:

зультате получится новое семейство векторов W n. Нетрудно W Cm. Читателя подобное обстоятельство наверняка удивит.

видеть, что Действительно, как может вектор с m2 координатами иметь более 1 чем вдвое меньшую размерность Но ведь если речь идёт о плос|W|= |W|= C2p m 2 2 кости или об 3, то нас не удивляет, что некоторые множества имеют размерность 1 или 2. Примерно то же и здесь: соотноше(векторы xx и -x(-x) совпадают).

ния xixj=xjxi и x2=1 задают подпространство m2 надлежащей i Найдём расстояние между произвольными двумя векторами размерности, и этим-то всё и объясняется. Если поверить в такие xx и yy из W в терминах их скалярного произведения:

нестрогие рассуждения и положить n=C2, так что m 2 n, то m окажется, очевидно, что |xx-yy|2=(xx, xx)+(yy, yy)-2(xx, yy).

2n n Понятно, что f(n) 1,139...+o(1) 1,203...+o(1).

m m m Последнее неравенство, как мы знаем, принадлежит Кану и Калаи, (xx, yy)= xixjyiyj= xiyi =(x, y)2.

оставаясь в то же время не самым лучшим из известных. Что же делать i=i=1 j=Можно рассмотреть такую — абсолютно общую — конструкцию. Положим Таким образом, расстояние между векторами xx, yyW мак {i: W= x=(x1,..., xm): xi{b1,..., br} ; xi=bj} =lj.

симально (на векторах xx, yy достигается диаметр W) тогда и только тогда, когда скалярное произведение их прообразов Имеется в виду, что W состоит из всевозможных векторов, у каx, yW равно нулю.

ждого из которых ровно l1 координат совпадает с b1, ровно l2 коорПредположим, W представлено в виде динат — с b2, и т. д. вплоть до lr координат, равных br. Разумеется, W=W1...Wf, b1,..., br, и l1+...+lr =m. Понятно, что где diam Wi

l1!·l2!·...·lr! C2p m f<, В частности, если r=2, b1=-1, b2=1, то при подходящем зна4Cp m чении l1 мы возвращаемся к уже исследованной ситуации. В той то найдётся такое i, что |Wi |>2Cp. Но тогда |Wi|>2Cp, коль скоро ситуации для нас <критическим> было нулевое скалярное произm m WiW — это семейство прообразов векторов из Wi. Стало быть, ведение. Теперь же мы и в выборе нового критического произвепо лемме в Wi существуют векторы x, y, скалярное произведение дения, в принципе, вольны. Тут есть огромное количество разных 48 тонкостей, повязанных на неизвестный нам линейно-алгебраиче- 38 (проблема). Пусть m=2k, а ский метод, и мы не станем даже пробовать рассуждать сейчас m {i:

о них. Однако суть задачи ясна, и, кроме того, видно, что деятельV= x=(x1,..., xm): xi{-1, 0, 1} ; xi=±1} =.

ности здесь — непочатый край. В сущности, дай Бог разобраться хотя бы с r=3, b1=-1, b2=0, b3=1, и мы вернёмся к этому Ясно, что |V|=Cm/2·2m/2. А сколь велико может быть подмноm аспекту проблемы в разделе задач.

жество QV, свободное от пар векторов с нулевым скалярным Заметим напоследок, что Г. М. Циглер со своими учениками произведением В частности, если при m=16 окажется, что доказал такой замечательный факт: в пространстве размерности n9 каждое множество, состоящее из (0, 1)-векторов, разбивается C8 ·|Q| на n+1 часть меньшего диаметра. Стало быть, если в малых размерностях контрпримеры и найдутся, то устроены они будут не так, как их многомерные собратья.

(а это весьма правдоподобно), то гипотеза Борсука будет опро33. Докажите, что вергнута при n135.

39 (проблема). Пусть V n таково, что расстояние между n n n n любыми двумя его точками есть либо a, либо b, т. е. V — это n!e.

e так называемое двухдистанционное множество. Верно ли, что f(V)n+1 34 (<точность> оценки в лемме). Пусть m=8q, где q — л ю40. Найдите как можно большую размерность, в которой любое б о е натуральное число. Докажите, что в R={1,..., m} найдётся множество (-1, 0, 1)-векторов разбивается на n+1 часть мень Cq совокупность, состоящая из 2q-сочетаний, никакие два 4q шего диаметра.

из которых не пересекаются по q общим элементам. С помощью 41 (теорема Эрдеша—Ко—Радо). Пусть любые два множества формулы Стирлинга докажите, что в совокупности k-сочетаний из {1,..., m} имеют непустое пересе 2 чение. Какая максимальная мощность может быть у совокупности Cq = 1,754...+o(1) m и C2q= 1,754...+o(1) m.

4q m 42 (теорема Франкла—Уилсона—Алсведе—Хачатряна). Пусть любые два множества в совокупности k-сочетаний из {1,..., m} Это будет означать, что если и можно улучшить лемму, то только пересекаются не менее чем по t общим элементам. Какая максина уровне бесконечно малых.

мальная мощность может быть у совокупности 35. Рассмотрим V= x=(x1,..., xm): xi{0, 1} ; x1+...+xm=3.

15. О СВЯЗИ МЕЖДУ ВЕЛИЧИНОЙ f(n) И ХРОМАТИЧЕСКИМ ЧИСЛОМ ПРОСТРАНСТВА Пусть Q= x1,..., xs V таково, что (xi, xj)=1 для любых i и j.

Докажите как можно лучшую верхнюю оценку на мощность Q.

В этой, заключительной, главе мы поговорим о связи меж36. Рассмотрим ду проблемой Борсука и задачей отыскания хроматического числа пространства. Напомним (см. [1]), что в последнем случае речь V= x=(x1,..., xm): xi{0, 1} ; x1+...+xm=5.

идёт о минимальном числе цветов, в которые можно так раскра сить всё n, чтобы одноцветные точки не могли отстоять друг от Пусть множество Q= x1,..., xs V таково, что (xi, xj)=2 для друга на расстояние 1. Иными словами, определяется величина любых i и j. Докажите, что существует константа c>0, такая, ( n)=min, в которой минимум берётся по всем разбиениям прочто s=|Q|cm2.

странства, имеющим вид 37 (проблема). Пусть m=4q, где q — л ю б о е натуральное число. Рассмотрим n=V1...V, V= x=(x1,..., xm): xi{0, 1} ; x1+...+xm=2q. где для каждого i{1,..., } и для любых двух точек x, yVi выполнено |x-y|=1.

Пусть Q= x1,..., xs V таково, что (xi, xj)=q для любых i и j. Уже из приведённого определения видно, что между величи Какая оценка для s является наилучшей нами f(n) и ( n) должна быть какая-то связь. В самом деле, если 50 в случае хроматического числа мы разбиваем всё пространство ЛИТЕРАТУРА на части, <не содержащие> расстояний 1, то в проблеме Борсука [1] Р а й г о р о д с к и й А. М. Хроматические числа. — М.: МЦНМО, мы аналогичным образом поступаем с каждым множеством диа2003.

метра 1. Естественно, возникает целая серия <промежуточных> задач. Рассмотрим произвольное множество A n, diam A =1, [2] Б о л т я н с к и й В. Г., Г о х б е р г И. Ц. Теоремы и задачи и постараемся как можно экономнее представить его в виде комбинаторной геометрии. — М.: Наука, 1965.

A =A1...A, [3] Д а н ц е р Л., Г р ю н б а у м Б., К л и В. Теорема Хелли. — М.: Мир, 1968.

предполагая, что в каждом Ai нет пар точек, отстоящих друг [4] Я г л о м И. М., Б о л т я н с к и й В. Г. Выпуклые фигуры. — от друга на данное расстояние a(0, 1]. Положим a(A )=min М.: Гостехиздат, 1951.

(в этом-то как раз и <экономия>), далее, положим [5] Х а д в и г е р Г., Д е б р у н н е р Г. Комбинаторная геометрия (n, a)=max a(A ).

A плоскости. — М.: Наука, 1965.

Pages:     | 1 |   ...   | 4 | 5 || 7 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.