Многочлены – это не просто упражнения в абстрактных материях. Они прекрасно подходят для выявления структур в неожиданных местах.
В 2015 году бывший поэт, ставший математиком, Джун Хо помог решить задачу, сформулированную около 50 лет назад. Она была связана со сложными математическими объектами, «матроидами«, и графами (комбинациями точек и отрезков). А ещё она была связана с многочленами – знакомыми нам с уроков математики выражениями, состоящими из суммы переменных, возведённых в различные степени.
В какой-то момент в школе вы, наверное, проходили раскрытие скобок у многочленов. К примеру, вы можете помнить, что x2 + 2xy + y2 = (x + y)2. Удобный алгебраический трюк, но где он может пригодиться? Оказывается, что многочлены отлично помогают выявлять скрытые структуры – и в своём доказательстве Хо активно использовал этот факт. Вот простая загадка, иллюстрирующая это.
Допустим, нам нужно рассадить за квадратным столом две команды игроков. Чтобы предотвратить мошенничество, нужно сделать так, чтобы игроки не сидели рядом с другими игроками своей команды. Сколько способов рассадки существует?
Начнём с рассадки красной и синей команды. Допустим, красный игрок сидит наверху диаграммы:
Рядом с верхним местом есть два места – справа и слева – и чтобы удовлетворить правилу, эти места должны занять синие игроки.
Оставшееся внизу место соседствует с двумя синими, поэтому там должен сидеть красный игрок.
Никто из игроков не сидит рядом с членом своей команды, и наше условие выполнено.
Мы также могли начать с синего игрока наверху. Похожие рассуждения приводят к следующей рассадке:
И снова ни один игрок не сидит рядом с другими членами своей команды. Наше условие выполнено, и такая рассадка допустима. На самом деле, таких рассадок существует ровно две. Как только мы выберем цвет верхнего места, все остальные полностью определяются.
Есть способ узнать, что существует всего две возможные рассадки, не рисуя всех этих диаграмм. Начнём сверху: у нас есть два варианта, красный и синий. После этого выбора остаётся один вариант (другой цвет) для левого и правого сидений. А для нижнего сиденья остаётся один вариант – тот цвет, с которого мы начали. Используя «фундаментальный принцип подсчёта», мы знаем, что общее количество возможностей является результатом перемножения количества возможностей для каждого из вариантов. Это даёт нам 2 × 1 × 1 × 1 = 2 рассадок, как мы и определили из наших диаграмм.
Добавим теперь третью команду с третьим цветом. Представим, что у нас существуют красные, синие и жёлтые игроки. Сколько рассадок можно сделать при условии, что соседние места должны быть разного цвета? Для изображения всех возможностей придётся нарисовать целый вагон диаграмм, поэтому давайте вместо этого попробуем провести расчёты.
Для верхнего места теперь у нас есть выбор из трёх цветов. После этого выбора мы можем выбирать любой из двух оставшихся цветов для левого и правого мест.
Что будет внизу квадрата? Есть искушение заявить, что для последнего места останется лишь один вариант, поскольку оно находится рядом и с левым, и с правым сиденьем. Но чувствуете ли вы изъян в этой логике?
Действительно, если у левого и правого мест будут разные цвета, то для нижнего места останется только один вариант. Если слева, допустим, будет синий, а справа – красный, то нижний обязан быть жёлтым. Но что, если левый и правый цвета будут одинаковые? В таком случае для нижнего места останется выбор из двух вариантов. Этот последний выбор зависит от предыдущих, что усложняет наши подсчёты.
Придётся рассмотреть два разных случая: когда цвета слева и справа совпадают, и когда они отличаются.
Если цвета слева и справа совпадают, количество возможностей для каждого из мест выглядит так:
Для верхнего сиденья у нас есть три варианта. Для правого остаётся два. Поскольку мы предполагаем, что у левого и правого мест один цвет, у нас остаётся только один вариант для левого места: такой же цвет, как у правого. Наконец, поскольку слева и справа цвет один и тот же, для нижнего сиденья мы можем выбирать любой из двух оставшихся цветов. В итоге мы получаем 3 × 2 × 1 × 2 = 12 возможных рассадок.
Теперь посмотрим на те возможности, когда справа и слева цвета разные:
У нас снова есть три варианта для верхнего и два – для правого места. У левого места вариант снова один, но по другой причине: он не может быть таким же, как верхний, соседний, и не может быть таким же, как правый, по нашему условию. И, поскольку справа и слева цвета разные, для нижнего места остаётся только один вариант (такой же, как сверху). Этот случай даёт 3 × 2 × 1 × 1 = 6 возможных рассадок.
Поскольку два этих варианта покрывают все возможности, мы складываем их, и получаем 12 + 6 = 18 возможных рассадок.
Добавление третьего цвета усложнило нашу задачу, но наш тяжёлый труд будет вознаграждён. Теперь мы можем использовать эту стратегию для 4, 5 или любого количества q разных цветов.
Вне зависимости от количества цветов, у нас всегда будет два случая: слева и права будут либо одинаковые, либо разные цвета. Допустим, у нас есть выбор из q цветов. Вот диаграмма, показывающая количество вариантов для каждой стороны, в случае, когда справа и слева цвет один:
Сначала у нас есть q цветов для верхнего сиденья, и q-1 для правого. Поскольку мы предположили, что цвета слева и справа совпадают, у нас есть только один вариант для левого цвета. Это оставляет q-1 вариантов для нижнего места, ведь оно может быть любого цвета, кроме того, который мы выбрали для левого и правого мест. Фундаментальный принцип подсчёта даёт нам q × (q – 1) × 1 × (q – 1) = q(q – 1)2 возможных рассадок.
Если левое и правое места раскрашены по-разному, то мы можем подсчитать возможности так:
Вновь у нас есть q вариантов для верхнего и q-1 для правого мест. Слева не может быть тот же цвет, который выбран для верхнего и правого мест, поэтому там остаётся q-2 вариантов. Снизу может быть любой цвет, кроме тех двух, что мы использовали слева и справа, что опять даёт q-2 вариантов. Получаем в сумме q × (q – 1) × (q – 2) × (q – 2) = q(q – 1)(q – 2)2 возможных рассадок. Поскольку две эти ситуации покрывают все варианты, мы, как и ранее, складываем их и получаем общее количество возможных рассадок: q(q – 1)2 + q(q – 1)(q – 2)2.
Такое выражение может показаться странным ответом на вопрос «Сколько существует различных рассадок разных команд за квадратным столом, таких, что два члена одной команды не будут сидеть рядом?» Однако в этом многочлене заключено много информации о нашей задаче. Он не только даёт нам количественный ответ, но и раскрывает структуру нашей задачи.
Такой многочлен называется «хроматический многочлен«, поскольку отвечает на вопрос: сколько существует способов раскраски вершин сети (или графа) таких, что любая пара соседних вершин имеет разные цвета?
Изначально наша проблема была связана с рассадкой вокруг стола, но мы легко можем превратить её в вопрос о раскраске вершин графа. Вместо людей за столом:
мы представим себе их в виде вершин, соединяемых рёбрами в том случае, когда они сидят рядом:
Теперь любую раскраску вершин графа можно представить в виде рассадки людей вокруг квадратного стала, где «сидеть рядом» за столом означает «иметь общее ребро» на графе.
Теперь, переформулировав нашу задачу в виде графа, вернёмся к хроматическому многочлену. Назовём его P(q).
P(q) = q(q – 1)2 + q(q – 1)(q – 2)2
Замечательное свойство этого многочлена в том, что он отвечает на вопрос раскраски для любого возможного количества цветов. К примеру, чтобы ответить на вопрос с тремя цветами, полагаем q = 3, и получаем:
P(3) = 3(3 – 1)2 + 3(3 – 1)(3 – 2)2 = 3 × 22 + 3 × 2 × 12 = 12 + 6 = 18
Именно этот ответ мы и получили в случае с тремя командами. А если положить q = 2:
P(2) = 2(2 – 1)2 + 2(2 – 1)(2 – 2)2 = 2 × 12 + 2 × 1 × 02 = 2 + 0 = 2
Звучит знакомо? Это ответ на нашу первую загадку, с двумя командами. Мы можем найти ответы для четырёх, пяти или даже 10 разных команд, просто подставляя нужное значение для q: P(4) = 84, P(5) = 260 и P(10) = 6 570. Хроматический многочлен уловил некую фундаментальную структуру задачи, обобщив нашу стратегию подсчёта.
Мы можем раскрыть больше деталей структуры, проведя алгебраические действия над нашим многочленом P(q) = q(q – 1)2 + q(q – 1)(q – 2)2:
= q(q−1)(q−1)+q(q−1)(q−2)2
= q(q−1)((q−1)+(q−2)2)
= q(q−1)(q−1+q2−4q+4)
= q(q−1)(q2−3q+3)
Мы вынесли множитель q(q – 1) из каждой части суммы и скомбинировали похожие члены, приведя многочлен к разложенному на множители виду. И в этом виде многочлен может рассказать нам о структуре при помощи своих «корней».
Корни многочлена – это входные значения, при которых он становится равным нулю на выходе. В разложенном на множители виде находить корни легче: поскольку многочлен выражен в виде перемноженных частей, любое значение, при котором один из множителей равен нулю, обнуляет всё произведение.
К примеру, у нашего многочлена P(q) = q(q – 1)(q2 – 3q + 3) есть множитель (q – 1). Если принять q = 1, этот множитель становится равным нулю, как и весь результат перемножения. То есть, P(1) = 1(1 – 1)(12 – 3 × 1 + 3) = 1 × 0 × 1 = 0. Сходным образом P(0) = 0 × (–1) × 3 = 0. Поэтому q = 1 и q = 0 – это корни нашего многочлена. (Вас может заинтересовать множитель (q2 – 3q + 3). Поскольку он не равен нулю ни при каком вещественном q, он не даёт новых корней нашему хроматическому многочлену).
У этих корней есть смысл в рамках нашего графа. Если у нас есть выбор из одного цвета, каждая вершина должна быть одного и того же цвета. Невозможно раскрасить граф так, чтобы у всех соседних вершин были разные цвета. Именно это и означает, что q = 1 является корнем нашего хроматического многочлена. Если P(1) = 0, тогда способов раскрасить граф так, чтобы соседние вершины не были одинаковых цветов, существует ровно ноль. То же верно для варианта с нулевым количеством цветов, P(0) = 0. Корни нашего хроматического многочлена рассказывают нам о структуре нашего графа.
Возможность видеть структуру через алгебру становится ещё более очевидной, если мы будем рассматривать другие графы. Давайте посмотрим на треугольный граф:
Сколько существует способов раскрасить этот граф q цветами так, чтобы соседние вершины не были одинаковых цветов?
Как обычно, для первых двух соседних вершин есть q и q-1 вариантов. И поскольку последняя вершина соседствует с двумя первыми, он должен отличаться по цвету от их обоих, что оставляет нам q-2 вариантов. Это даёт нам хроматический многочлен для этого треугольного графа: P(q) = q(q – 1)(q – 2).
В такой форме разложения на множители этот хроматический многочлен сообщает нам кое-что интересное: у него есть корень q=2. И если P(2) = 0, должно быть невозможно раскрасить этот граф двумя цветами так, чтобы в нём не было двух соседних вершин одного цвета. Так ли это?
Представьте, что мы идём по кругу в этом треугольнике, раскрашивая вершины по пути. Если у нас есть всего два цвета, нам нужно чередовать их после каждой вершины: если первая красная, то вторая будет синяя, что означает, что третья опять должна быть красной. Но первая и третья вершины соседние, и они не могут быть красными обе. Двух цветов недостаточно, как и предсказывал многочлен.
Используя подобный аргумент с чередованием можно прийти к значительному обобщению: хроматический многочлен любой замкнутой петли с нечётным количеством вершин должен иметь корень, равный 2. Поскольку, если вы чередуете два цвета, и движетесь по петле нечётной длины, первая и последняя раскрашенные вершины окажутся одного цвета. Но так, как это петля, они будут соседними. Раскраска невозможна.
К примеру, мы можем использовать различные техники для определения того, что у петли с пятью вершинами хроматический многочлен выглядит так: P(q) = q5 – 5q4 + 10q3 – 10q2 + 4q. Разложив это на множители, получим P(q) = q(q – 1)(q – 2)(q2 – 2q + 2). Как и ожидалось, оказывается, что q = 2 является корнем, и P(2) = 0. Что интересно, как только мы нашли эту связь между графами и их многочленами, идеи начинают работать в обе стороны. Многочлены могут сообщать нам сведения о структуре графов, а графы – о структуре многочленов.
Именно поиски структуры привели Джуна Хо к доказательству 40-летней гипотезы Рида касающейся хроматических многочленов. Гипотеза утверждает, что если перечислить коэффициенты хроматического многочлена по порядку, игнорируя их знаки, то будет выполняться следующее условие: квадрат любого коэффициента должен быть не меньше произведения двух соседних с ним. К примеру, в хроматическом многочлене для нашей петли из пяти вершин, P(q) = q5 – 5q4 + 10q3 – 10q2 + 4q, мы видим, что 52 ≥ 1 × 10, 102 ≥ 5 × 10 and 102 ≥ 10 × 4. Из этого, например, следует, что не каждый многочлен может быть хроматическим: у хроматических многочленов, связанных с графами, есть более глубокая структура. Более того, связь между этими многочленами и другими областями позволила Хо и его соавторам ответить на гораздо более широкий вопрос, связанный с гипотезой Рота, через несколько лет после доказательства гипотезы Рида.
Возможно, многочлены более всего известны в своём наихудшем виде – в качестве абстрактных упражнений формальной манипуляции алгебраическими выражениями. Но многочлены и их свойства – корни, коэффициенты, различные формы – помогают раскрывать структуры в неожиданных местах, создавая во всём, что нас окружает, связи с алгеброй.
Упражнения
1. Полный граф – это граф, каждая пара вершин которого соединена ребром. Найдите хроматический многочлен полного графа из пяти вершин.
2. Найдите хроматический многочлен для следующего графа (используйте информацию о хроматических многочленах более простых графов).
3. Граф называется двусторонним, если его вершины можно разделить на две группы, A и B, так, что вершины из A являются соседними только вершинам В, а вершины В соседние только для вершин из А. Допустим, у графа G есть хроматический многочлен P(q). Какое свойство P(q) позволит вам заключить, что граф G – двусторонний?
Источник
