Всего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов




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

Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.

Задачи по раскраске графов часто легко сформулировать, однако невероятно трудно решить. Даже на поиски ответа на вопрос, с которого началась вся эта область исследований – достаточно ли четырёх цветов для раскраски любой карты? – ушло более ста лет (если вам интересно, то ответ – да).

Задача, рассматривавшаяся в новой работе, до сей поры не считалась исключением. Её не могли решить более 50 лет, и она касается тензорных произведений – графов, составленных из особой комбинации двух разных графов (назовём их G и H). Тензорное произведение графов G и H – это новый, более крупный граф, каждая вершина которого обозначает пару вершин оригинальных графов – одну от G и одну от H – при этом две вершины тензорного произведения соединены, если соединены как соответствующие им вершины в G, так и соответствующие им вершины в H.

Предположим, вы – преподаватель музыки, и вам нужно найти хорошие дуэтные пары для концерта пятого курса. Вы можете составить граф, вершинами которого будут студенты, а связи между парами будут обозначать наличие хороших отношений между ними. Затем вы можете составить второй граф, в котором каждый узел будет обозначать различные музыкальные инструменты, а связь между ними – наличие у вас нотных листов для дуэта двух этих инструментов. В тензорном произведении двух этих графов будет по одной вершине для каждого возможного объединения студента и инструмента (допустим, Алиса и тромбон), а две вершины будут связаны, если два студента хорошо работают вместе, и при этом два инструмента совместимы.

В 1966 году Стивен Хедетниеми, сегодня работающий профессором в Университете Клемсона в Южной Каролине, в своей докторской диссертации выдвинул предположение, что минимальное количество цветов, необходимое для раскраски тензорного произведения, равняется наименьшему из двух количеств цветов, необходимых для раскраски любого из двух составляющих его графов. «Это одна из основных гипотез в теории графов, — сказал Гил Калай из Еврейского университета в Иерусалиме. – Её пыталось обдумывать много людей».

За прошедшие десятилетия математики собрали гору свидетельств, некоторые из которых говорили об истинности гипотезы, а некоторые – о её ложности. У разных математиков были разные предположения по поводу того, какой из вариантов в итоге победит. Но все соглашались, что, по крайней мере, это сложная задача.

«Лично я считал, что эта гипотеза верна, поскольку огромное количество умных людей изучали её, и должны были бы придумать контрпример», если бы такой существовал, сказал Энтони Бонато из Университета Райерсона в Торонто.

И вот российский математик Ярослав Николаевич Шитов придумал простой способ создания контрпримеров, тензорных произведений, которым требуется меньше цветов, чем любому из двух составляющих их графов. Доказательство вышло «элементарным, но гениальным», сказал Павол Хелл из университета Саймона Фрейзера в Бёрнаби (Канада).

Тензорные графы тесно связаны с вопросами об отображениях разных графов друг на друга, и в этой области математики гипотеза Хедетниеми была, вероятно, крупнейшей из открытых проблем, сказал Хелл. «Это важнейший прорыв».

Цветастые сборища


Чтобы представить, какую информацию можно извлечь из раскрашивания тензорного графа, представьте, что вы собираетесь каждые выходные приглашать своих друзей в своё загородное поместье. И, как хорошему хозяину, вам хочется собрать людей, которые будут получать удовольствие от компании друг друга.

Вы знаете, что некоторые из ваших друзей смогут быстро подружиться на почве работы, а другие – нет. Также вы знаете, что у ваших друзей есть хобби – ещё один способ, через который гости смогут найти общие интересы. Вы размышляете, что преподаватель танцев, играющий на скрипке, может хорошо провести время, беседуя с инструктором по йоге, играющим в теннис, или обсуждая музыку с фермером, добывающим кленовый сироп, и играющим на пианино, но при этом, вероятно, ему не о чем будет говорить с политологом, коллекционирующим марки. Вы хотите, чтобы на любых выходных каждая пара гостей смогла найти некие общие интересы, будь то работа или хобби, и вам интересно, сколько сборищ нужно устроить, чтобы перебрать всех гостей из списка.


Ярослав Шитов обнаружил контрпример гипотезе Хедетниеми 53-летней давности из теории графов

Взаимоотношения различных видов работы вы могли бы представить в виде графа, узлами которого будут работы, а рёбрами будут соединяться две любых работы, между которыми, скорее всего, нельзя будет найти общих тем для разговора (такой подход может показаться вывернутым наизнанку, однако в контексте раскраски графов такое соединение вершин имеет смысл, поскольку мы будем использовать цвета для разделения этих проблемных пар). Также вы могли бы сделать граф, вершинами которого служат разные хобби, и соединить между собой все несовместимые.

У тензорного произведения двух этих графов будут узлы для каждой пары работа-хобби, а две вершины будут объединяться, если как обе работы, так и оба хобби несовместимы – это как раз та ситуация, которой вы хотите избежать на выходных. Если вы сможете раскрасить вершины тензорного произведения так, чтобы у соединённых рёбрами вершин были разные цвета, это даст вам способ формирования списков гостей на разные выходные: вы можете пригласить людей, соответствующих зелёным вершинам, в «зелёные» выходные, красным вершинам – в «красные», и так далее, и быть уверенным в том, что несовместимые гости окажутся в списках на разных выходных. Количество использованных вами цветов сообщит вам, сколько выходных нужно будет занять в календаре.

Из этого примера следует, что любая допустимая раскраска графа работ переносится и на тензорное произведение – вы можете просто раскрасить каждую комбинацию работа-хобби тем же цветом, что вы использовали и для работы. Такая раскраска приведёт к тому, что на сборищах каждая пара гостей будет совместима исключительно по профессиональным интересам, вне зависимости от их хобби.

И наоборот, любая допустимая раскраска графа хобби переносится и на тензорное произведение. Хедетниеми предположил, что наилучшим способом раскрасить тензорный граф будет минимальная по количеству цветов раскраска одного из изначальных графов.

На первый взгляд, гипотеза Хедетниеми кажется маловероятной. Ведь если вы основываете тензорную раскраску на раскраске рабочего графа, вы игнорируете всё, что вы знаете о совместимых хобби ваших друзей, и потенциально разделяете гостей, которые бы поладили друг с другом. Если же вы скомбинируете всю информацию о работах и хобби, возможно, вам удастся использовать меньше цветов и насладиться заслуженными выходными без гостей.

И всё же в течение более чем 50 лет математики не могли найти ни одного тензорного произведения, для раскраски которого требовалось бы меньше цветов, чем для любого из составляющих его графов. Они смогли доказать, что гипотеза верна, если для раскраски одного из двух графов требовалось не более четырёх цветов. Она также верна в более общем случае «дробных» раскрасок, когда каждой вершине можно назначать комбинацию из цветов – например, 2/3 жёлтого и 1/3 зелёного. (В терминах выходных сборищ это может соответствовать ситуации, когда в вашем списке друзей есть три журналиста, один из которых играет в теннис, и вы пригласили двух из них на «жёлтые» выходные, а третьего – на «зелёные»).

Эти открытия подсказывали, что гипотеза может быть истинной, однако другие говорили о противоположном. К примеру, математики показали, что гипотеза Хедетниеми разваливается для графов, которым требуется бесконечное количество цветов для раскраски, или для направленных графов, у рёбер которых есть предпочтительные направления. Но, несмотря на то, что математики доказали гипотезу Хедетниеми для каких-то случаев, и опровергли для других, они не смогли решить вопрос в той области, которую изначально рассматривал сам Хедетниеми: конечные ненаправленные графы с целочисленной раскраской.

«Все в целом считали её верной, однако доказать или опровергнуть это было сложно», — сказал Нога Элон из Принстонского университета.

Раскрашивая страницы


Шитов разбил все эти неопределённости при помощи чёткой и простой демонстрации ложности гипотезы Хедетниеми. В работе, основное доказательство которой умещается на одной странице, под завязку забитой математикой, он показывает, как создать особый тип тензорного произведения, для раскраски которого требуется меньше цветов, чем для любого из его составляющих.

Шитов начинает работу с наблюдения за тем, что произойдёт, если скомбинировать граф G с одним из его экспоненциальных графов, и получить их тензорное произведение. У экспоненциального графа имеется по одному узлу для каждой из возможных раскрасок G неким фиксированным количеством цветов (разрешаются все возможные раскраски, не только те, у которых соединённые вершины имеют разные цвета). Если у графа G, допустим, 7 вершин, а в нашей палитре 5 цветов, тогда у экспоненциального графа будет 57 вершин – поэтому он и называется экспоненциальным.


Гипотеза Стивена Хедетниеми о минимальном количестве цветов для раскраски тензорного произведения графов оставалась неподтверждённой более 50 лет

Если вернуться к варианту раскраски, в котором связанные вершины должны быть разных цветов, то у нас не будет гарантии, что пяти цветов нашей палитры будет достаточно для раскраски графа G, и точно так же их может не хватить для раскраски экспоненциального графа с 57 вершин. Однако математикам давно известно, что существует один граф, для раскраски которого достаточно пяти цветов: это тензорное произведение, состоящее из G и его экспоненциального графа.

На самом деле, у всех экспоненциальных графов есть это свойство: тензорное произведение, комбинирующее экспоненциальный граф с графом, на основе которого он был создан, можно раскрасить ровно таким же количеством цветов, как и оригинальный граф. Шитов опроверг гипотезу Хедетниеми, показав, как можно создать такой граф G, что для раскраски как его, так и его экспоненциального графа требуется больше цветов.

Хедетниеми заявил, что «совершенно восхищён» разрешением ситуации с его гипотезой после стольких десятилетий. У доказательства Шитова «есть определённая элегантность, простота и явное качество», написал он в емейл.

Новый контрпример оказался хитроумным и изобретательным, говорят математики, и ему не нужны сложные передовые математические инструменты. «Специалисту по теории графов эту конструкцию можно объяснить двумя предложениями», — сказал Калай.

Почему этот аргумент никто не замечал более 50 лет – для математиков загадка. «Иногда маленький драгоценный камень прячется под грудой листвы, — сказал Хелл. – Шитову просто удалось понять этот вопрос глубже, чем всем остальным».

Графы Шитова получаются гигантскими: он не подсчитывал их точный размер, но оценивает, что у графа G, вероятно, будет около 4100 вершин, а у экспоненциального – не менее 410000 вершин, то есть куда как больше, чем примерное количество элементарных частиц в наблюдаемой Вселенной [порядка 1080 / прим. перев.].

Но, конечно, всё зависит от наблюдателя. Шитов считает, что его контрпример «не такой уж и огромный. В математике можно найти контрпримеры, по сравнению с которыми этот будет весьма крохотным».

И хотя вы вряд ли сможете пригласить 410000 в ваш загородный дом, работа Шитова не отвергает существования контрпримеров гораздо меньшего размера. Но теперь, когда математики знают, что гипотеза Хедетниеми ложна, естественным вопросом будет, насколько именно она ложна: насколько меньше цветов может понадобиться для раскраски тензорного произведения по сравнению с составляющими его графами, и какое минимальное количество узлов и рёбер может быть у таких контрпримеров?

Тем временем, Элон сказал, что в новой работе содержится важный урок для всех математиков: «Иногда причина того, что гипотезу так сложно доказать, заключается в том, что она ложна».

Комментарии (66)


  1. tas
    02.08.2019 10:19
    +1

    Пост, поднявший настроение с утра. Рад за Россиянина!


    1. spanasik
      02.08.2019 11:40
      +1

      просто за любого другого умного молодого человека был бы не рад?


      1. Agne
        02.08.2019 12:41
        +23

        Рад за умного молодого человека +1 к радости.
        Рад за соотечественника +2 к радости.
        Рад за русского математика +5 к радости.


      1. maxzhurkin
        02.08.2019 14:55

        Больше рад за Россиянина, чем был бы рад за иностранца, видимо


      1. MaxVetrov
        03.08.2019 00:49

        а просто за любого другого умного старого человека был бы не рад? :)

        Ну эта такая же радость как за однокашника, земляка. Никакой дискриминации.)


    1. Sirion
      02.08.2019 11:50
      +1

      Меня всегда забавляет, когда люди, так радеющие за Россию, не удосужились выучить правила русского языка. По которым, собственно, названия наций пишутся со строчной буквы.


      1. Ergistael
        02.08.2019 14:28
        -5

        В данном случае допустимо. Интонационно это слово тоже выделяется. Мы же пишем Человек, когда хотим сказать о выдающемся, настоящем человеке. Я ни на чьей стороне, просто мимокрокодил.


        1. Sirion
          02.08.2019 14:34
          +14

          Мы же пишем Человек, когда хотим сказать о выдающемся, настоящем человеке.
          А если человек совсем выдающийся, то пишем его ВСЕМИ БОЛЬШИМИ БУКВАМИ. А если не совсем, но просто прикольный, то пишем его ЛеСеНкОй.


          1. Ergistael
            02.08.2019 15:25

            Сударь, вы не правы, если считаете, что нарицательные всегда (кроме как в начале предложений) пишутся со строчной буквы. Прочтите, пожалуйста, известное (даже по школьному курсу) любому образованному человеку стихотворение Редьярда Киплинга «Заповедь» в переводе М. Лозинского (в других переводах встречается иное, но причина написать так у переводчика была). Его завершает четверостишье:

            Наполни смыслом каждое мгновенье,
            Часов и дней неумолимый бег, —
            Тогда весь мир ты примешь во владенье,
            Тогда, мой сын, ты будешь Человек!


            Я не псевдопатриот, я за правду: так написать можно, если хочется и если чувствуешь язык. А то иногда ведь можно имя собственное со строчнОй буквы написать. Ходят всякие петросяны, шутят… У меня всё.


            1. siziyman
              02.08.2019 15:30
              +4

              так написать можно, если хочется
              Ну да, это авторская большая буква, как авторские знаки препинания иногда случаются. Но это не соответствует нормам русского языка.


              1. Ergistael
                02.08.2019 15:35
                -4

                Ну, да, и это же повод в карму сразу насрать (мою). Как бы намекая, что это именно человек плохой, а не только его комментарий.


                1. siziyman
                  02.08.2019 16:15
                  +6

                  У меня нет кармы/рейтинга для того, чтобы ставить кому-либо минусы и/или плюсы. Так что это вы не по адресу возмущаетесь. Это раз.
                  По нормам русского языка нарицательные пишутся и правда всегда со строчной буквы. Это два. Отход от нормы может иметь место, но это отход от нормы.


                  1. geher
                    02.08.2019 22:01
                    +1

                    По нормам русского языка нарицательные пишутся и правда всегда со строчной буквы.

                    Во-первых, это неправда, ибо есть аббревиатуры, многие из которых пишутся только с большой буквы.
                    Во-вторых, вы сами написали, "авторская большая буква". А автор комментария вам уже не автор?


                1. Sirion
                  02.08.2019 16:30
                  +2

                  Между прочим, моя карма в процессе этого обсуждения тоже понизилась) любая точка зрения небезопасна.


                  1. tvr
                    03.08.2019 16:13
                    -2

                    Да, заметно, что в последнее время все стали более нервными, или свежих минусомётчиков завезли — развлекаются. Или и то и другое.


            1. Sirion
              02.08.2019 15:47
              +1

              Что дозволено Киплингу, не дозволено быку. Думаю, вы не хотели бы жить в интернете, где в качестве грамматической нормы взят, скажем, Велемир Хлебников.


              1. Ergistael
                02.08.2019 15:59

                Я уже не хочу «жить в интернете», где технические статьи пишут с дичайшими грамматическими ошибками, а за осознанное отступление от правил в допустимом месте «клеймят по карме». Ладно, ерунда всё это, проехали.


                1. Sirion
                  02.08.2019 16:13
                  +1

                  1. Это была не техническая статья и даже не технический комментарий.
                  2. Нет никаких признаков того, что отступление от правил было осознанным.
                  3. «Допустимость» места вы обосновываете, ссылаясь на авторскую орфографию поэта. Я с тем же успехом могу сослаться, скажем, на Алексея Цветкова (одного из немногих моих любимых поэтов по нашу сторону Стикса). Он сейчас пишет все свои стихотворения строчными буквами и вообще без знаков препинания.
                  4. Художественный эффект, созданный этой авторской орфографией — отвращение.
                  5. Если вы расскажете, как именно подключены к интернету, я посоветую вам, как быстрее всего от него отключиться.


                  1. Sergey_Kovalenko
                    02.08.2019 21:59
                    -1

                    дружище язык придуман для того чтобы люди могли делится своими наблюдения мыслями идеями похоже цель обучения правилам в школе большинстве случаев скорее препятствует коммуникации наверное этому тоже есть свои причины и вы им неосознанно следуете по моему мнению если правила больше усложняют задачу одного собеседника чем облегчают задачу другого то правила не нужны


                    1. Sirion
                      03.08.2019 00:18
                      +1

                      Интересное наблюдение: среди людей, чьи мысли мне действительно интересны, процент тех, у кого были проблемы с выучиванием правил русского языка в школе, чрезвычайно мал (разумеется, я сейчас лишь о русскоговорящих/русскопишуших).

                      Интересное наблюдение номер два: грамотный человек может позволить себе просторечную лексику, сленг, нарочитые грамматические ошибки, упрощения пунктуации, разнообразные орфоарты. При этом по его тексту всё равно будет понятно, что он грамотный человек. В нём будет формально больше ошибок, чем в аналогичном тексте малограмотного человека, но при этом он будет вызывать меньше отвращения. Это как инсталляция из мусора на выставке и просто мусор на тротуаре.

                      Интересное наблюдение номер три: язык — это инструмент. Правила относительны; можно соблюдать их или нарушать, добиваясь при этом того или иного впечатления у читателя. Соблюдение правил — дефолтный выбор. Нарушение — средство выразительности. Что именно будет им выражено и насколько это будет красиво или уродливо — зависит от контекста. В исходном комментарии с этим всё грустно, отчего и стартовала эта ветка.


                      1. 9660
                        05.08.2019 07:36

                        Интересное наблюдение: у меня, русскоговорящего в школе не случалось никаких проблем с выучиванием правил русского языка. Аттестат тому подтверждение.
                        А вот желание заморачиваться данными правилами отсутствует уже лет как 30.
                        Ну и дефолтный выбор это выражение своих мыслей, по возможности понятными собеседнику, а соблюдение придуманных кем-то правил глубоко вторично.


          1. Druu
            03.08.2019 05:02
            +1

            Вы забываете, что комментарии — это не письменная речь, а фиксация разговорной. По-этому, да, можно и лесенкой, можно и курсивом выделять, можно смайлики ставить, можно и как-нибудь вообще вот так: "чЕЛОВЕК", или намеренно коверкая написание.
            Нормы русского языка подобные вещи никак не регламентируют.


            В исходном комментарии с этим всё грустно, отчего и стартовала эта ветка.

            Так это ваше личное мнение. С точки зрения автора комментария — все хорошо, и никакого отвращения использованный им прием не вызывает.


            К слову, тут у комментатора ниже в посте смайлик есть. Еще и с двумя скобками на конце! С точки зрения норм русского языка — это на порядок более существенное нарушение, но вы чего-то к нему не цепляетесь.


            1. Sirion
              03.08.2019 10:41
              +1

              Так это ваше личное мнение.
              Так или иначе, все языковые вопросы сводятся к личным мнениям. Точнее — к совокупностям личных мнений.

              Допустим, моё личное мнение — в «Цветах для Элджернона» орфографические ошибки уместны и хороши, в рассказе какого-нибудь усреднённого начинающего писателя — неуместны и плохи. Это моё личное мнение совпадает с личными мнениями миллионов других людей. Любопытная форма коллективного помешательства.

              Ещё моё личное мнение — комментатору ниже можно простить смайлик (даже будучи пуристом), и даже вам, скрепя сердце, можно простить «по-этому». По причинам сугубо утилитарным: грамматический или пунктуационный разбор вашего комментария уведёт нас в сторону от сути беседы.

              В случае заглавного комментария уходить в сторону было не от чего. У него не было содержания, кроме довольно уродливой (моё личное мнение (с)) формы патриотизма. Мне показалось забавным, что этот патриотизм выражается с помощью коверкания русского языка на английский манер (Glad for Russian!) — и вот мы здесь.


      1. trapwalker
        02.08.2019 14:44
        +4

        Может быть он хотел вообще КАПСОМ написать, но вовремя остановился. Я считаю этого его может и реабилитировать, как разумно умеренного Патриота.


      1. frog6y
        03.08.2019 08:56
        -4

        А вам совсем уже заняться нечем, чем цепляться к человеку из-за написания слов и сливать ему комменты и карму? Скучно живете.


        1. Sirion
          03.08.2019 10:47
          +2

          А вам нечем заняться, кроме как огульно обвинять меня в использовании кармомёта? Вы живёте не только скучно, но ещё и неправедно.


      1. fgengine
        03.08.2019 12:53
        -1

        А вы случаем не слышали выражение «Человек с большой буквы»?


        1. Sirion
          03.08.2019 13:18
          +2

          Я слышал много разных выражений. От тех, которые сочтёт валидными интерпретатор V8, до тех, за которые на Хабре можно схлопотать пермач. И это выражение тоже слышал. Ещё я слышал фразу «в аббревиатуре IoT буква S означает безопасность». Следует ли из этого, что я действительно должен писать эту аббревиатуру с буквой S?


  1. Atterratio
    02.08.2019 10:38
    -4

    вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет.

    с которого началась вся эта область исследований – достаточно ли четырёх цветов для раскраски любой карты? – ушло более ста лет (если вам интересно, то ответ – да).

    Россия признаёт наличие границ с 18 государствами
    (часть конечно морских, но даже сухопутных куда больше 4-х)



    1. ilnoor
      02.08.2019 11:46
      -1

      del


    1. Sirion
      02.08.2019 11:52

      Насколько я помню, государства не обязаны быть связными. Таким образом, раскраска политической карты мира не является частным случаем проблемы четырёх красок.


      1. trapwalker
        02.08.2019 14:48
        +4

        Обожаю такие неожиданные, но после некоторого размышления очевидные повороты! Для полноты картины не хватает ещё одного комментатора, который вспомнит, что бывают ещё и спорные спорные территории, но его люто заминусуют по политическим причинам.


        1. trapwalker
          02.08.2019 14:50

          Черт, похоже я нечаянно породил самоисполняющееся пророчество=(


          1. Sirion
            02.08.2019 14:51
            +1

            Ещё ж не минусовали)


            1. trapwalker
              02.08.2019 16:52

              Я решил за счет чувства противоречия хабравчан попробовать сделать из этого самоисполняющееся пророчества пророчество Шрёдингера.


      1. akhalat
        02.08.2019 14:51

        В википедии во втором предложении подчеркивается, что односвязность не требуется


        1. Sirion
          02.08.2019 14:52
          +2

          Ещё бы википедия подчёркивала разницу между односвязностью и связностью — цены бы ей не было, столько преподавательских нервов сберегла бы.


    1. saboteur_kiev
      02.08.2019 12:45
      +4

      Судя по этому комментарию, этот «соотечественник» даже не понял суть задачи.


    1. mayorovp
      02.08.2019 16:06
      +1

      Под "соседними странами" понимаются не разные соседи одной и той же страны, а соседи друг с другом.


    1. eugenik
      02.08.2019 17:50
      +1

      Уже успели заминусовать человека, но я объясню: здесь налицо неправильное понимание условия задачи — не «ВСЕ соседи России» должны иметь разные цвета, а соседние пары.
      Допустим, Россию покрасили цветом 1, оставшиеся три цвета чередуй покругу, чтобы соседние соседи* были разноцветные. В идеале, для одной страны хватит трех цветов: первый — сама страна, два других — соседи в «шахматной» раскраске
      ________________
      * да, масло масляное: )


      1. CaptainFlint
        02.08.2019 19:02

        В идеале, для одной страны хватит трех цветов: первый — сама страна, два других — соседи в «шахматной» раскраске
        Не хватит, если соседей нечётное количество (и большее единицы :-) ).


  1. arandomic
    02.08.2019 12:25
    +5

    «Специалисту по теории графов эту конструкцию можно объяснить двумя предложениями»

    В статье этих предложений конечно нет? — как генерируется этот граф G с 4^100 вершин так и не понятно.


    1. Sirion
      02.08.2019 12:55
      +8

      Чтобы опровергнуть знаменитую гипотезу, надо просто…


    1. domix32
      02.08.2019 12:56
      +8

      Для SLY_G — это уже естественное явление. Открываешь почитать конкретики, а видишь кучу воды без пояснений: в заголовке "ученый изнасиловал журналиста", а в статье "никогда такого не было и вот опять".


  1. staticlab
    02.08.2019 13:58
    +5

    N+1 опубликовал статью об этом доказательстве ещё в конце мая.


  1. CryptoPirate
    02.08.2019 14:56
    +5

    достаточно ли четырёх цветов для раскраски любой карты? – ушло более ста лет (если вам интересно, то ответ – да).

    Это смотря на какой поверхности. На торе — нет. На торе нужно 7 цветов, 4 не хватит.


    1. NetBUG
      02.08.2019 15:30
      +3

      Изыди, недекартовый!


      1. mayorovp
        02.08.2019 16:11
        +9

        Неевклидовый. Тор — вполне себе "декартова" поверхность (он имеет топологию декартова произведения окружности на себя).


  1. AVI-crak
    02.08.2019 14:59
    -1

    Так, значится можно создать печатную плату всего в четырёх слоях, вне зависимости от её сложности.
    Осталось понять как это делать. Абстрактного обсуждения раскраски галстуков у гостей на свадьбе — явно недостаточно для этой темы.
    И вообще я против излишней абстрактности в подобных делах. Если это математика — то решением должно быть компактное математическое выражение. А всё остальное придумают учителя школ, у них работа такая — полтора землекопа вычислять.


    1. arandomic
      02.08.2019 15:14
      +4

      В статье искаженные странные фразы, вводящие в заблуждение. (факты вроде не искажены, но если бы я их не знал, я бы ничего не понял)
      Задача про 4 краски — безумно стара и доказана в 60х. Она как раз про планарные графы.
      Т.е. если вы смогли развести плату в один слой, то вам хватит четырех красок чтобы раскрасить элементы так, что никакие два, соединенные дорожкой не будут одного цвета.

      Из опровержения гипотезы Хидетниеми вроде ничего полезного для разводки плат не следует…


    1. COKPOWEHEU
      02.08.2019 16:44
      +1

      Печатную плату и на двух можно, вопрос размера.


  1. zenkov
    02.08.2019 18:06

    России надо делать ставку на математиков. В отличии от всех остальных, этим ничего не надо. Время от времени подбрасывать им дохлых мышей чтоб совсем с голоду не умерли, да мел для досок.


    1. Sirion
      02.08.2019 18:08
      +1

      И держать в клетке. Чтобы они не уезжали туда, где мыши сочнее)


    1. grinCo
      02.08.2019 19:57
      +1

      Проблема с математиками, что они когда поголодают — уходят в программирование.


      1. OneType
        03.08.2019 21:59
        -3

        А разве бывают математики не программисты? Им всем нужно моделировать и проверять свои математические знания с помощью программного кода. Те же mathlab и wolfram, как бы специально для математиков.


        1. Sirion
          03.08.2019 22:02
          +1

          Вы чудовищно неправы.


          1. OneType
            04.08.2019 00:31
            -1

            Очень аргументировано, спасибо.


            1. Sirion
              04.08.2019 01:10
              +2

              Ну, у вас просто такое количество неверных пресуппозиций в этом коротком комментарии, что развенчание их займёт больше времени, чем я готов потратить. Если вам действительно интересно, познакомьтесь с настоящим живым математиком и расспросите его за чашечкой пива. До тех пор можете поверить мне на слово как человеку, который с ними знаком и почти стал одним из них.


    1. gnaeus
      02.08.2019 21:20

      Че-то Стивенсона напомнило =)


  1. kluwert
    02.08.2019 18:14

    Тут главный вывод из этой истории очень простой: если добросовестно и глубоко копаешься в какой-то теме и, при этом, имеешь кругозор, то всегда имеешь реальный шанс найти тот самый алмаз под листвой :)


    1. Sirion
      02.08.2019 18:50
      +1

      На эту тему вспоминается не столь давний пост.


  1. erty
    02.08.2019 19:07
    +7

    У меня сложилось впечатление, что я пять или шесть абзацев прочитал с одним и тем же текстом, сказанным немножко по разному. Видимо текст писал американец для американцев, это их любимое развлечение.


  1. TimeCoder
    02.08.2019 19:13
    +1

    Очень не хватает иллюстрации. Пример с гостями, граф профессий, граф хобби — понятно. Но как выглядит тензорный граф из них я так и не понял(((


    1. fingolfin
      05.08.2019 22:12

      В статье же написано:

      У тензорного произведения двух этих графов будут узлы для каждой пары работа-хобби, а две вершины будут объединяться, если как обе работы, так и оба хобби несовместимы – это как раз та ситуация, которой вы хотите избежать на выходных.

      Как я понял, в тензорном произведении будут связны только те вершины, который связаны во всех «графах-множителях»