Basics.hpp File Reference

Plans regarding the basic notions for hypergraphs. More...

Go to the source code of this file.

Detailed Description

Plans regarding the basic notions for hypergraphs.

Lists instead of sets
  • Additionally to "hypergraphs" and "general hypergraphs" we introduce "ordered hypergraphs" and "ordered general hypergraphs":
    1. Computationally these notions are considered to be more fundamental.
    2. An ordered hypergraphs is a pair [V,E], where V and E are lists without repetition, such that [setify(V),setify(E)] is a hypergraph.
    3. An ordered general hypergraph is a triple [V,E,f], where V, E are lists without repetition, such that [setify(V),setify(E),f] is a general hypergraph.
  • Multi-versions:

    1. We also should have "multi-hypergraphs", triples [V,E,c], s.t. [V,E] is a hypergraph, and c: E -> NN.
    2. And "ordered multi-hypergraphs, [V,E,c] s.t. [setify(V),setify(E),c] is a multi-hypergraph, and [V,E] is an ordered hypergraph.
    Naming conventions
    • "hg" for hypergraph, "ghg" for general hypergraph, and "ohg", "oghg" for the ordered versions.
    • "muhg" for multi-hypergraph, and "omuhg" for ordered multi-hypergraph.
    • Conversions then as "hg2ghg", "ohg2hg" etc.
    • Connections to graphs (see ComputerAlgebra/Graphs/Lisp/plans/general.hpp):
      1. g, gl <= hg
      2. mug, mugl <= muhg
      3. gg <= ghg
      4. og, ogl <= ohg
      5. omug, omugl <= omuhg
      6. ogg <= oghg
    Polar hypergraphs
    • While a "square hypergraph" is a hypergraph [V,E] with |V| = |E|, we introduce the notion of a "bipolar hypergraph" ("bphg") as a pair [V,f], s.t. [V,V,f] is a general hypergraph.
    • A "polar hypergraph" is a bipolar hypergraph [V,f] s.t. for all y in f(x) we also have x in f(y).
    • Specialising correspondences [R,A,B] to "relationals" [R,A], considering only symmetric relations, representing the relation R <= A^2 by a function from A to P(A), and changing the order, we have exactly the polar hypergraphs; dropping "symmetric", we get the bipolar hypergraphs.
    • Another view is that the bipolar hypergraphs [V,f] correspond exactly to the digraphs with vertex set V, where f(v) is the set of out-neighbours, while polar hypergraphs correspond exactly to the graphs with vertex set V.
    • The notion of a "polar hypergraph" comes from incidence structures:
      1. Given an incidence structure [I,A,B], a "polarity" p is a bijection p: A -> B such that I(x,p(y)) = I(y,p(x)) for all x, y in A.
      2. Given such a polarity, we obtain a "polar indicence structure" as a pair [I',A] with I': A^2 -> {0,1} through I'(x,y) := I(x,p(y)) (where I' is symmetric).
      3. And while incidence structures correspond to general hypergraphs, polar incidence structures correspond to polar hypergraphs.
      4. See ComputerAlgebra/IncidenceStructures/Lisp/plans/general.hpp.
    • Relations with graphs:
      1. We have natural translations gl2phg, dgl2bphg and phg2gl, bphg2dgl.
      2. Additionally we also have bphg2g, which is the same as g2dg after bphg2dgl.
      3. For the direction (d)gl2(b)phg, it seems most natural to implement the function f through hash-maps.
      4. Additionally we have stdgl2phg and stddgl2bphg, which use arrays.

Definition in file Basics.hpp.