commit 19e1dc5c3e83c41fb9c31da689d8e768a5e6dd05
parent 7d8bcbb3b969055ac63270753e82aecbd0421664
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 30 Sep 2026 08:02:44 +0200
commit with codex
Diffstat:
12 files changed, 69 insertions(+), 3 deletions(-)
diff --git a/alpha_acyclic b/alpha_acyclic
@@ -10,6 +10,8 @@ Equivalent to having a [join_tree]
Equivalent to being both [hypergraph_conformal] and [hypergraph_chordal]
+Equivalent to having an [alpha_elimination_order]
+
Equivalent to [querywidth] and [hypertreewidth] and [generalized_hypertreewidth] being 1
Defining paper proving the equivalences: [beeri1983desirability]
@@ -20,4 +22,4 @@ Can be tested in [linear_time] using [tarjan1984simple] via [chordal] and [hyper
Up: [degree_of_acyclicity]
-See also: [acyclic_hypergraph_sandwich_problem]
+See also: [acyclic_hypergraph_sandwich_problem], [alpha_leaf]
diff --git a/alpha_elimination_order b/alpha_elimination_order
@@ -0,0 +1,13 @@
+# Alpha elimination order
+
+An [elimination_order] which iteratively removes [alpha_leaves]
+
+cf [irwin2016branching] Theorem 1.15
+
+A [hypergraph] is [alpha_acyclic] iff it admits an alpha elimination order
+
+Up: [alpha_acyclic], [elimination_order]
+
+Aliases: alpha-elimination order, alpha elimination ordering, alpha-elimination ordering
+
+See also: [beta_elimination_order]
diff --git a/alpha_leaf b/alpha_leaf
@@ -0,0 +1,9 @@
+# Alpha leaf
+
+A [vertex] v in a [hypergraph] for which there exist one single [hyperedge] containing v and its [neighborhood]
+
+Up: [alpha_acyclic], [leaf]
+
+See also: [alpha_elimination_ordering], [beta_leaf], [brault2016hypergraph], [gamma_leaf]
+
+Aliases: alpha leaves
diff --git a/beta_elimination_order b/beta_elimination_order
@@ -0,0 +1,9 @@
+# Beta elimination order
+
+An [elimination_order] of a [hypergraph] where you iteratively remove [beta_leaves]
+
+Up: [beta_acyclic], [elimination_order]
+
+See also: [Alpha_elimination_order]
+
+Aliases: beta elimination orders, beta elimination ordering, beta elimination orderings, beta-elimination orders, beta-elimination ordering, beta-elimination orderings, beta-elimination order
diff --git a/conjunctive_query_signed b/conjunctive_query_signed
@@ -10,3 +10,5 @@ a [conjunctive_query] with [negation] on some [atoms]
Up: [conjunctive_query], [queries_with_negation]
See also: [hypergraph_signed]
+
+Aliases: CQ with negated atoms
diff --git a/degeneracy b/degeneracy
@@ -21,4 +21,4 @@ A [k_vertex_connected] graph has degeneracy at least k
Up: [width_measure]
-See also: [arboricity], [thickness]
+See also: [arboricity], [thickness], [elimination_order]
diff --git a/four_color_theorem b/four_color_theorem
@@ -5,4 +5,6 @@ Variant on graphs embedded in more general [genus]:
Generalization: [inoue2024three]
+Faster version: [inoue2026four]
+
Up: [graph_coloring] of [planar_graph]
diff --git a/fractional_hypertree_width_computing b/fractional_hypertree_width_computing
@@ -0,0 +1,9 @@
+# Fractional hypertree width computing
+
+It is [NP_complete] to check if an input [hypergraph] has [FHW] <= 2 ([fischl2017general])
+
+Up: [fractional_hypertree_width], [computation_problem]
+
+See also: [Generalized_hypertreewidth_computing]
+
+Aliases: Fractional hypertreewidth computing, Fractional hypertreewidth computation, Fractional hypertree width computation, FHW computation, FHW computing
diff --git a/leaf b/leaf
@@ -4,6 +4,6 @@
Up: [tree]
-See also: [internal_node], [leaf_power]
+See also: [internal_node], [leaf_power], [alpha_leaf]
Aliases: leaves
diff --git a/query_evaluation_conjunctive_query b/query_evaluation_conjunctive_query
@@ -0,0 +1,11 @@
+# Conjunctive query evaluation
+
+CQ evaluation is [NP_complete] in [combined_complexity] and even in [query_complexity], cf [chandra1977optimal]
+
+dual: [constraint_satisfaction_problem], cf [other_side]
+
+Up: [query_evaluation], [conjunctive_query]
+
+See also: [Homomorphism_problem]
+
+Aliases: CQ evaluation, conjunctive query evaluation
diff --git a/synchronizing_sets b/synchronizing_sets
@@ -0,0 +1,7 @@
+# Synchronizing sets
+
+construction in [ellert2026time]
+
+See also: [synchronizing_word]
+
+Up: [stringology]
diff --git a/uniform_sampling b/uniform_sampling
@@ -5,3 +5,5 @@
[FPAUS]: fully-polynomial almost uniform sampler
Up: [sampling]
+
+See also: [rosenbaum's_algorithm]
