commit 19c1497d43cc411d28fb0ccf358b7c218cbf4a9e
parent 2aa721eb2160c71a77ab575e0a5450f71f5bca57
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 6 Jan 2025 14:55:15 +0100
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
24 files changed, 127 insertions(+), 8 deletions(-)
diff --git a/average_degree b/average_degree
@@ -0,0 +1,5 @@
+# Average degree
+
+The [average] of the [degree] of [vertices] in a [graph]
+
+Up: [degree], [average]
diff --git a/boolean_formula b/boolean_formula
@@ -9,6 +9,6 @@ An [expression] which represents a [boolean_function], built from [literals] usi
- [term]
- [literal]
-Up: [boolean_function]
+Up: [representation] of [boolean_function]
See also: [boolean_circuit], [knowledge_compilation_classes]
diff --git a/crossing_number b/crossing_number
@@ -0,0 +1,11 @@
+# Crossing number
+
+https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)
+
+Lowest number of [edge] crossings of a [plane_embedding] of an [undirected_graph].
+
+An [undirected_graph] is a [planar_graph] iff the crossing number is zero
+
+[crossing_number_inequality]
+
+Up: [planar_graph]
diff --git a/crossing_number_inequality b/crossing_number_inequality
@@ -0,0 +1,7 @@
+# Crossing number inequality
+
+https://en.wikipedia.org/wiki/Crossing_number_inequality
+
+lower bound on the [crossing_number] as a function of the number of [edges] and [vertices]
+
+Up: [crossing_number], [inequality]
diff --git a/degree b/degree
@@ -5,5 +5,6 @@ Number of [neighbors] of a [vertex]
In [directed_graphs], we can distinguish the [indegree] and [outdegree], respectively the number of [vertices] having a edge to the [vertex], or from the [vertex]
- [maximal_degree]
+- [average_degree]
Up: [graph_basic_notions]
diff --git a/equation b/equation
@@ -9,4 +9,4 @@
Up: [mathematics]
-See also: [disequation], [inequation]
+See also: [disequation], [inequation], [equality]
diff --git a/eulers_formula b/eulers_formula
@@ -0,0 +1,9 @@
+# Euler's formula
+
+https://en.wikipedia.org/wiki/Euler_characteristic#Plane_graphs
+
+https://en.wikipedia.org/wiki/Planar_graph#Euler's_formula
+
+Up: [planar_graph]
+
+See also: [crossing_number_inequality]
diff --git a/function b/function
@@ -21,3 +21,5 @@ Notions:
Up: [mathematics]
See also: [functional_dependency]
+
+Aliases: functions
diff --git a/literal b/literal
@@ -3,3 +3,5 @@
Either a [variable] or the [negation] of a [variable]
Up: [boolean_formula]
+
+Aliases: literals
diff --git a/mathematics b/mathematics
@@ -28,6 +28,8 @@
- [function]
- [equation]
- [equation_system]
+ - [inequation]
+ - [disequation]
- [sequence]
- [cartesian_product]
- [plane_mathematics]
@@ -45,6 +47,9 @@
- [cardinal]
- [fourier_transform]
- [convexity]
+- [equality]
+- [inequality_mathematics]
+- [disequality]
## Fields
diff --git a/mathematics_fields b/mathematics_fields
@@ -16,5 +16,6 @@ classification [msc]
- [randomness]
- [fourier_analysis]
- [discrete_mathematics]
+- [statistics]
Up: [mathematics]
diff --git a/planar_graph b/planar_graph
@@ -1,6 +1,6 @@
# Planar graph
-A [graph_undirected] that can be embedded on [plane_mathematics]
+A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics]
- Recognizing them: [planarity_testing]
- [dynamic_planarity_testing]
@@ -9,18 +9,25 @@ A [graph_undirected] that can be embedded on [plane_mathematics]
- open for [treewidth]
- [planar_language]
-[Theorem]s:
+[Theorems]:
- [Kuratowskis_theorem] in terms of [topological_minors]
- [Wagners_theorem] in terms of [graph_minors]
+Necessary conditions:
+
+- [Euler's_formula]
+ - implies that [average_degree] must be at most 6
+
Specific algorithms:
- [fkt_algorithm]
-Generalizations to [hypergraph]s: [planar_hypergraph]
+Generalizations:
-Generalization: [directed_planar_graph]
+- to [hypergraphs]: [planar_hypergraph]
+- to [directed_graphs]: [directed_planar_graph]
+- to quantify the "degree of non-planarity": [crossing_number]
See also: [graph_drawing]
diff --git a/positive_threshold_function b/positive_threshold_function
@@ -0,0 +1,7 @@
+# Positive threshold function
+
+cf https://cstheory.stackexchange.com/questions/31469/which-monotone-boolean-functions-are-representable-as-thresholds-on-sums
+
+Up: [boolean_function_classes]
+
+See also: [threshold]
diff --git a/representation b/representation
@@ -0,0 +1,8 @@
+# Representation
+
+- of [boolean_function]
+ - [boolean_formula]
+ - [boolean_circuit]
+ - [pseudo_boolean_constraint]
+
+Up: [mathematics]
diff --git a/spanning_tree b/spanning_tree
@@ -6,3 +6,5 @@
See also: [steiner_tree]
Up: [tree]
+
+Aliases: spanning trees
diff --git a/statistics b/statistics
@@ -0,0 +1,6 @@
+# Statistics
+
+- [average]
+- [median]
+
+Up: [mathematics_fields]
diff --git a/submodular_approximation b/submodular_approximation
@@ -0,0 +1,5 @@
+# Submodular approximation
+
+[hochbaum2017submodular]
+
+Up: [submodular_optimization], [approximation]
diff --git a/submodular_function b/submodular_function
@@ -0,0 +1,9 @@
+# Submodular function
+
+- on [sets]: [submodular_set_function]
+- the [domain] may be different
+
+[zivny2009expressive]: [submodular_function_locally_defined], i.e., a [sum] of [functions] of bounded [arity]
+ - related to [pseudo_boolean_optimization]
+
+Up: [function]
diff --git a/submodular_optimization b/submodular_optimization
@@ -4,5 +4,6 @@ https://en.wikipedia.org/wiki/Submodular_set_function#Optimization_problems
- [submodular_minimization]
- [submodular_maximization]
+- [submodular_approximation]
-Up: [optimization]
+Up: [optimization], [submodular_function]
diff --git a/submodular_set_function b/submodular_set_function
@@ -9,4 +9,4 @@ Implies being [subadditive], converse is not true in general
See also: [submodular_optimization], [concave_function]
-Up: [function]
+Up: [submodular_function]
diff --git a/theorem b/theorem
@@ -37,3 +37,5 @@ A [result] in [mathematics], recognized as challenging to prove
Up: [mathematics]
See also: [automated_theorem_proving], [theoremkb]
+
+Aliases: theorems
diff --git a/threshold b/threshold
@@ -0,0 +1,7 @@
+# Threshold
+
+- [positive_threshold_function]
+- [pqe_threshold]
+- [locally_threshold_testable_language]
+
+Up: [mathematics]
diff --git a/tree_even b/tree_even
@@ -0,0 +1,13 @@
+# Tree even
+
+A [tree] where the length of the unique [path] connecting any two [leaves] is [even]
+
+[hanaka2024complexity] studies the problem of finding [spanning_trees] that are even.
+- [NP_hard] on general [undirected_graphs]
+- [PTIME] on [bipartite_graphs]
+
+Up: [tree]
+
+Aliases: even tree, even trees
+
+See also: [tree_odd]
diff --git a/tree_odd b/tree_odd
@@ -0,0 +1,9 @@
+# Tree odd
+
+A [tree] where the length of the unique [path] connecting any two [leaves] is [odd]
+
+[hanaka2024complexity] remarks it is equivalent to requiring that the tree is a [path]
+
+Up: [tree]
+
+See also: [tree_even]
