commit 33811b492e68d0fd3e636820a65d57548a2e4f12
parent 2c525d39a41e336f9b35fa9004248189a60e797f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 29 May 2025 12:18:57 +0200
commit with codex
Diffstat:
12 files changed, 76 insertions(+), 20 deletions(-)
diff --git a/c2 b/c2
@@ -11,6 +11,6 @@ Turns out to be the expressive power of [Weisfeiler_Leman]
subclass: [gc2]
-Up: [logic]
+Up: [logic], [C]
See also: [FO2_plus_C]
diff --git a/equivalence_relation b/equivalence_relation
@@ -5,3 +5,5 @@ A [mathematics_relation] is an equivalence relation if it is [relation_symmetric
Up: [mathematics]
See also: [equivalence_class], [quotient], [partition]
+
+Aliases: equivalence relations
diff --git a/first_order_logic_successor_invariant b/first_order_logic_successor_invariant
@@ -0,0 +1,9 @@
+# First order logic successor invariant
+
+FO with access to a [successor_relation], the formula is independent from the specific successor relation picked
+
+Up: [first_order_logic], [successor_invariant]
+
+See also: [first_order_logic_order_invariant], [julien_grange]
+
+Aliases: successor invariant FO
diff --git a/graph_minor b/graph_minor
@@ -8,6 +8,6 @@
Up: [graph_embedding]
-See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor]
+See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor], [minor_closed]
Aliases: graph minors, minor, minors
diff --git a/grid_graph b/grid_graph
@@ -8,4 +8,4 @@ Up: [graph_family]
See also: [wall_graph]
-Aliases: grid graphs
+Aliases: grid graphs, grid
diff --git a/matrix b/matrix
@@ -2,23 +2,7 @@
## Types
-- [matrix_square]
-- [matrix_zero]
-- [matrix_boolean]
-- [matrix_identity]
-- [matrix_permutation]
-- [matrix_diagonal]
-- [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] has [determinant] 0 or 1 or -1
-- [strongly_unimodular] matrix
-- [pet_matrix]
+[matrix_types]
## Operations
@@ -31,6 +15,10 @@
- [determinant] and [permanent]
- [trace]
+## Concepts
+
+- [eigenvalue]
+
## [computational_problem]
- [matrix_multiplication]
diff --git a/matrix_symmetric b/matrix_symmetric
@@ -0,0 +1,7 @@
+# Matrix symmetric
+
+A [matrix] M where M[i,j ] = M[j,i ] for all i, j
+
+Up: [matrix_types]
+
+Aliases: symmetric matrix, symmetric matrices
diff --git a/matrix_types b/matrix_types
@@ -0,0 +1,23 @@
+# Matrix types
+
+- [matrix_square]
+- [matrix_zero]
+- [matrix_boolean]
+- [matrix_identity]
+- [matrix_permutation]
+- [matrix_diagonal]
+- [matrix_triangular]
+- [matrix_invertible]
+- [matrix_vandermonde]
+- [matrix_positive_semidefinite]
+- [matrix_toeplitz]
+- [matrix_stochastic]
+ - [matrix_doubly_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] has [determinant] 0 or 1 or -1
+- [strongly_unimodular] matrix
+- [pet_matrix]
+- [matrix_symmetric]
+
+Up: [matrix]
diff --git a/order b/order
@@ -6,6 +6,9 @@
- [linear_extension], see also [topological_sort]
- [well_quasi_ordering]
- [upper_bound] / [lower_bound]
+- [comparability_pair]
+- [comparability_graph]
+- [hasse_diagram]
Up: [mathematics]
diff --git a/reconstruction_conjecture b/reconstruction_conjecture
@@ -2,4 +2,7 @@
https://en.wikipedia.org/wiki/Reconstruction_conjecture
+Are [graphs] determined by the [multiset] of their [subgraphs]?
+- also a [set] version
+
Up: [graph_reconstruction]
diff --git a/todas_theorem b/todas_theorem
@@ -0,0 +1,7 @@
+# Toda's theorem
+
+https://en.wikipedia.org/wiki/Toda%27s_theorem
+
+The [polynomial_hierarchy] is included in [P_PP] ([P] to the [PP])
+
+Up: [theorem]
diff --git a/topological_sorting b/topological_sorting
@@ -0,0 +1,14 @@
+# Topological sorting
+
+Problem on [directed_graphs]: find a [total_order] on the graph vertices such that whenever u has a path to v then u comes before v in the order
+- only possible, as stated, when the graph is a [DAG]
+
+https://en.wikipedia.org/wiki/Topological_sorting
+
+- [constrained_topological_sorting]
+
+Up: [graph_algorithm], [directed_acyclic_graph]
+
+See also: [strongly_connected_component_algorithm]
+
+Aliases: topological sort, topological ordering, topological orderings
