У большинства графов сколько-нибудь приличного размера не одно остовное дерево, а много. Физик XIX века Густав Кирхгоф вывел формулу для их количества, однако она не отвечает на все возникающие вопросы, так что даже спустя столетие в этой области ведутся активные исследования. Здесь есть регулярность и структура. Например, сколько тупиков в случайном лабиринте? Конечно, чем больше лабиринт, тем больше в нем тупиков, но что, если мы зададимся вопросом, какую долю от мест в лабиринте занимают тупики? Очень крутая теорема Манны, Дхара и Мажумдара[660] 1992 года показывает, что при увеличении размеров лабиринта эта доля не сходится ни к 1, ни к 0, а по какой-то причине стремится к числу (8 / π2) (1–2 / π), чуть менее 0,3. Вы можете подумать, что число остовных деревьев в случайном графе будет более или менее случайным числом. Нет. Моя коллега Мелани Матчетт Вуд доказала в 2017 году[661], что если ваш граф выбирается случайным образом[662], то количество остовных деревьев будет четным с чуть большей вероятностью, чем нечетным. Точнее говоря, вероятность того, что количество остовных деревьев нечетно, будет бесконечным произведением:
(1 – 1/2) (1 – 1/8) (1 – 1/32) (1 – 1/128)…
где знаменатель каждой дроби вчетверо больше предыдущего. Снова геометрическая прогрессия! Это произведение примерно равно 0,419, то есть довольно далеко от 0,5. Такая асимметрия – признак какой-то более глубокой геометрической структуры на совокупности всех остовных деревьев; оказывается, существует осмысленный способ сказать, когда последовательность остовных деревьев образует арифметическую прогрессию![663]
Но чтобы объяснить это, мне пришлось бы углубиться в захватывающие подробности, а мы еще не спасли демократию. Поэтому вернемся к нашим избирательным округам.
Как только у вас в руках окажется остовное дерево, разделить сеть на части не составит труда: просто сделайте проигрывающий ход, убрав ребро и разъединив граф. Любой ваш выбор разделит граф на две части; если немножко постараться, то можно найти ребро, которое делает их примерно равными по размеру. (Если не выходит, возьмите другое дерево и начните заново.) Получится приблизительно такая картинка: и слева, и справа одну из частей я выделил, а другую – нет.
Теперь вы более или менее знаете, как работает ReCom[664]: берете удвоенный округ, выбираете наугад остовное дерево (например, проведя игру со случайным удалением ребер[665]), выбираете в нем случайное ребро, режете его – и ваш граф распадается ровно на два новых округа.
Я хочу сделать одну оговорку. Существует огромная разница между случайным блужданием посредством метода ReCom на пространстве карт и случайным блужданием с помощью тасований на пространстве способов расположить карты в колоде в каком-то порядке. Во втором случае мы имеем теорему о семи тасованиях, где под теоремой я подразумеваю именно теорему: есть математическое доказательство, что определенного количества тасований (шести!) достаточно, чтобы добраться до любого возможного порядка карт, и, сверх того, с помощью нескольких тасований (семи!) можно обеспечить примерно одинаковую вероятность всех расположений карт в колоде. Когда дело касается округов, никаких теорем нет. О геометрии разбиений на округа мы знаем гораздо меньше, чем о геометрии тасований. Пространство всех разбиений может выглядеть, скажем, так:
В этом случае, начав с одного конца, вы потенциально можете долгое время случайно блуждать по одной части, прежде чем доберетесь до другого конца перешейка. Может даже оказаться, что пространство всех разбиений может быть разделено на две (или даже больше) отдельные части. А вдруг там есть неоткрытая страна возможных карт Северной Каролины, принципиально отличная от всех, когда-либо предлагавшихся математиками, компьютерами или недобросовестными политиками; и вполне может быть, что для этих карт десять республиканских мест из тринадцати – как раз самое обычное дело. Если мы не можем исключить такую вероятность, то имеем ли мы право говорить, что нынешняя карта с мошенническим построением границ – это выброс?
Да, насколько я понимаю. Мы не можем с абсолютной уверенностью знать, существует ли где-нибудь некое секретное хранилище альтернативных карт, но мы знаем, что на практике, если взять карту Северной Каролины, составленную законодательным собранием, и начать ее менять, то она становится менее республиканской, что бы вы с ней ни делали. Такой эксперимент дает четкое подтверждение – в любом значимом статистическом смысле, – что эта карта сфальсифицирована. Это не доказательство мошенничества картографов. Если уж на то пошло, то таким доказательством не являлись бы даже их электронные письма или заявления, прямо утверждающие, что они подтасовывают разбиение; в конце концов, нет никакого доказательства в евклидовом смысле, что они на самом деле не пытались просто набрать: «Давайте приступим к делу и начертим карты, которые беспристрастно отражают волю людей», но их пальцы соскользнули, и вместо этого получилось: «Давайте проведем границы этого штата так, чтобы мы не могли проиграть». Это доказательство в смысле закона, но не в смысле геометрии.
Ансамбль карт, составленных с помощью случайных блужданий, оказался в самом центре судебных дел о джерримендеринге, которые Верховный суд рассматривал весной 2019 года. Суть была не в том, чтобы доказать, что карты составлены в пользу какой-то партии; этот вопрос не оспаривался. Томас Хофеллер, архитектор карты Северной Каролины, уже дал показания, что его целью было «создать как можно больше избирательных округов, в которых кандидаты от Великой старой партии будут успешными»[666] и «минимизировать количество округов, в которых демократы… могли бы избрать своего кандидата». Вопрос стоял так: сработал ли этот план? Вы не можете отбрасывать карту только потому, что ее стремились сделать нечестной. Вы должны доказать, что она такой и получилась.
Метод ансамбля – лучший инструмент, который у нас для этого есть. Более старые идеи, например разрыв эффективности, в запросах истцов в основном отсутствовали. Истцы просили суд признать[667], что карта Северной Каролины – выброс, который выделяется среди нейтральных аналогов, как бородавочник в помете поросят. Они утверждали, что анализ выбросов и есть тот самый «контролируемый стандарт», который разыскивает суд. Джонатан Маттингли, математик из Университета Дьюка и участник группы, создавшей ансамбль карт для выборов в висконсинскую ассамблею, сделал то же самое и для округов Северной Каролины по выборам в конгресс, продемонстрировав, что в его ансамбле из 24 518 карт нашлось всего 162, в которых республиканцы выиграли бы 10 округов. На существующей карте Северной Каролины доля демократов штата была так эффективно распределена по трем округам, что они получили там 74, 76 и 79 %; ни на одной из 24 518 смоделированных карт таких перекошенных округов не нашлось.
В своем консультативном заключении математики излагали аналогичные аргументы, хотя наши графики были красивее.
Затем последовали прения, которые для всех нас, кто рассматривал это судебное дело через призму математики, стали полным разочарованием. Как будто и не было многих лет прогресса в изучении разбиения на округа, словно мы вернулись к избитому вопросу, дают ли 55 % в общем голосовании 55 % мест в законодательном органе. Пол Клемент, защищавший карты Северной Каролины, говорил судье Соне Сотомайор: «Я думаю, что вы уловили то, что мои друзья с той стороны считают проблемой, а именно отсутствие пропорционального представительства». Судья Сотомайор пыталась сообщить Клементу, что дело не в этом, но он продолжал, обращаясь уже к Стивену Брайеру: «Вы не можете говорить даже в целом о выбросах или крайностях, если не знаете, от чего они отклоняются. И я так понимаю, по вашему вопросу и по вопросу судьи Сотомайор, что людей беспокоит отклонение от принципа пропорционального распределения». «На самом деле…» – вмешалась Соня Сотомайор. «Вы все время так говорите, но я не думаю, что это правильно», – возразила Елена Каган. Это не остановило Клемента, который высказался насчет положения в Массачусетсе. Он заметил, что республиканцы никогда не имели в конгрессе представителя от Массачусетса, хотя треть населения штата принадлежит к республиканской партии: «Никто не думает, что это нечестно, поскольку вы реально не можете начертить такие районы, потому что они распределены равномерно. Для них это, возможно, и печально, но я не думаю, что это нечестно».
Бедственное положение республиканцев Массачусетса также обсуждалось в заключении математиков. Наше мнение в основном совпадало с мнением Клемента, за исключением одной важной детали: то, что, по его словам, истцы просят обеспечить, на самом деле то, что истцы просят запретить. Нет ничего нечестного в том, что республиканцы в Массачусетсе не обладают пропорциональным представительством. Вы можете создать ансамбль карт, целые тысячи карт, нарисованных безо всяких гнусных партийных целей, и любая из них отправит в конгресс девять демократов и ноль республиканцев[668]. Вот почему наблюдательная группа Common House не просила Верховный суд гарантировать пропорциональное представительство. Пропорциональное представительство – плохой критерий справедливости. Карта для Массачусетса, составленная с прицелом на пропорциональное представительство, не была бы защищена от обвинений в джерримендеринге и на самом деле была бы такой же жульнической, как и карта «Агрессивный Джо».