commit ac02a1bd80d5d78800b3e91ad7cf5caacd83d3ef
parent 3a4a8e05924485a06921f93b9e1066865a53e6f3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 28 Nov 2025 14:39:21 +0100
commit with codex
Diffstat:
35 files changed, 157 insertions(+), 11 deletions(-)
diff --git a/123_conjecture b/123_conjecture
@@ -0,0 +1,7 @@
+# 123 conjecture
+
+solved by [keusch2024solution]
+
+For every [undirected_graph] without [isolated_edge], we can give weights to the edges in {1, 2, 3} so that no two neighbors receive the same sum of incident edge weights
+
+Up: [graph_theorem]
diff --git a/automata_classes b/automata_classes
@@ -9,6 +9,7 @@
- [automata_acyclic]
- [automata_weakly_acyclic]
- [automata_self_verifying]
+- [xor_automata]
- [automata_one_way]
- [automata_two_way]
diff --git a/automaton_equivalence b/automaton_equivalence
@@ -5,8 +5,10 @@
- [automaton_equivalence_pushdown_automaton]
- [automaton_equivalence_pushdown_automaton_deterministic]
+Special case: [automaton_universality]
+
Up: [automata_problems]
-See also: [language_equivalence], [automaton_inclusion], [query_equivalence_problem]
+See also: [language_equivalence], [automaton_inclusion], [query_equivalence_problem], [regular_language_equivalence]
Aliases: automaton equivalence problem, automata equivalence problem
diff --git a/automaton_inclusion b/automaton_inclusion
@@ -1,8 +1,19 @@
# Automaton inclusion
- [NFA_inclusion]: [PSPACE_complete]
+- [UFA_inclusion]: [PTIME] by reduction to [UFA_universality]
+ - by reduction to [NXA_universality]: https://cstheory.stackexchange.com/a/25478
+- [k_unambiguous_inclusion]: PTIME via [stearns1985equivalence]
- [DFA_inclusion]: [PTIME] via [product_construction]
+[inclusion_DFA_trick]
+
+[regular_language_inclusion_dichotomy]
+
+Special case: [automaton_universality]
+
Up: [automata_problems], [language_inclusion]
See also: [automaton_equivalence]
+
+Aliases: regular language inclusion
diff --git a/edge_coloring b/edge_coloring
@@ -7,3 +7,5 @@
Up: [graph_coloring]
Aliases: edge colored
+
+See also: [graph_edge_colored], [graph_factorization]
diff --git a/eertree b/eertree
@@ -0,0 +1,5 @@
+# Eertree
+
+discussed in [wang2025double] on [dynamic_strings]
+
+Up: [palindrome]
diff --git a/eulerian_path b/eulerian_path
@@ -11,3 +11,5 @@ Variants:
- [chinese_postman_problem]
Up: [path]
+
+See also: [Eulerian_partitioning]
diff --git a/f_factor b/f_factor
@@ -0,0 +1,9 @@
+# F factor
+
+A [subgraph] which is a [regular_graph]
+
+cf https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-16-4.pdf
+
+- a [1_factor] is just a [perfect_matching]
+
+Up: [subgraph]
diff --git a/graph_basic_notions b/graph_basic_notions
@@ -34,4 +34,4 @@
Up: [graph]
-See also: [multigraph]
+See also: [multigraph], [edge_colored_graph], [graph_extensions]
diff --git a/graph_edge_colored b/graph_edge_colored
@@ -0,0 +1,11 @@
+# Edge-colored graph
+
+A [graph] with colors on the [edges]
+
+[yeo's_theorem] [yeo1997note] on edge-colored [undirected_graph] with no alternating [simple_cycle] (i.e., a cycle with no two consecutive edges of the same color)
+
+See also: [edge_coloring]
+
+Aliases: edge colored graph, edge colored graphs
+
+Up: [graph_extensions]
diff --git a/graph_orientation b/graph_orientation
@@ -3,6 +3,8 @@
- [transitive_orientation]
- [balanced_orientation]
- [constraint_graph_satisfiability]
+- [T_odd_orientation]
+- [acyclic_orientation]
Up: [computational_problem] on [graph]
diff --git a/graph_product b/graph_product
@@ -4,5 +4,6 @@
- [chromatic_number] is at most the min of the chromatic number of the arguments and the inequality can be strict [shitov2019counterexamples]
- [graph_cartesian_product]
- [chromatic_number] is the sum of the two chromatic numbers: [Sabidussi's_theorem]
+- [graph_strong_product] in [dujmovic2025grid]
Up: [graph_basic_notions]
diff --git a/graph_theorem b/graph_theorem
@@ -3,6 +3,7 @@
- [graph_structure_theorem]
- [four_color_theorem]
- [strong_perfect_graph_theorem]
+- [123_conjecture]
Up: [graph]
diff --git a/inclusion_dfa_trick b/inclusion_dfa_trick
@@ -0,0 +1,7 @@
+# Inclusion DFA trick
+
+In [automaton_inclusion] problems, the left-hand-side automaton can be transformed into a [DFA] by distinguishing every transition, up to modifying the right-hand-side automaton to create parallel transitions: this does not break [unambiguity] for instance
+
+source: https://cstheory.stackexchange.com/a/34739
+
+Up: [automaton_inclusion]
diff --git a/intersection_nonemptiness b/intersection_nonemptiness
@@ -0,0 +1,5 @@
+# Intersection nonemptiness
+
+- [automaton_intersection_nonemptiness]
+
+Up: [intersection]
diff --git a/k_unambiguous b/k_unambiguous
@@ -6,4 +6,4 @@
Up: [unambiguous]
-See also: [degree_of_ambiguity]
+See also: [degree_of_ambiguity], [K_ambiguous]
diff --git a/kotzigs_theorem b/kotzigs_theorem
@@ -0,0 +1,8 @@
+# Kotzig's theorem
+
+[Theorem] about the [undirected_graphs] with a unique [perfect_matching]
+- they have a [bridge] belonging to the [perfect_matching]
+
+see [szeider2004theorems]
+
+Up: [theorem] about [perfect_matching]
diff --git a/language_equivalence b/language_equivalence
@@ -4,6 +4,7 @@ test if two languages are the same
- on [regular_languages]: [regular_language_equivalence]
- [pspace_complete]
+ - see also [automaton_equivalence]
- on [context_free_languages]:
- [context_free_grammar_equivalence_problem]
- [undecidability]
diff --git a/palindrome b/palindrome
@@ -2,6 +2,8 @@
A [word] which is equal to its [mirror]
+- [eertree]
+
Up: [word]
See also: [manachers_algorithm], [context_free_language], [palindrome_language]
diff --git a/parity b/parity
@@ -6,8 +6,11 @@
- [sat_parity]
- [parity_constraints]
- [parity_function]
+- [xor_automata]
- [even]
- [odd]
Up: [modulo]
+
+See also: [xor]
diff --git a/parity_p b/parity_p
@@ -10,4 +10,4 @@ Generalization to other moduli: [mod_k_p]
Up: [parity], [complexity_class]
-See also: [parity_fine_grained], [Z_2Z], [parity_L], [modular_counting]
+See also: [parity_fine_grained], [Z_2Z], [parity_L], [modular_counting], [xor_automata]
diff --git a/perfect_matching b/perfect_matching
@@ -6,8 +6,10 @@ A [matching] where every vertex is incident to an edge of the matching
- [perfect_matching_counting]
+Graphs with unique [perfect_matching]: [Kotzig's_theorem]
+
Up: [matching]
See also: [matching_counting], [f_factor]
-Aliases: perfect matchings
+Aliases: perfect matchings, 1 factor
diff --git a/regular_expression_squaring b/regular_expression_squaring
@@ -0,0 +1,7 @@
+# Regular expression squaring
+
+[regular_expression] augmented with [squaring] operator
+
+makes [language_inclusion] and [language_universality] [EXPSPACE_complete], cf https://cstheory.stackexchange.com/a/40250
+
+Up: [regular_expression], [squaring]
diff --git a/regular_language_equivalence b/regular_language_equivalence
@@ -0,0 +1,11 @@
+# Regular language equivalence
+
+[language_equivalence] of [regular_languages]
+
+[PSPACE_complete]
+
+[regular_language_equvialence_dichotomy]
+
+Up: [language_equivalence] of [regular_languages]
+
+See also: [automaton_equivalence]
diff --git a/run b/run
@@ -8,4 +8,4 @@ A [sequence] of [states] that starts by an [initial_state] and follows [configur
Up: [automata_concepts]
-Aliases: runs
+Aliases: runs, automaton run, automaton runs, automata run, automata runs
diff --git a/simple_cubic_graph b/simple_cubic_graph
@@ -0,0 +1,7 @@
+# Simple cubic graph
+
+A [simple_graph] which is a [cubic_graph]
+
+Up: [simple_graph], [cubic_graph]
+
+Aliases: simple cubic graphs
diff --git a/simple_graph b/simple_graph
@@ -2,6 +2,8 @@
A [graph] which is not a [multigraph], i.e., there cannot be multiple copies of the same [edge]
+- [simple_cubic_graph]
+
Up: [graph]
See also: [set_semantics]
diff --git a/squaring b/squaring
@@ -4,6 +4,7 @@
- [square_testing]
- [matrix_square]
- [shuffle_square]
+- [regular_expression_squaring]
Up: [exponentiation]
diff --git a/subsequence_closure b/subsequence_closure
@@ -6,4 +6,6 @@ By definition it is a [subsequence_closed_language]
By [Higman's_lemma], the subsequence closure is always regular
-Up: [subword_closure]
+See also: [subword_closure], [automaton_subsequence_closed], [supersequence_closure]
+
+Up: [subsequence]
diff --git a/supersequence b/supersequence
@@ -2,7 +2,7 @@
A [word] u is a *supersequence* of a [word] v if v is a [subsequence] of u
-See also: [subsequence]
+See also: [subsequence], [supersequence_closure], [automaton_supersequence_closed]
Up: [formal_language_theory], [stringology]
diff --git a/t_odd_orientation b/t_odd_orientation
@@ -0,0 +1,7 @@
+# T odd orientation
+
+Given an [undirected_graph] G and subset T of vertices, a *T-odd orientation* is a [graph_orientation] of G where precisely the vertices of T have odd [in_degree]
+
+discussed in [gravier2025note] in connection to [acyclic_orientation]
+
+Up: [graph_orientation]
diff --git a/universality_automata b/universality_automata
@@ -1,4 +1,4 @@
-# Universality automata
+# Automaton universality
The [computational_problem] of testing if an [automaton] accepts every possible [word]
@@ -12,6 +12,8 @@ The [computational_problem] of testing if an [automaton] accepts every possible
Variant: [length_universality_automata]
+Generalization: [automaton_inclusion], [automaton_equivalence]
+
Up: [universality_problem], [automata_problems]
See also: [totality], [validity], [taulology], [automaton_emptiness]
diff --git a/vizings_theorem b/vizings_theorem
@@ -2,8 +2,17 @@
https://en.wikipedia.org/wiki/Vizing%27s_theorem
-If a [graph_undirected] has [maximal_degree] d then it can be [edge_colored] with at most d+1 colors
+If an [undirected_graph] has [maximal_degree] d then it can be [edge_colored] with at most d+1 colors, in time O(mn)
+
+high-level explanation of the algorithm in [polynomial_times], https://simons.berkeley.edu/media/28058/download?attachment p17
+- uses [Eulerian_partitioning]
+ - easier to get a d+3 coloring
+
+A graph is called [class_1] if it can be edge-colored with exactly d colors, and [class_2] otherwise. It is [NP_complete] to decide if a graph is [class_1], cf [holyer1981np], even for [simple_cubic_graphs]
+- and [leven1983np] for other degrees
+
+Such a coloring can be computed in time O(m log d) with high probability, cf [assadi2025vizing]
Up: [theorem] on [edge_coloring]
-See also: [graph_coloring_greedy]
+See also: [graph_coloring_greedy], [1_factorization]
diff --git a/xor_automata b/xor_automata
@@ -0,0 +1,11 @@
+# Xor automata
+
+An [automaton] that accepts if the number of accepting runs is odd
+
+- [nondeterministic_xor_automaton] (NXA)
+
+A specific case of [weighted_automaton]
+
+Tractable [automaton_minimization] and [automaton_inclusion] for them, cf https://cstheory.stackexchange.com/a/24938 [vuillemin2009equivalence]
+
+Up: [automata_classes]
diff --git a/yeos_theorem b/yeos_theorem
@@ -0,0 +1,5 @@
+# Yeo's theorem
+
+Used in [linear_logic], cf [diguardia2025yeos]
+
+Up: [graph_edge_colored]
