Processing math: 21%

Oksana Firman ; Joachim Spoerhase - Hypergraph Representation via Axis-Aligned Point-Subspace Cover

dmtcs:11676 - Discrete Mathematics & Theoretical Computer Science, February 13, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.11676
Hypergraph Representation via Axis-Aligned Point-Subspace CoverArticle

Authors: Oksana Firman ; Joachim Spoerhase

    We propose a new representation of k-partite, k-uniform hypergraphs, that is, a hypergraph with a partition of vertices into k parts such that each hyperedge contains exactly one vertex of each type; we call them k-hypergraphs for short. Given positive integers ,d, and k with d1 and k={d\choose\ell}, any finite set P of points in \mathbb{R}^d represents a k-hypergraph G_P as follows. Each point in P is covered by k many axis-aligned affine \ell-dimensional subspaces of \mathbb{R}^d, which we call \ell-subspaces for brevity and which form the vertex set of G_P. We interpret each point in P as a hyperedge of G_P that contains each of the covering \ell-subspaces as a vertex. The class of \emph{(d,\ell)-hypergraphs} is the class of k-hypergraphs that can be represented in this way. The resulting classes of hypergraphs are fairly rich: Every k-hypergraph is a (k,k-1)-hypergraph. On the other hand, (d,\ell)-hypergraphs form a proper subclass of the class of all k-hypergraphs for \ell<d-1. In this paper we give a natural structural characterization of (d,\ell)-hypergraphs based on vertex cuts. This characterization leads to a poly\-nomial-time recognition algorithm that decides for a given k-hypergraph whether or not it is a (d,\ell)-hypergraph and that computes a representation if existing. We assume that the dimension d is constant and that the partitioning of the vertex set is prescribed.


    Volume: vol. 27:2
    Section: Combinatorics
    Published on: February 13, 2025
    Accepted on: February 8, 2025
    Submitted on: July 31, 2023
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 105 times.
    This article's PDF has been downloaded 58 times.