commit 0c698c6501ae26ffc3148c69e8e601d3d71c0d6c
parent fbc26a76061326dbd50de3c40c52c6b7e87aad26
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 6 Sep 2025 23:01:47 +0200
commit with codex
Diffstat:
27 files changed, 112 insertions(+), 54 deletions(-)
diff --git a/1_critical b/1_critical
@@ -1,7 +1,9 @@
-# 1 critical
+# 1 critical structure
The *1 critical* [structure] is the [structure] with a single [domain_element] and every [relation] contains only the [tuple] mentioning only that element
Called the "well of positivity" in [gogacz2014all]
Up: [structure]
+
+Aliases: 1 critical structure
diff --git a/bidirectional_edges b/bidirectional_edges
@@ -0,0 +1,7 @@
+# Bidirectional edges
+
+*Bidirectional edges* in a [directed_graph] G are [directed_edges] that exist in both directions, i.e., (x, y) and (y, x). It may or may not include [self_loops]
+
+Up: [graph_directed]
+
+Aliases: bidirectional edge
diff --git a/boolean b/boolean
@@ -1,10 +1,12 @@
# Boolean
+- [Boolean_query]
+- [Boolean_formula]
+- [Boolean_satisfiability]
+- [Boolean_semiring]
+
- [decision_problem]
-- [query_boolean]
-- [formula_boolean]
-- [satisfiability_boolean]
-- [boolean_semiring]
+
- [true]
- [false]
diff --git a/decision_problem b/decision_problem
@@ -1,6 +1,8 @@
-# Decision_problem
+# Decision problem
-A [boolean] [computational_problem], i.e., one with a yes/no answer
+https://en.wikipedia.org/wiki/Decision_problem
+
+A *decision problem* is a [boolean] [computational_problem], i.e., one with a yes/no answer
Up: [computational_problem], [boolean]
diff --git a/goedels_incompleteness_theorem b/goedels_incompleteness_theorem
@@ -7,3 +7,5 @@ http://www.yann-ollivier.org/goedel/goedel.php
Up: [theorem], [logic]
See also: [undecidability]
+
+Aliases: Gödel's incompleteness theorem
diff --git a/graph b/graph
@@ -1,6 +1,6 @@
# Graph
-[graph_definition]
+See [graph_definition]
## Basic notions
@@ -24,26 +24,26 @@ See [graph_basic_notions]
- [width_measure]
- [graph_decomposition]
-## [theorems]
+## [Theorems]
-- [graph_theorem]
+- [graph_theorems]
## Results
- [handshaking_lemma], consequence of [degree_sum_formula]
- [graph_removal_lemma]
-## [graph_algorithm]
+## [Graph_algorithms]
- [floyd_warshall]
- [bellman_ford]
- [dijkstras_algorithm]
-## [graph_family]
+## [Graph_families]
See [graph_family]
-## [graph_problem]
+## [Graph_problems]
See [graph_problem]
@@ -62,22 +62,16 @@ See [graph_problem]
- [incidence_graph]
- [graph_complementation]
-## [graph_operations]
+## [Graph_operations]
- [graph_union]
- [graph_product]
- [edge_contraction]
-## Software
+## [Software]
[graph_software]
-## Problems
-
-- [minimum_linear_arrangement]
-- [graph_sandwich_problem]
-- [planarity_testing]
-
## Graph representations
- [adjacency_list]
diff --git a/graph_definition b/graph_definition
@@ -0,0 +1,5 @@
+# Graph definition
+
+A *graph* consists of a set of [vertices] V and a set of [edges] E. The [edges] can be [undirected_edges] for an [undirected_graph], or [directed_edges] for a [directed_graph]
+
+Up: [graph]
diff --git a/graph_directed b/graph_directed
@@ -1,6 +1,6 @@
# Graph directed
-A [graph] where [edges] are [directed_edges]
+A [graph] where [edges] are [directed_edges] (but it may contain [bidirectional_edges])
- [directed_acyclic_graph]
- [graph_period]
diff --git a/graph_family b/graph_family
@@ -42,6 +42,6 @@ May have the property of being [graph_class_hereditary]
Up: [graph]
-Aliases: graph class, graph classes
+Aliases: graph class, graph classes, graph families
See also: [halls_theorem], [network_reliability], [robertson_seymour], [graph_radius_diameter], [turan_theorem], [graph_substructure], [graph_labeling], [erdos_posa], [graph_traversal]
diff --git a/graph_homomorphism b/graph_homomorphism
@@ -1,6 +1,6 @@
# Graph homomorphism
-A [homomorphism] from a [graph] to an [other]
+A [homomorphism] from a [graph] to another
[Computational_problem]: [graph_homomorphism_problem]
diff --git a/graph_homomorphism_problem b/graph_homomorphism_problem
@@ -0,0 +1,9 @@
+# Graph homomorphism problem
+
+The *graph homomorphism problem* is the [decision_problem] that asks, given two [graphs] G and H, whether there exists a [homomorphism] from G to H
+
+The problem is [NP_complete] even if the right-hand-side [graph] H is fixed, e.g., to a [triangle] (because it amounts to [deciding] [3_colorability] of G
+
+Up: [decision_problem], [graph_homomorphism]
+
+See also: [CSP], [graph_isomorphism_problem]
diff --git a/graph_problem b/graph_problem
@@ -22,7 +22,12 @@
- [graph_reconstruction]
- [clique_problem]
- [cycle_problem]
+- [minimum_linear_arrangement]
+- [graph_sandwich_problem]
+- [planarity_testing]
Up: [computational_problem] on [graph]
See also: [constraint_satisfaction_problem]
+
+Aliases: graph problems
diff --git a/graph_theorem b/graph_theorem
@@ -5,3 +5,5 @@
- [strong_perfect_graph_theorem]
Up: [graph]
+
+Aliases: graph theorems
diff --git a/homomorphism b/homomorphism
@@ -1,10 +1,18 @@
# Homomorphism
+A [function] from a [structure] A to a [structure] B on the same [relational_signature] is a [homomorphism] if, for every [tuple] t in A for some [relation] R, the image of t by the function is also a [tuple] in B for R
+
+On specific structures:
+
+- [graph_homomorphism]
+
+Notions:
+
- [homomorphism_closed]
- [homomorphism_equivalence]
-- [graph_homomorphism]
- [homomorphism_count]
-- [homomorphism_problem]
+
+[Computational_problem]: [homomorphism_problem]
Variants: [homomorphism_variants]
diff --git a/homomorphism_closed b/homomorphism_closed
@@ -1,8 +1,10 @@
# Homomorphism closed
-[query] Q closed under [homomorphism]:
- - if A satisfies Q and A has [homomorphism] to B then B also satisfies Q
+A [query] Q is *closed under [homomorphism]* if the following holds:
+ - if A satisfies Q and A has a [homomorphism] to B then B also satisfies Q
[cate2023when]: characterization of which classes are closed under [homomorphism_count]
Up: [closure] under [homomorphism]
+
+Aliases: closed under homomomorphism
diff --git a/homomorphism_equivalence b/homomorphism_equivalence
@@ -1,8 +1,9 @@
# Homomorphism equivalence
-A and B are homomorphically equivalent if there is a [homomorphism] from A to B and a [homomorphism] from B to A
+A and B are *homomorphically equivalent* if there is a [homomorphism] from A to B and a [homomorphism] from B to A
-It is an [equivalence_relation]: [transitivity] is because the [composition] of two [homomorphisms] is a [homomorphism]
+It is an [equivalence_relation]:
+- [transitivity] is because the [composition] of two [homomorphisms] is a [homomorphism]
Up: [homomorphism], [equivalence]
diff --git a/logic b/logic
@@ -39,9 +39,9 @@
## Results
-- [goedels_incompleteness_theorem]
+- [Gödel's_incompleteness_theorem]
- [zero_one_law]
-- [feferman_vaught_theorem] about [product]
+- [feferman_vaught_theorem] about [product_(structures)]
## Concepts
diff --git a/mathematics_basic_concepts b/mathematics_basic_concepts
@@ -37,5 +37,9 @@
- [relation_mathematics]
- [integer]
- [fraction]
+- [pair]
+ - [ordered_pair]
+ - [unordered_pair]
+- [tuple]
Up: [mathematics]
diff --git a/minimum_violation_problem b/minimum_violation_problem
@@ -0,0 +1,10 @@
+# Minimum violation problem
+
+Having fixed a template graph H, given a [weighted_graph] G, the *minimum violation problem* asks us to find a vertex map from G to H which is [surjective] and minimizes the weight of edges whose image is not an edge of H (i.e., which witness that the map is not a homomorphism)
+- can be studied with fixed edges, i.e., which cannot be removed
+
+Studied in [kawarabayashi2020minimum]
+
+Connections to [max_csp]
+
+Up: [computational_problem], [graph_homomorphism]
diff --git a/query b/query
@@ -2,9 +2,9 @@
- [query_language]
- [conjunctive_query]
-- [query_full]
-- [query_boolean]
- - [query_non_boolean]
+- [full_query]
+- [Boolean_query]
+ - [non_Boolean_query]
- [query_with_negation]
## Problems
diff --git a/query_equivalence b/query_equivalence
@@ -11,4 +11,4 @@ For non-Boolean [queries], on every [database] the [set] of returned [answers] s
Up: [equivalence], [query]
-Aliases: query_equivalent
+Aliases: query_equivalent, equivalent (query)
diff --git a/query_minimization b/query_minimization
@@ -1,10 +1,10 @@
# Query minimization
-The [function_problem], given a [query] Q in a [query_language], of computing a [query] Q' (usually in the same language) which is [query_equivalent] to Q but is "smaller"
+*Query minimization* is the [function_problem], given a [query] Q in a [query_language], of computing a [query] Q' (usually in the same language) which is [query_equivalent] to Q but is "smaller"
- usually smaller number of [atoms]
- but can be another measure, e.g., the [treewidth]
-This problem can be turned into a [decision_problem] by asking, given a [query] Q and integer k, whether there exists a query which is [query_equivalent] to Q but has at most k atoms
+This problem can be turned into a [decision_problem] by asking, given a [query] Q and integer k, whether there exists a [query] which is [equivalent_(query)] to Q but has at most k [atoms]
For various [query_languages]:
- [CQ_minimization]
@@ -12,6 +12,6 @@ For various [query_languages]:
- [CRPQ_minimization]
- [UCRPQ_minimization]
-Up: [query_problems]
+Up: [query_problems], [minimization]
See also: [core]
diff --git a/self_loop b/self_loop
@@ -11,3 +11,5 @@ In [multigraph_directed], you may have multiple self-loops
Up: [graph_basic_notions]
Aliases: self-loops, self_loops
+
+See also: [bidirectional_edges]
diff --git a/smallest_grammar_problem b/smallest_grammar_problem
@@ -2,9 +2,9 @@
The [computational_problem] of finding the smallest [CFG] that generates a specific set of [words].
-[np_complete]
+It is [np_complete]
-[charikar2005smallest]
+Studied in [charikar2005smallest]
Up: [minimization] of [context_free_grammar]
diff --git a/structure b/structure
@@ -1,9 +1,15 @@
# Structure
-A [structure] consists of a [domain] D, a [relational_signature] σ, and an interpretation giving, for each [relation] of σ of [arity_(relation)] k, a set of k-tuples that are those for which the relation holds
+A *structure* consists of a [domain] D, a [relational_signature] σ, and an interpretation giving, for each [relation] of σ of [arity_(relation)] k, a set of k-tuples that are those for which the relation holds
+There may also be [function_symbols]
+
+Operations:
+
+- [product_(structures)]
+- [disjoint_union]
- [substructure]
-- [reduct]: the [substructure] which is the restriction of a [structure] to a subset of the [signature]
+- [reduct]: restriction to a [subset] of the [signature]
Up: [logic]
diff --git a/triangle b/triangle
@@ -1,18 +1,19 @@
# Triangle
+The *triangle* is the [complete_graph] on 3 [vertices]; it can be an [undirected_graph], or a [directed_graph] in which case the edges may be [bidirectional_edges] or it may be a [directed_cycle]
+
+[Computational_problems]:
+
- [triangle_detection]
- unbalanced triangle detection
- [triangle_listing]
- [triangle_counting]
- [triangle_counting_incremental]
-- [provenance_triangle]
-
-Variante: single-source triangle counting ?
+ - Variant: single-source triangle counting
- [sparse_triangle]
-See also: [matrix_multiplication], [ov_conjecture], [negative_triangle], [exact_triangle], [triangle_free_graph], [triangle_inequality],
-[Loomis_Whitney]
+See also: [matrix_multiplication], [ov_conjecture], [negative_triangle], [exact_triangle], [triangle_free_graph], [triangle_inequality], [Loomis_Whitney], [provenance_triangle]
Up: [graph]
diff --git a/word_problem b/word_problem
@@ -1,6 +0,0 @@
-# Word problem
-
-Word problem for [group]
-- interesting special cases, e.g., for [coxeter_groups]
-
-Up: [computational_problem] on [group]
