OKlibrary  0.2.1.6
BasicNotions.hpp File Reference

Plans regarding notions of bicliques. More...

Go to the source code of this file.

## Detailed Description

Plans regarding notions of bicliques.

Todo:
The notion of a "biclique"
• General discussion:
1. The "full" mathematical notion of a biclique B in a (general/multi-) graph G is that of a sub-graph of G, which itself is a complete bipartite graph.
2. Since the edges determine the sub-graph B, it is natural to represent B by a set B' of edges.
3. However then we have the problem, that this notion is not stable under sub-set-formation, i.e., a subset of B' in general is not again a biclique.
4. So for multigraphs and graphs G alternatively we can use sets of *vertices* B' such that we can find edges in B' making it a complete biclique.
5. For graphs this is the subgraph induced by B'
6. However, then it is needed to specify the bipartitioning, since in general there are many ways that a set of vertices could form a biclique.
• For multigraphs a biclique partition is a "numerical condition", which seems perfectly appropriate since multigraphs are close to combinatorial matrices.
• Only for general graphs, where the edges have an identity, we need to know precisely which edges are part of the biclique.
• So we could speak of a "subgraph-biclique", "edge-set-biclique" and "vertex-set-biclique" (where the latter is a pair of vertex-sets).
• For the ordered graph versions instead a vertex-sets we have vertex-lists, and their order must conform with the given total order; the abbreviation then is "ovbc".
• DONE (since we need two subsets, it's not really a hypergraph) The vertex-bicliques then form a hereditary hypergraph (vertices the vertices of the given graph; "hereditary" means that for every hyperedge also every subset is a hyperedge, where here we must exclude subsets of size 0 or 1).
• DONE (solved by using pairs) Likely for (general) digraphs for a given vertex-biclique there are several possibilities to interprete it as a edge-biclique, but otherwise there should be no ambiguities.
• A subgraph-biclique as well as an edge-biclique can be refined by specifying an associated vertex-biclique (which fixes the bipartitioning).
Todo:
Abbreviations
• "bc" for "biclique".
• Bicliques exist as "sbc", "ebc" and "vbc" (subgraphs, edge-sets or vertex-sets).
• A test would be named e.g. "sbc_ogdg_p".
Todo:
Maximal biclique
• We need tests for checking whether a biclique is maximal (cannot be extended).
• We need maximal_bc_ogl.
• We need a version of maximal_bc_ogl allowing randomisation.
1. One control parameter is the given order of the vertices.
2. And then we have 0 <= p <= 1, which controls the probability that the left or right side is considered first.
• For an algorithm finding all maximal bicliques see ComputerAlgebra/Graphs/Lisp/Bicliques/plans/Consensus.hpp.
• And regarding *maximum* bicliques see "Maximum bicliques" in ComputerAlgebra/Graphs/Lisp/Bicliques/plans/general.hpp.

Definition in file BasicNotions.hpp.