commit 385133318fc14b55803d0f65c52ab32718a2de8f
parent e18997ad9a4924615484ec5ed7c551fb41e3bd04
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 26 May 2025 15:37:36 +0200
commit with codex
Diffstat:
12 files changed, 91 insertions(+), 3 deletions(-)
diff --git a/compositionality b/compositionality
@@ -0,0 +1,7 @@
+# Compositionality
+
+the [logical_type] of a [structure] can be computed for that of its [substructures]
+
+e.g., [MSO] on [treelike_data]
+
+Up: [logic]
diff --git a/depth_tree b/depth_tree
@@ -3,3 +3,5 @@
The depth of a [node] in a [tree] is the length of the [downward_path] from the [root] to that node (so 0 for the [root])
Up: [depth], [tree]
+
+See also: [treedepth]
diff --git a/first_order_model_checking b/first_order_model_checking
@@ -17,3 +17,5 @@
Up: [model_checking] for [first_order_logic]
See also: [fine_grained_complexity], [clique_problem]
+
+Aliases: FO model checking
diff --git a/graph_embedding b/graph_embedding
@@ -0,0 +1,10 @@
+# Graph embedding
+
+- [graph_minor]
+- [topological_minor]
+- [subgraph]
+- [induced_subgraph]
+
+Up: [graph]
+
+Aliases: graph embeddings
diff --git a/graph_family b/graph_family
@@ -41,6 +41,6 @@ May have the property of being [graph_class_hereditary]
Up: [graph]
-Aliases: graph class
+Aliases: graph class, graph classes
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_h_minor_free b/graph_h_minor_free
@@ -6,6 +6,10 @@ Each [undirected_graph] H thus defines a [graph_family], which must be [sparse_g
discussed in https://en.wikipedia.org/wiki/Graph_minor
+Example: [planar_graphs] are the graphs that are {K_3, K_{5,5}}-free ([kuratowskis_theorem], [Wagners_theorem])
+
Up: [graph_free]
See also: [graph_h_free]
+
+Aliases: H minor free, minor free, H minor free graph, H minor free graphs
diff --git a/graph_minor b/graph_minor
@@ -6,7 +6,7 @@
- [graph_immersion]
-Up: [graph]
+Up: [graph_embedding]
See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor]
diff --git a/half_graphs b/half_graphs
@@ -0,0 +1,9 @@
+# Half graphs
+
+A *half graph* is a [bipartite_graph] on vertices a_1, ..., a_n, b_1, ..., b_n, with edges between a_i and b_j iff i \leq j
+
+Up: [bipartite_graph]
+
+Aliases: half graph
+
+See also: [monadically_stable]
diff --git a/hypergraph_uniform b/hypergraph_uniform
@@ -1,7 +1,9 @@
# Hypergraph uniform
-k-uniform [hypergraph]: all [hyperedge]s have size k
+k-uniform [hypergraph]: all [hyperedges] have size k
- [graph_undirected] is k-uniform [hypergraph]
Up: [hypergraph]
+
+See also: [graph_uniform]
diff --git a/monadic_second_order_logic b/monadic_second_order_logic
@@ -0,0 +1,28 @@
+# Monadic Second-Order Logic (MSO)
+
+Definition variants:
+
+- [monadic_second_order_logic_1]
+ - [quantification] over [sets] of [vertices]
+- [monadic_second_order_logic_2]
+ - [quantification] over [sets] of [edges]
+
+Extensions:
+
+- [counting_monadic_second_order_logic]
+- [weighted_MSO]
+
+[Computational_complexity]:
+
+- Tractable on [trees]
+ - Corresponds to [regular_tree_languages], cf [buchis_theorem]
+- Tractable on [treelike_data]
+ - cf [Courcelle's_theorem]
+ - it is [FPT] when parameterized by the [treewidth] of the graph and the [logical_formula]
+- [MSO1] [NP_hard] in [data_complexity] already on [planar_graphs]
+
+Up: [logic]
+
+See also: [tree_automaton], [courcelle_theorem], [first_order_logic], [second_order_logic], [monadic]
+
+Aliases: MSO, MSOL, monadic second order
diff --git a/monadic_second_order_logic_1 b/monadic_second_order_logic_1
@@ -0,0 +1,13 @@
+# Monadic second order logic 1
+
+[MSO] with [quantification] over [sets] of [vertices]
+
+also called "edge encoding"
+
+Can express that a [graph] is [3_colorable]
+
+Up: [monadic_second_order_logic]
+
+Aliases: MSO1
+
+See also: [MSO2]
diff --git a/monadic_second_order_logic_2 b/monadic_second_order_logic_2
@@ -0,0 +1,11 @@
+# Monadic second order logic 2
+
+also called "incidence encoding", corresponds to the [incidence_graph] between [vertices] and [edges]
+
+Can express that a [graph] has a [Hamiltonian_cycle], [max_cut], [edge_dominating_set], [graph_coloring]
+
+Up: [monadic_second_order_logic]
+
+Aliases: MSO2
+
+See also: [MSO1]
