commit 4c79a3f8f9d1350d62cdd9774f14375d0feccbe1
parent 6251944caf1dac2583367717f0b35b46b6e4175a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 5 Sep 2026 11:53:09 +0200
fixes
Diffstat:
10 files changed, 23 insertions(+), 19 deletions(-)
diff --git a/4clique_hypothesis b/4clique_hypothesis
@@ -1,7 +1,13 @@
-# 4clique hypothesis
+# 4-clique hypothesis
-[bringmann2022tight]: you cannot determine in O(n^3) whether a [graph] contains a [4_clique]
+[bringmann2022unbalanced] Definition 2.5: you cannot determine in O(n^3) whether a [graph] contains a [4_clique] (the [clique_problem] for [4_cliques])
+
+also in [gutenberg2020new] and in [carmeli2019enumeration]
+
+this is a special case of the [k_clique_hypothesis] from [lincoln2020tight]
Up: [computational_hypothesis], [4_clique]
-See also: [hyperclique_hypothesis]
+See also: [hyperclique_hypothesis], [triangle_detection_conjecture]
+
+Aliases: 4 clique hypothesis
diff --git a/ackermanns_function b/ackermanns_function
@@ -1,9 +1,6 @@
# Ackermanns_function
-A(1) = 1+1 [addition]
-A(2) = 2x2 = 2+2 [multiplication]
-A(3) = 3^3 = 3×3x3 [exponentiation]
-A(4) = 4 [tetration] 4 = 4^(4^(4^4)) [tetration]
+[ackermanns_function_unary]
Up: [mathematics]
diff --git a/clique b/clique
@@ -2,7 +2,7 @@
https://en.wikipedia.org/wiki/Clique_(graph_theory)
-[graph_complete] as [subgraph] of a [graph]. Cf [clique_problem]
+A [complete_graph] as [subgraph] of a [graph]. Cf [clique_problem]
- [clique_listing]
- [triangle_listing]
diff --git a/clique_problem b/clique_problem
@@ -1,16 +1,16 @@
# Clique problem
-Problem of finding [clique] in input [graph]
+The [computational_problem] of finding a [clique] in an input [graph]
Also:
- subgraph with the largest proportion of edges ([np_hard] for the same reason),
-- [densest_subgraph]: subgraph of maximal density (#edges/#vertices) which is [ptime] and
-reducible to [network_flow]
+- [densest_subgraph]: subgraph of maximal density (#edges/#vertices) which is [ptime] and reducible to [network_flow]
-- [4clique_hypothesis]
+- [4_clique_hypothesis]
+- [k_clique_hypothesis]
Up: [graph_problem] of finding [clique]
-See also: [clique_listing], [hyperclique_detection], [hyperclique_conjecture], [cycle_problem]
+See also: [clique_listing], [hyperclique_detection], [hyperclique_conjecture], [cycle_problem], [triangle_detection]
Aliases: k_clique
diff --git a/expansion b/expansion
@@ -1,6 +1,6 @@
# Expansion
-Given a [database_instance] I on a [relational_signature] σ, for a [supersignature] σ' of σ, the *reduct* of I on σ' is the [database_instance] J such that I is the [reduct] of J on σ
+Given a [database_instance] I on a [relational_signature] σ, for a [supersignature] σ' of σ, an *expansion* of I on σ' is a [database_instance] J such that I is the [reduct] of J on σ
See also: [reduct]
diff --git a/fine_grained_complexity_problems b/fine_grained_complexity_problems
@@ -10,6 +10,7 @@
- [vutd]
- [zero_clique]
- [triangle_detection] / [sparse_triangle]
+- [k_clique]
- [hyperclique] / [sparse_hyperclique]
Up: [fine_grained_complexity], [computational_problem]
diff --git a/graph_h_minor_free b/graph_h_minor_free
@@ -6,7 +6,7 @@ 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])
+Example: [planar_graphs] are the graphs that are {K_5, K_{3,3}}-free ([kuratowskis_theorem], [Wagners_theorem])
Up: [graph_free]
diff --git a/menage_problem b/menage_problem
@@ -5,5 +5,3 @@ https://en.m.wikipedia.org/wiki/M%C3%A9nage_problem
Seating male-and-female couples at a table so that men and women alternate and no one sits next to their partner
Up: [combinatorics]
-
-See also: [heteronormative_math]
diff --git a/tree_undirected b/tree_undirected
@@ -1,6 +1,6 @@
-# Tree undirected
+# Undirected tree
-An [undirected_graph] which is a [connected_graph]
+An [undirected_graph] which is a [connected_graph] and an [acyclic_graph]
Up: [tree]
diff --git a/triangle_detection_conjecture b/triangle_detection_conjecture
@@ -4,3 +4,5 @@
- [dense_triangle_hypothesis]: asserts that for [graph_dense] you cannot do O(n^{omega-delta}) for any delta>0
Up: [computational_hypothesis] on [triangle_detection]
+
+See also: [4_clique_hypothesis]
