commit a0505616ae96f2e4293bf8561b8a99881213d217
parent b7de4b7d4417e158504784de9a1ff14a255fac8a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 11 Jun 2025 19:53:24 +0200
commit with codex
Diffstat:
12 files changed, 76 insertions(+), 16 deletions(-)
diff --git a/berge_acyclic b/berge_acyclic
@@ -0,0 +1,13 @@
+# Berge acyclic
+
+A [hypergraph] is *Berge acyclic* if its [incidence_graph] is [graph_acyclic]
+- In particular, whenever there are two [hyperedges] sharing more than one element, then the hypergraph is not Berge-acyclic
+
+Can also be defined for [database_instances] and [CQs], but then the criterion is on the [incidence_multigraph]
+- So whenever some element occurs twice in a [fact] or in an [atom] then the [database_instance] or [CQ] is not Berge acyclic
+
+If a hypergraph is Berge acyclic then any [subhypergraph] also is
+
+Up: [degree_of_acyclicity]
+
+Aliases: Berge acyclicity, incidence acyclic, incidence acyclicity
diff --git a/berge_graph b/berge_graph
@@ -5,3 +5,5 @@
[strong_perfect_graph_theorem]: a graph is a Berge graph iff it is a [perfect_graph]
Up: [graph_family]
+
+See also: [berge_acyclicity]
diff --git a/cycle b/cycle
@@ -19,6 +19,8 @@ Special cases:
- [hamiltonian_cycle]
- [eulerian_cycle]
+- [odd_cycle]
+- [even_cycle]
Up: [graph_basic_notions]
diff --git a/database_instance b/database_instance
@@ -6,6 +6,6 @@ A set of [relations] containing [tuples] or [facts], for the [relations] defined
Up: [database_theory]
-Aliases: database
+Aliases: database, database instances
See also: [instance]
diff --git a/degree_of_acyclicity b/degree_of_acyclicity
@@ -1,14 +0,0 @@
-# Degree of acyclicity
-
-foundational paper: [fagin1983degrees], see also [brault2014hypergraph]
-
-- [alpha_acyclic]
-- [beta_acyclic]
- - [lanzinger2021tractability]
-- [gamma_acyclic]
- - cf [delpia2018multilinear]
-- [berge_acyclic]
-
-Up: [hypergraph]
-
-See also: [gyo]
diff --git a/even_cycle b/even_cycle
@@ -0,0 +1,9 @@
+# Even cycle
+
+An *even cycle* is a [cycle] whose [length] is [even]
+
+- [even_cycle_free_graph]
+
+Up: [cycle]
+
+See also: [odd_cycle]
diff --git a/exptime b/exptime
@@ -0,0 +1,9 @@
+# Exptime
+
+https://en.wikipedia.org/wiki/EXPTIME
+
+in 2^{P(n)} for P a [polynomial]
+
+Up: [complexity_time_classes]
+
+See also: [2exptime], [EXPTIME_complete], [nexptime]
diff --git a/fagin1983degrees b/fagin1983degrees
@@ -0,0 +1,14 @@
+# Degree of acyclicity
+
+- [alpha_acyclic]
+- [beta_acyclic]
+ - [lanzinger2021tractability]
+- [gamma_acyclic]
+ - cf [delpia2018multilinear]
+- [berge_acyclic]
+
+Up: [academic_paper] about [hypergraph_acyclicity]
+
+See also: [gyo], [brault2014hypergraph]
+
+Aliases: degree of acyclicity
diff --git a/graph_bipartite b/graph_bipartite
@@ -9,4 +9,4 @@ Up: [graph_family], [graph_kpartite]
See also: [hypergraph_balanced], [incidence_structure], [3_colorable]
-Aliases: bipartite graph, bipartite graphs
+Aliases: bipartite graph, bipartite graphs, 2 colorable
diff --git a/hypergraph_acyclicity b/hypergraph_acyclicity
@@ -0,0 +1,16 @@
+# Hypergraph acyclicity
+
+[academic_papers]:
+- [fagin1983degrees]
+ - [alpha_acyclic]
+ - [beta_acyclic]
+ - cf [lanzinger2021tractability]
+ - [gamma_acyclic]
+ - [berge_acyclic]
+- [brault2014hypergraph]
+- [gottlob2001hypergraphs]
+ - talks about [beta_hypertreewidth]
+
+Up: [graph_acyclicity], [hypergraph]
+
+See also: [graph_traversal]
diff --git a/odd_cycle b/odd_cycle
@@ -0,0 +1,7 @@
+# Odd cycle
+
+An *odd cycle* is a [cycle] whose [length] is [odd]
+
+Up: [cycle]
+
+See also: [even_cycle]
diff --git a/union b/union
@@ -7,3 +7,5 @@
Up: [set_theory], [boolean_operator]
See also: [disjunction]
+
+Aliases: unions
