commit 7151be82d7ef7c3912678c2ff1067ca5069c6ddb
parent 4c79a3f8f9d1350d62cdd9774f14375d0feccbe1
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 5 Sep 2026 13:05:42 +0200
commit with codex
Diffstat:
30 files changed, 25 insertions(+), 90 deletions(-)
diff --git a/arboricity b/arboricity
@@ -3,7 +3,7 @@
A [width_measure] on [undirected_graphs]: the minimum number of [spanning_forests] needed to cover all [edges] of the [graph]
- equivalently, the [minimum] number of [forests] in which the [edges] can be partitioned
-A [planar_graph] has arboricity has arboricity at most 3
+A [planar_graph] has arboricity at most 3
Connection between [arboricity] and [dynamic_data] in [lu2021towards]
diff --git a/chebyshevs_inequality b/chebyshevs_inequality
@@ -1,11 +0,0 @@
-# Chebyshev's inequality
-
-https://en.wikipedia.org/wiki/Chebyshev%27s_inequality
-
-Pr[|X - EX| \geq epsilon EX] \leq (Var X) epsilon^2 (EX)^2
-
-Up: [concentration_inequality]
-
-See also: [expectation], [variance]
-
-Aliases: Chebyshev inequality, Chebyshef inequality, Chebyshef's inequality
diff --git a/clique b/clique
@@ -18,4 +18,4 @@ Up: [graph]
See also: [cliquewidth], [fine_grained_complexity], [treewidth], [graph_minor], [graph_complete], [hyperclique], [multicolored_clique]
-Aliases: cliques
+Aliases: cliques, k clique, k cliques
diff --git a/clique_listing b/clique_listing
@@ -1,6 +1,6 @@
# Clique listing
-Bound: graph with m edges has at most plus O(m^{k/2}) k-cliques
+Bound: graph with m edges has at most O(m^{k/2}) [k_cliques]
Special case: [triangle_listing]
diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic
@@ -4,7 +4,7 @@ Can be evaluated by [yannakakis_algorithm] following a [join_tree]
- [acyclic_free_connex]
-the evaluation problem is in the complexity class [logcfl], and the the complexity is in O(database×query + output)
+the evaluation problem is in the complexity class [logcfl], and the complexity is in O(database×query + output)
We can test in linear time if a [hypergraph] is acyclic and if so build the [join_tree]: [GYO_algorithm]
- not so obvious to understand where the [linear_time] claim comes from...
diff --git a/description_logics b/description_logics
@@ -10,7 +10,6 @@ Classes:
- [DL_Lite]
- [DL_Lite_F]
- [DL_Lite_FR]
- - [DL_Lite_FR]
- [ALC]
- conjunctions imply disjunctions
- can use existentials in [rule_head] and [rule_body]
diff --git a/disjoint_paths_undirected b/disjoint_paths_undirected
@@ -2,7 +2,7 @@
Given an [undirected_graph] G and vertices s_1, t_1, ..., s_k, t_k, decide whether there exist k [disjoint_paths] connecting s_i and t_i for each i
-It is is [NP_complete] if k is not fixed ([karp1975computational], cited in [liu2025disjoint])
+It is [NP_complete] if k is not fixed ([karp1975computational], cited in [liu2025disjoint])
- For any constant k, by [Robertson_Seymour] it is [PTIME], in O(n^3), and even in [almost_linear_time] by [korhonen2024minor]
- It is [FPT] parameterized by k
diff --git a/enumeration_delay b/enumeration_delay
@@ -13,7 +13,7 @@ Variants:
- [output_linear_delay]
- [polynomial_total_time]
- [incremental_polynomial_time]
-- notion de [incremental_total_time], cf
+- [incremental_total_time]
Up: [enumeration_definition]
diff --git a/forest b/forest
@@ -1,6 +1,6 @@
# Forest
-A [set] of [trees] (for [tree_unordered]), or possibly a [sequence] of [trees] (for [tree_unordered])
+A [set] of [trees] (for [tree_unordered]), or possibly a [sequence] of [trees] (for [tree_ordered])
Generalization: [pseudoforest]
diff --git a/graph_minor_testing b/graph_minor_testing
@@ -1,6 +1,6 @@
# Graph minor testing
-Given [undirected_graphs] G and H, decide whether G a [graph_minor] of H
+Given [undirected_graphs] G and H, decide whether G is a [graph_minor] of H
Can be done in [almost_linear_time] for fixed H [korhonen2024minor]
diff --git a/hadwiger_conjecture b/hadwiger_conjecture
@@ -2,7 +2,7 @@
https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)
-Asks whether every [graph] with [chromatic_number] k have a k-[clique] as a [graph_minor]
+Asks whether every [graph] with [chromatic_number] k has a [k_clique] as a [graph_minor]
Up: [graph_coloring]
diff --git a/integers b/integers
@@ -1,6 +1,6 @@
# Integers
-The set \mathbb{Z} of [natural_numbers] or the [negative_numbers] (including [zero])
+The set \mathbb{Z} including the [natural_numbers], the [negative_numbers], and [zero]
Up: [number]
diff --git a/leftist_heap b/leftist_heap
@@ -20,7 +20,7 @@ So worse than [Brodal_queue]
## [Meld]
-Let's merge two min leftist heaps with the the first one having the lower key
+Let's merge two min leftist heaps with the first one having the lower key
Merge it with the right child
diff --git a/linear_datalog_conjecture b/linear_datalog_conjecture
@@ -1,6 +1,6 @@
# Linear datalog conjecture
-mentionde in [bodirsky2024symmetric]: is it true that every
+mentioned in [bodirsky2024symmetric]: is it true that every
[finite_domain_CSP] which is in [NL] can be solved by a [linear_Datalog] program
Up: [conjecture], [datalog_linear]
diff --git a/many_one_reduction b/many_one_reduction
@@ -1,13 +0,0 @@
-# Many-one reduction
-
-[reduction] that transforms an instance of A into an instance of B and answer in the same way
-
-Called "Karp reduction" when it is [ptime_reduction]
-
-- restriction "one-one" when the reduction function is injective ; aussi notion "recursively isomorphic"
-
-Up: [reduction]
-
-See also: [turing_reduction], [weihrauch_reduction]
-
-Aliases: Many one reductions, Karp reduction, Karp reductions
diff --git a/minimization_automaton b/minimization_automaton
@@ -5,6 +5,6 @@
Up: [minimization] of [automaton]
-Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton, automaton minimisation, automata minimisation
+Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton, minimal automata, automaton minimisation, automata minimisation
See also: [canonical_labeling], [canonical_DFA]
diff --git a/multigraph_directed b/multigraph_directed
@@ -1,9 +0,0 @@
-# Directed multigraph
-
-#todo
-
-Up: [multigraph], [directed_graph]
-
-Aliases: directed multigraph, directed multigraphs
-
-See also: [undirected_multigraph]
diff --git a/multigraph_undirected b/multigraph_undirected
@@ -1,9 +0,0 @@
-# Undirected multigraph
-
-#todo
-
-Up: [multigraph], [undirected_graph]
-
-Aliases: undirected multigraph, undirected multigraphs
-
-See also: [directed_multigraph]
diff --git a/nobdd b/nobdd
@@ -2,7 +2,7 @@
[obdd] [nondeterministic]
-[sauerhoff2003guess]: in an nOBDD, imposing that nondetermistic guesses are at the beginning can cause an exponential blowup
+[sauerhoff2003guess]: in an nOBDD, imposing that nondeterministic guesses are at the beginning can cause an exponential blowup
- [nobdd_model_counting]
diff --git a/np_complete b/np_complete
@@ -9,7 +9,7 @@ Problem which is in [nptime] and [np_hard]
- [bin_packing]
- [3_dimensional_matching]
- [knapsack]
- - [subset_sum] mais [pseudo_polynomial_time] algorithm
+ - [subset_sum] but [pseudo_polynomial_time] algorithm
- [hitting_set]
- https://en.wikipedia.org/wiki/List_of_NP-complete_problems
- [garey_johnson]
diff --git a/number_theory b/number_theory
@@ -3,7 +3,8 @@
Open problems:
- Infinite number of [mersenne_prime] / odd [perfect_number]?
-- existence of an even [perfect_number]?
+- existence of an odd [perfect_number]?
+- existence of infinitely many [perfect_numbers]
- [goldbach_conjecture]
- [ternary_goldbach_problem]
- [twin_prime_conjecture]
diff --git a/partial_order b/partial_order
@@ -15,7 +15,7 @@ Variants:
- [omega_complete]
- [ascending_chain_condition]
- - generalization [poset_rank]: largest rank of a stricly increasing [chain]
+ - generalization [poset_rank]: largest rank of a strictly increasing [chain]
- (minus one: x0 < ... < xr has rank r)
- [least_upper_bound]
diff --git a/perfect_elimination_ordering b/perfect_elimination_ordering
@@ -1,6 +1,6 @@
# Perfect elimination ordering
-A *perferct elimination ordering* of an [undirected_graph] is a [vertex_ordering] such that for every [vertex], its higher-numbered neighbors forms a [clique]
+A *perfect elimination ordering* of an [undirected_graph] is a [vertex_ordering] such that for every [vertex], its higher-numbered neighbors forms a [clique]
See also: [chordal], [degeneracy]
diff --git a/provenance_datalog b/provenance_datalog
@@ -16,6 +16,6 @@ Subcases:
For [datalog_extensions]:
- [datalog_negation_provenance]
-- [bogaerts2025why] [bogaerts2026why] pour [datalog_with_negation]
+- [bogaerts2025why] [bogaerts2026why] for [datalog_with_negation]
Up: [provenance], [datalog]
diff --git a/query_approximation b/query_approximation
@@ -3,7 +3,7 @@
- [under_approximation]
- [maximal_under_approximation]
- [over_approximation]
- - [minimal_under_approximation]
+ - [minimal_over_approximation]
Up: [query_evaluation]
diff --git a/query_evaluation b/query_evaluation
@@ -3,7 +3,7 @@
- [query_evaluation_conjunctive_query] for [conjunctive_query]
- [datalog_query_evaluation] for [datalog]
- [datalog_semiring_query_evaluation] for [datalog_semiring]
-- [agm_bound] pour [conjunctive_query] / [optimal_joins]
+- [agm_bound] for [conjunctive_query] / [optimal_joins]
- [panda]
- for [provenance] and [datalog_acyclic], see [wang2021query]
- [query_optimization]
diff --git a/query_rewriting b/query_rewriting
@@ -1,23 +0,0 @@
-# Query rewriting
-
-from a [query], produce a [query] which is [query_equivalent] and has some better properties, e.g.,
-- membership to restricted [query_language]
-
-## Examples
-
-- [first_order_rewriting]
- - [fok_rewriting]
-- [datalog_rewriting]
-- [UCQ_rewriting]
-
-## Distiction
-
-Distinguish
-- rewritability
- - an [algorithm] that can rewrite a [query_language] into another in a [computable] way
-- [expressibility]
- - [queries] in a given [query_language] can always be expressed as a [query_equivalent] [query] in another [query_language]
-
-Up: [database_theory]
-
-See also: [query_evaluation], [OMQA]
diff --git a/regex_formula b/regex_formula
@@ -2,7 +2,7 @@
A *regex formula* is like a [regular_expression] but with [capture_variables] of the form x{alpha} where x is a [variable] and alpha is a [regular_expression]
-It recognizes a [subset] of the [spanners] that can be expressed with of [vset_automata]
+It recognizes a [subset] of the [spanners] that can be expressed with [vset_automata]
Up: [spanner]
diff --git a/star_free_language b/star_free_language
@@ -5,7 +5,7 @@
- Language that can be defined from letters, empty set, empty word, and [boolean_operations] ([union], [intersection], [complement]) and [concatenation] but not [kleene_star]
- [aperiodic] [syntactic_monoid]
- characterization based on loops in the [automata] ([automaton_counter_free])
- - can always tested on the minimal automata ([automaton_minimization])
+ - can always be tested on the [minimal_automata]
## Subclass
diff --git a/variable_set_automaton b/variable_set_automaton
@@ -5,7 +5,7 @@ Like an [automaton] but with [capture_variables], specifically, [transitions] la
We only consider the [runs] where the markers are assigned correctly:
- every [variable] is opened exactly once and then closed exactly once
-However, but we do not require markers to be [well_nested], unlike [regex_formulas] where this is required.
+However, we do not require markers to be [well_nested], unlike [regex_formulas] where this is required.
[spanners_incomplete]
