François Pitois ; Mohammed Haddad ; Hamida Seba ; Olivier Togni - Hypergraphs with Polynomial Representation: Introducing $r$-splits

dmtcs:10751 - Discrete Mathematics & Theoretical Computer Science, January 2, 2024, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10751
Hypergraphs with Polynomial Representation: Introducing $r$-splitsArticle

Authors: Mohammed Haddad ; François Pitois ; Hamida Seba ; Olivier Togni

    Inspired by the split decomposition of graphs and rank-width, we introduce the notion of $r$-splits. We focus on the family of $r$-splits of a graph of order $n$, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$ of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least $\Omega(n^r)$ hyperedges to be represented, using a generalization of set orthogonality.


    Volume: vol. 25:3 special issue ICGT'22
    Section: Special issues
    Published on: January 2, 2024
    Accepted on: November 2, 2023
    Submitted on: December 29, 2022
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 423 times.
    This article's PDF has been downloaded 308 times.