commit af0060b2161660e06c4191156e5105649f99b778
parent a645d0286bb11d422cb3a2c098c2a5884263219e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 28 May 2025 11:29:44 +0200
commit with codex
Diffstat:
28 files changed, 146 insertions(+), 9 deletions(-)
diff --git a/2cnf b/2cnf
@@ -0,0 +1,9 @@
+# 2-CNF
+
+A [conjunctive_normal_form] [boolean_formula] where every [clause] contains two [literals]
+
+- [satisfiability_boolean] on such formulas: [2sat]
+- generalization: [kcnf]
+- special case: [monotone2cnf]
+
+Up: [conjunctive_normal_form]
diff --git a/3_colorability b/3_colorability
@@ -0,0 +1,5 @@
+# 3 colorability
+
+The [computational_problem] of deciding, given a [graph], whether it is [3_colorable], i.e., admits a [3_coloring]
+
+Up: [colorability]
diff --git a/3_colorable b/3_colorable
@@ -4,4 +4,6 @@
See also: [3_coloring], [graph_bipartite]
-Up: [graph_family]
+Up: [graph_family], [graph_kpartite]
+
+Aliases: graph 3 colorable, graph tripartite, tripartite graph, 3 colorable graph
diff --git a/3_coloring b/3_coloring
@@ -4,4 +4,4 @@
Up: [graph_coloring]
-See also: [3_colorable]
+See also: [3_colorable], [3_colorability]
diff --git a/bipartiteness_testing b/bipartiteness_testing
@@ -0,0 +1,7 @@
+# Bipartiteness testing
+
+Testing if a [graph] is [bipartite_graph] can be done in [linear_time] with [greedy_algorithm]
+
+Up: [computational_problem], [graph_bipartite], [graph_colorability]
+
+Aliases: 2_colorability
diff --git a/cutwidth_approximation b/cutwidth_approximation
@@ -0,0 +1,5 @@
+# Cutwidth approximation
+
+[bansal2024approximating]
+
+Up: [cutwidth], [width_measure_approximation]
diff --git a/diophantine_equation b/diophantine_equation
@@ -1,6 +1,8 @@
# Diophantine equation
-fun [open_problems]: https://en.m.wikipedia.org/wiki/Euler_brick#Perfect_cuboid
+fun [open_problems]: [perfect_cuboid]
+
+- [linear_diophantine_equation]
See also: [sum_of_powers]
diff --git a/edge_coloring b/edge_coloring
@@ -2,6 +2,7 @@
- [incremental_maintenance_edge_coloring]
- [vizings_theorem]
+- [2_edge_coloring]
Up: [graph_coloring]
diff --git a/existential_second_order_logic b/existential_second_order_logic
@@ -0,0 +1,9 @@
+# Existential second order logic
+
+[FO] extended with higher-arity [existential_quantification]
+
+Corresponds to [NP] by [Fagin's_theorem]
+
+Up: [second_order_logic]
+
+Aliases: existential SO, ESO
diff --git a/fagins_theorem b/fagins_theorem
@@ -2,4 +2,6 @@
https://en.wikipedia.org/wiki/Fagin%27s_theorem
+[Existential_SO] is precisely [NP]
+
Up: [theorem], [descriptive_complexity]
diff --git a/generalized_hypertree_width_approximation b/generalized_hypertree_width_approximation
@@ -0,0 +1,5 @@
+# Generalized hypertree width approximation
+
+[lanzinger2023fpt]: [fixed_parameter_tractable] [approximation] of [generalized_hypertree_width] for [bounded_edge_intersection]
+
+Up: [generalized_hypertree_width_computing], [width_measure_approximation]
diff --git a/graph_bipartite b/graph_bipartite
@@ -1,11 +1,11 @@
# Graph bipartite
-Testing if a [graph] is bipartite can be done in [linear_time] with [greedy_algorithm]
+[computational_problem]: [bipartiteness_testing]
- [deficiency]
- [complete_bipartite_graph]
-Up: [graph_family]
+Up: [graph_family], [graph_kpartite]
See also: [hypergraph_balanced], [incidence_structure], [3_colorable]
diff --git a/graph_colorability b/graph_colorability
@@ -0,0 +1,8 @@
+# Graph colorability
+
+The [computational_problem] of, given a [graph] G and number k, deciding whether G admits a [graph_coloring] with at most k colors
+
+- [bipartiteness_testing]
+- [3_colorability]
+
+Up: [computational_problem], [graph_coloring]
diff --git a/graph_coloring b/graph_coloring
@@ -37,4 +37,6 @@
Up: [graph_problem]
-See also: [chromatic_number]
+See also: [chromatic_number], [graph_colorability]
+
+Aliases: graph colored
diff --git a/graph_kpartite b/graph_kpartite
@@ -0,0 +1,14 @@
+# Graph kpartite
+
+https://en.wikipedia.org/wiki/Multipartite_graph
+
+A [graph] that can be [graph_colored] with k colors (i.e., for every color the set of vertices with that color is an [independent_set])
+
+Specific case:
+
+- k=2: [graph_bipartite]
+- k=3: [graph_3_colorable]
+
+Up: [graph_family]
+
+Aliases: colorable, graph colorable
diff --git a/graph_modification b/graph_modification
@@ -12,3 +12,5 @@ An [update] on [graphs]
Up: [graph]
See also: [graph_removal_lemma], [database_repairs]
+
+Aliases: graph modifications
diff --git a/graph_modification_problem b/graph_modification_problem
@@ -6,3 +6,5 @@
- for [treewidth]: [graph_modification_treewidth]
Up: [graph_modification]
+
+Aliases: graph modification problems
diff --git a/hierarchy b/hierarchy
@@ -0,0 +1,11 @@
+# Hierarchy
+
+- [complexity_hierarchy]
+- [dot_depth]: various hierarchies
+- [alternation_hierarchy]
+- [arithmetical_hierarchy]
+- [time_hierarchy_theorem] / [space_hierarchy_theorem]
+
+Up: [mathematics]
+
+See also: [conjunctive_query_hierarchical]
diff --git a/matrix b/matrix
@@ -11,11 +11,12 @@
- [matrix_triangular]
- [matrix_invertible]
- [matrix_vandermonde]
+- [matrix_positive_semidefinite]
- [matrix_toeplitz]
- [matrix_stochastic]
- [unimodular] matrix: [matrix_square] with [determinant] +1 or -1
- equivalently [matrix_invertible] over the integers
- - [totally_unimodular]: matrix (not necessarily square) where every [matrix_square] [submatrix] (deleting rows and columns) has [determinant] 0 or 1 or -1
+ - [totally_unimodular]: matrix (not necessarily square) where every [matrix_square] [submatrix] has [determinant] 0 or 1 or -1
- [strongly_unimodular] matrix
- [pet_matrix]
diff --git a/monochromatic_triangle_problem b/monochromatic_triangle_problem
@@ -0,0 +1,5 @@
+# Monochromatic triangle problem
+
+https://en.wikipedia.org/wiki/Monochromatic_triangle
+
+Up: [computational_problem], [edge_coloring]
diff --git a/perfect_cuboid b/perfect_cuboid
@@ -0,0 +1,5 @@
+# Perfect cuboid
+
+https://en.m.wikipedia.org/wiki/Euler_brick#Perfect_cuboid
+
+Up: [diophantine_equation], [open_problems]
diff --git a/pops_examples b/pops_examples
@@ -0,0 +1,10 @@
+# POPS examples
+
+- [boolean_semiring]: [semiring], [natural_order]
+- [natural_number]: [semiring], [natural_order]
+- [tropical_semiring]: [semiring], [natural_order]
+- the [reals] with an extra element that means "undefined"
+ - undefined is smaller than everything
+ - not [natural_order]
+
+Up: [partially_ordered_pre_semiring]
diff --git a/second_order_logic b/second_order_logic
@@ -2,7 +2,7 @@
- [monadic_second_order_logic]
- [descriptive_complexity]: correspondence with [polynomial_hierarchy]
- - [existential_second_order_logic] corresponds to [nptime], etc.,
+ - [existential_second_order_logic] corresponds to [NP] by [Fagin's_theorem], etc.,
[quantifier_prefix]
- [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity]
- corresponds to [pspace]
diff --git a/simplicial_vertex b/simplicial_vertex
@@ -0,0 +1,7 @@
+# Simplicial vertex
+
+A [vertex] whose [neighborhood] is a [clique]
+
+See also: [simplicial_tree_decomposition]
+
+Up: [vertex]
diff --git a/submatrix b/submatrix
@@ -0,0 +1,7 @@
+# Submatrix
+
+A [matrix] obtained from another [matrix] by deleting rows and columns
+
+Up: [matrix]
+
+See also: [subsequence]
diff --git a/tdta b/tdta
@@ -18,4 +18,4 @@ Up: [tree_automaton_top_down], [automata_deterministic]
See also: [bDTA], [tNTA], [tUTA]
-Aliases: deterministic top-down tree automaton
+Aliases: deterministic top-down tree automaton, tDTAs
diff --git a/tdta_set_acceptance b/tdta_set_acceptance
@@ -0,0 +1,9 @@
+# TDTA set acceptance
+
+An [acceptance_condition] that generalizes [tDTAs] by specifying not a set of [final_states], but a set of [final_state_sets]
+
+Characterizes [boolean_closure_tdta]
+
+Up: [tdta], [acceptance_condition]
+
+See also: [muller_acceptance]
diff --git a/width_measure_approximation b/width_measure_approximation
@@ -0,0 +1,7 @@
+# Width measure approximation
+
+- [cutwidth_approximation]
+- [pathwidth_approximation]
+- [generalized_hypertree_width_approximation]
+
+Up: [approximation], [width_measure]
