wiki_research

commit 2b5689ea7d28d1623cb968bc42c7a9a172d2bd58
parent af0060b2161660e06c4191156e5105649f99b778
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 28 May 2025 15:33:42 +0200

commit with codex

Diffstat:
boolean_clique_conjecture
 | 
5
+++++
conjunctive_query_boolean
 | 
2
+-
entropic_vector
 | 
8
++++++++
graph_coloring
 | 
7
++++---
graph_regular
 | 
2
++
h_coloring
 | 
7
+++++++
kolmogorov_complexity
 | 
5
+++++

7 files changed, 32 insertions(+), 4 deletions(-)
diff --git a/boolean_clique_conjecture b/boolean_clique_conjecture
@@ -0,0 +1,5 @@
+# Boolean clique conjecture
+
+for all ε>0, there is no [combinatorial_algorithm] that can check for a k-[clique] in an input [graph] in time O(n^{k-ε})
+
+Up: [computational_complexity_hypothesis]
diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean
@@ -4,4 +4,4 @@
 
 Up: [conjunctive_query], [query_boolean]
 
-Aliases: Boolean CQ, Boolean CQs
+Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query
diff --git a/entropic_vector b/entropic_vector
@@ -0,0 +1,8 @@
+# Entropic vector
+
+https://en.wikipedia.org/wiki/Entropic_vector
+
+- We have n [random_variables] x1 ... xn
+- We consider the [vector] of 2^n coordinates mapping each [subset] to the [entropy] of the [joint_distribution] on that [subset] of the [variables] ([marginalizing] away the others)
+
+Up: [entropy]
diff --git a/graph_coloring b/graph_coloring
@@ -21,15 +21,16 @@
 - [edge_coloring]
 - [list_coloring]
 - [graph_coloring_counting]
+- [H_coloring]:
 
 ## Complexity
 
-- [np_complete], already for [graph_planar] and 4-regular graphs 
+- [np_complete], already for [graph_planar] and [4_regular] graphs 
   - [np_complete] to find if it is 3 or 4
-    - knowing if it is 2 is [graph_bipartite] hence [ptime]-testable
-    - 4 colors is always feasible by the [four_color_theorem]
+    - 4 colors on [planar_graph] is always feasible by the [four_color_theorem]
 - [3_coloring] is in [linear_time] by [Brook's_theorem] on [graphs] of maximal [degree] 3
   - see https://cstheory.stackexchange.com/questions/51368/which-hypergraphs-can-be-simplified-by-alternatively-removing-a-hyperedge-and-an
+- [bipartiteness_testing] (k=2)
 
 ## References
 
diff --git a/graph_regular b/graph_regular
@@ -8,6 +8,8 @@ https://mathoverflow.net/questions/428212/perfect-matching-decomposition-algorit
 
 [Special_case]:
 - [2_regular]
+- [3_regular]
+- [4_regular]
 
 See also: [graph_matching_covered]
 
diff --git a/h_coloring b/h_coloring
@@ -0,0 +1,7 @@
+# H coloring
+
+Testing if an input [graph] can be mapped to a fixed template graph H by a [homomorphism]
+
+Equivalent to [CSP]
+
+Up: [graph_coloring]
diff --git a/kolmogorov_complexity b/kolmogorov_complexity
@@ -0,0 +1,5 @@
+# Kolmogorov complexity
+
+- [nothing_up_my_sleeve_number]
+
+Up: [information_theory]