Here’s the solution for Petersen graph:

Matchings are visualised with dotted edges. Up to isomorphism, there’s only 1 solution for Petersen graph.

There are 2 types of vertices:

• blue (we’ll call them oriented) - each pair of edges, that goes through this vertex in every cycle, is oriented in the same direction
• black (we’ll call them non-oriented) - same pairs are oriented differently in different cycles

TODO

Here’s the solution for one of Blanuša snarks (todo: probably it’s the first Blanuša snark)

Black and violet edges are rich. Every edge is covered 4 times, and now we take a look at the neighboring edges. If we have 4 different possibilities, then the edge is rich. Red and orange edges are poor — there are only 2 possibilities which occur twice in the covering.

Black and red edges constitute 2-factors, violet and orange edges constitute perfect matchings.

Oriented vs non-oriented — the story is about o6c4c (oriented 6-cycle 4-cover). Rich vs poor — the story is about general 6c4c.

This classification of edges is connected to Petersen coloring: if the 6c4c solution comes from Petersen coloring, we’ll get the ordinary definition of rich (all 5 colors in the neighborhood) and poor edges (only 3 colors).

Computational verification shows, that every (cyclically 4-edge connected with girth at least 5) snark with up to (and including) 30 vertices has at least 1 oriented Berge-Fulkerson solution. We’ll state this as a conjecture (oriented Berge-Fulkerson conjecture): every bridgeless cubic graph has an oriented 6-cycle 4-cover (these cycles are called 2-factors, because they are incident to every vertex in the graph) (the complement to these cycles are perfect matchings).

So this construction is also a clarification (and errata) to the 2 pages at Open Problems Garden:

http://www.openproblemgarden.org/op/m_n_cycle_covers (The orientable eight cycle four cover conjecture) http://www.openproblemgarden.org/op/cycle_double_cover_conjecture (The oriented cycle four cover conjecture) Some notation

s0 — number of circuits (circuit is a connected cycle; there are 12 in the solution for Petersen graph) s1 — number of rich edges (15 for Petersen graph) s2 — half of the number of perfect matchings with even number of rich edges (so in general it’s equal to 0, 1, 2 or 3) (0 for Petersen graph) or — number of oriented vertices t1 — number of poor edges which connect oriented with oriented vertex (t2 — number of poor edges which connect oriented with non-oriented vertex) (not used) t3 — number of rich edges which connect oriented with non-oriented vertex t4 — number of rich edges which connect non-oriented with non-oriented vertex total_poor_comps — number of connected components of poor edges odd_poor_comps_2-factors — number of 2-factors with odd number of connected components of poor edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (likewise we can define things as, e. g., odd_rich_comps_2-factors, where we count 2-factors with odd number of connected components of rich edges; or odd_poor_comps_matchings, where we count perfect matchings with odd number of connected components of poor edges) odd_poor_2-factors — number of 2-factors with odd number of poor edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (so we don’t count connected components of edges, just edges themselves) (so, s2 is same as even_rich_matchings / 2) nz-mod-k — nowhere-zero mod-k flow solution (which maybe doesn’t exist), built with 2-factors having weights from 0 to k — 1 and using modular arithmetics (we are interested in k = 5 and k = 6) General case

These statements are easy to prove:

or has same parity as t3 or has same parity in all possible orientations of fixed 6c4c solution Some not yet proven computational observations (checked on snarks with small number of vertices, I will later specify these numbers and decipher every notation):

There’s always at least one dominating circuit which goes through all oriented vertices If or = 0, then s2 = 3 If or = 0, then s0 has same parity as s1 There are no solutions with or = 1 There are no solutions with 16 rich edges There are never less than 15 rich edges for snarks if t1 + t3 < 9, then s0 + s1 + s2 is odd There are no solutions with t1 + t3 = 7 odd_poor_comps_2-factors is even, odd_rich_comps_2-factors is even, odd_poor_comps_matching is even (but odd_rich_comps_matching may have any parity) (if we count not components but just the edges then this becomes obvious) if we have o6c4c, nz-mod5 and don’t have nz-mod6, then or > 2 and s0 is even if total_poor_comps = 1, then s1 + s2 is odd; sometimes patterns start to break only when number of vertices is huge (usually works upto 26 and breaks on 28 vertices):

upto 26: if total_poor_comps = 1, and if the solution is orientable (so we have o6c4c) then s0 is even; breaks on 28.05g611 Case of splitting into 2 separate 6cdcs

If the 6c4c solution comes from Petersen coloring, then its also possible to divide the circuits into 2 separate 6-cycle double covers (we’ll denote this as 2x6cdcs). If we have a general 6c4c solution, then in case we have such decomposition:

it’s easy to show that we can have only 1 such decomposition up to circuit isomorphisms Also we have some unproven statements for this case:

total_poor_comps > 1 odd_poor_2-factors = 0 s2 is either 0 or 3 if the solution is orientable (so we have o6c4c) then s0 is even or + s1 is even (or same as saying that t4 is even) Q&A

Q: Are there any other graphs with 0 poor edges?

A: Yes, later I’ll show here an example

Q: Are there graphs with or = 0 and with splitting into 2x6cdcs?

A: TODO

В этом посте попробую развернуть часть истории про or != 1, кейсы с or = 0, какие вообще бывают конфигурации oriented вершин. Может получится что-то для себя прояснить и доказать. Ну или хотя бы прояснить и всё выписать уже наконец.

В предыдущей заметке есть 3 гипотетических утверждения про oriented вершины:

Если or = 0, то s2 = 3 Если or = 0, то s0 имеет такую же чётность, как и s1 Не существует решений, где or = 1 Вообще я в целом думал и продолжаю воспринимать эту ситуацию по аналогии с теорией Морса и с критическими точками на многообразиях (хоть я их и плохо понимаю). Ну или я вот сходу не знаю как найти подобное в теории критических точек, но вот есть наглядный пример, vortex-antivortex пары, из блога Джона Баеза:

Было 0, стало сразу 2, минуя возможность получить 1 особую точку. Вот, но это всё какие-то аналогии, конечно нужно искать строгое доказательство, пока что не знаю как, но есть всякие наблюдения.

Рассмотрим o6c4c такой, что мы можем собрать из его циклов nz5 поток (nowhere-zero 5-flow). Тогда — у каждой вершины появляется дополнительный тип из nz5 — 112, 123, 134 и 224 (первые 2 цифры — входящие рёбра в вершину, третья — выходящее ребро; или же наоборот). Тип будет со знаком (например, если 112 и ребро 2 выходит, то будет тип +112; если ребро 2 входит в вершину, то тип будет -112).

Подсчитаем, сколько и каких типов вершин у нас есть среди oriented вершин. Зафиксируем o6c4c (todo: или 6c4c?), и будем варьировать nz5. Внезапно, выясняется (пока что недоказано), что по каждому из типов 112, 123, 134 и 224 мы получаем всегда совпадение между числом положительных и отрицательных типов (сюда же попадает граф Петерсена); или же всегда несовпадение.

Ограничимся теперь только теми o6c4c + nz5 решениями, где число положительных типов (среди oriented вершин) хоть где-то несовпадает с числом отрицательных, по любому из 112, 123, 134 и 224 (сюда как раз граф Петерсена не попадает). Тогда! Есть интересные наблюдения, как устроены эти oriented вершины.

Но постойте — в графе Петерсена, например, 3 oriented вершины; явно никакого баланса (совпадения по количеству) быть не может, в чём прикол?

Ага, был не прав. Я действительно, прям буквально имел в виду типы 112, 123, 134, 224, -112, -123, -134, -224 и сумму по типам. Как переинтепретировать тогда совпадение по числу типов? Как сумму по типам. В графе Петерсена: 2 вершины с типом 112, и одна вершина с типом -224.

Например, варианты того, как можно получить nz5 потоки, ограничены. В o6c4c 6 циклов, каждый взят с каким-то весом. Веса можно дополнительно отнормировать (потому что сумма всех 6 циклов даёт нулевой поток по всему графу). Так вот, из всех возможных вариантов тогда останутся только следующие: -4 -3 -2 0 0 0 -4 -2 -1 0 0 0 -3 -2 -1 0 0 0 -3 -1 0 0 0 1 -2 -1 0 0 0 1 -2 -1 0 0 0 2 -2 0 0 0 1 2 -1 0 0 0 1 2 -1 0 0 0 1 3 0 0 0 1 2 3 0 0 0 1 2 4 0 0 0 2 3 4

Во всех кейсах — ровно 3 цикла совпадают по весу, в примерах выше я выбрал для них вес 0.

Зафиксируем 6c4c и любую из вершин. Тогда 6 циклов можно сгруппировать в 3 пары циклов. А именно по совпадению пары рёбер, инцидентных данной вершине.

fixme: тут надо додумать мысль, кажется она сейчас неверна (Тогда, все oriented вершины характеризуются тем, что каждый из циклов с весом 0 попадает в свою отдельную пару.)

В моём файлике есть такие примеры («смотрю кейсы, где есть nz5 и oriented sums ненулевые»):

24.05g15: types: 11:224 12:-112 15:-224 16:-112 22:-112 types: 11:-134 12:-123 15:134 16:-123 22:-123 types: 11:-112 12:-224 15:112 16:-224 22:-224 тут понятно разбиение - (11, 15) и (12, 16, 22)

24.05g25: types: 2:112 4:-112 12:-112 18:-112 19:-112 types: 2:123 4:-123 12:-123 18:-123 19:-123 types: 2:134 4:-134 12:-134 18:-134 19:-134 types: 2:-134 4:134 12:134 18:134 19:134 тут 5 вершин одного типа, с сигнатурой (-, +, +, +, +) во втором o6c4c та же история 24.05g33: types: 5:123 7:123 8:123 15:123 17:-123 types: 0:-123 3:-123 9:-123 15:123 17:-123

types: 3:-123 8:123 14:-123 17:-123 19:-123 types: 3:-123 8:123 13:-123 18:-123 21:-123 types: 3:224 8:-224 15:-224 19:-224 20:-224 types: 3:-123 8:123 12:123 16:123 21:123

может это от графа зависит или какого другого параметра возможно от чётности s0 (-, +, +, +, +) - s0 чётный (+,-), (+, +, +) - s0 нечётный

28.05g89 types: 0:-112 4:112 6:-112 14:-112 18:-112 20:112 24:-112 (- + - - - + -) s0 чётный types: 6:-134 11:-134 14:-134 18:-134 22:-134 23:-134 (- - - - - -) s0 чётный types: 0:224 1:-224 3:112 5:-112 21:224 22:224 24:224 (+ - + + +) (+ -) s0 чётный types: 0:224 1:-224 2:-224 3:112 5:-112 20:-224 25:-224 (+ - - - -) (+ -) s0 чётный 28.05g133 types: 1:224 2:-224 5:-224 10:-224 15:-224 17:-224 21:-224 24:-224 (+, -, -, -, -, -, -, -) s0 чётный

получается это такое усиление гипотезы, что or != 1 они склеены на самом деле хотя это наверно даже понятно как можно понять надо глянуть - как именно циклы друг с другом склеены в этих вершинах и понять - почему они рождаются парами с противоположным знаком, тройками с одним и тем же знаком, или более сложными комбинациями вот этих двух конфигураций хотя это я игнорирую сейчас кейсы, где есть несколько oriented вершин а сумма по ним 0

правда ли, что у всех графов один и тот же список возможных весов? (комбинаторный, их типа 128 или 256) (хотя не всегда, но может там подмножество?) или например зависит только от сигнатуры на oriented вершинах такое ощущение сложилось после истории про сумму потоков на or вершинах да, судя по 28.05, по кейсам, где oriented sums ненулевой всего бывает 7680 вариантов (без отождествления перестановок) 2^935 если отсортировать - будет 64 варианта и что интересно - разница между максимумом и минимумом либо 3, либо 4 а это значит, что минимум можно выставить в 0 получится 12 вариантов 0 0 0 1 2 3 0 1 1 1 2 3 0 1 2 2 2 3 0 1 2 3 3 3 0 0 0 1 2 4 0 0 0 2 3 4 0 1 1 1 2 4 0 1 2 2 2 4 0 1 2 4 4 4 0 2 2 2 3 4 0 2 3 3 3 4 0 2 3 4 4 4 также во всех кейсах веса ровно 3 циклов совпадают если зафиксировать эту тройку на 0, тогда -4 -3 -2 0 0 0 -4 -2 -1 0 0 0 -3 -2 -1 0 0 0 -3 -1 0 0 0 1 -2 -1 0 0 0 1 -2 -1 0 0 0 2 -2 0 0 0 1 2 -1 0 0 0 1 2 -1 0 0 0 1 3 0 0 0 1 2 3 0 0 0 1 2 4 0 0 0 2 3 4 если не учитывать перестановки тогда получится 1440 вариантов (= 12 * 6 * 5 * 4; 12 посорченных вариантов, и нужно выбрать местоположение 3 различных чисел)

По 6c4c решению можно также построить 244-поток (todo: нужно пояснить что это, и вставить референс на статью). Это 3 подграфа, один из них — это цикл. Я называю его 244-циклом.

есть 3 цикла с весом 0 а у остальных не 0 смотрю примеры, где сумма по oriented не 0 дошло тут, что по идее если мы говорим про тройки +++, а не пары +- то все oriented вершины несидят в цикле 244-flows то есть он весь из не-oriented вершин состоит поэтому давайте рассмотрим отдельно non-oriented вершины из 244-flows и отдельно те, что на цикле во, на 32 вершинах (на первых 46 графах из файла cyc5):

рассматриваю только те кейсы, где or_sum по графу ненулевой: nz5 sums = 1 nz5 sums 244 = 1 nz5 sums not244 = 1 or nz5 sums = 8 or nz5 sums 244 = 1 or nz5 sums not244 = 8 un nz5 sums = 8 un nz5 sums 244 = 1 un nz5 sums not244 = 8

nz5 types = 8 10 20 24 48 nz5 types 244 = 8 10 20 16 32 nz5 types not244 = 8 or nz5 types = 8 8 16 8 8 or nz5 types 244 = 8 8 8 1 1 or nz5 types not244 = 8 un nz5 types = 8 10 20 24 48 un nz5 types 244 = 8 8 16 16 32 un nz5 types not244 = 8

todo вот этот кусок выглядит странно un nz5 sums = 8 un nz5 sums 244 = 1 un nz5 sums not244 = 1 надо перепроверить

короче явно видно, что вне цикла из 244 значения потока зафиксированы с точностью до какой-то симметрии (перестановки?) todo: что это за симметрия?

Assertion failed: (triple_or_count == 0), function find_int_nz_from_o6c4c, file experiments/o6c4c.cpp, line 306. так где-то я заблуждаюсь в предположениях ошибаюсь довольно логичным образом ortypes: 3:-112 13:112 17:112 18:-224 20:112 22:224 24:112 тут есть пара вершин 18, 22 которые ломают assertion можно поменять assertion на проверку, что на этих вершинах сумма выдаст 0 заменил, вроде ок

заменил max_fs на types, всё осталось прежним

ага вершины вне цикла более-менее зафиксированы (8 вариантов) а что с циклом происходит?

stats1: 8 8 1 8 16 20 16 8 как-то я пропустил эту строчку внезапно тут 16 вариантов для oriented надо проверить, что для oriented вне цикла - вариантов всё ещё 8 да, всё так

судя по весам: в случаях 8, 10 и 24 - один из циклов выделенный в случае 10 - 3 выделенных цикла в случаях 20 и 48 - получаем 2 непересекающиеся тройки циклов

o6c4c, nz5, or_sum != 0 глянуть вершины вне 244-цикла и есть какая-то интересная зависимость по типам 2:191 - or_not244types: 5:-112 7:112 10:112 12:112 20:112 2:191 - unor_not244types: 2:134 6:-112 8:-112 15:-134 21:-112 ну то есть я бы хотел сказать, что or и unor совпадают по типу с точностью до парных вершин в unor вроде как все парные or вершины сидят в 244-цикле может можно заодно понять - где сидят парные unor вершины? всегда ли это одни и те же вершины? симметрия та же, что и в or? а, ух ты unor могут склеиваться и расклеиваться ещё но вроде бы знаки консистентны (глянул глазами пару примеров) а oriented так не могут or (not244 / 244), 32.05, cyc5: g3: 123/134, 134/123, 112/224, 224/112 g7, g9, g10, g12, g13 - то же ну ок, понял внутри unor not244 встречается также (тройки vs пара): 112/134 других вариантов не встречал а в unor 244 может быть всё что угодно

Вот с этим всем мне предстоит разобраться в ближайшие дни.