Maurice Pouzet ; Hamza Si Kaddour ; Bhalchandra Thatte - On the Boolean dimension of a graph and other related parameters

dmtcs:7437 - Discrete Mathematics & Theoretical Computer Science, September 23, 2022, vol. 23 no. 2, special issue in honour of Maurice Pouzet - https://doi.org/10.46298/dmtcs.7437
On the Boolean dimension of a graph and other related parametersArticle

Authors: Maurice Pouzet 1,2,3; Hamza Si Kaddour 1,2,3; Bhalchandra Thatte 4


We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions, and with the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.

https://doi.org/10.46298/dmtcs.7437
Source: HAL:hal-03214095v4
Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
Section: Special issues
Published on: September 23, 2022
Accepted on: August 2, 2022
Submitted on: May 3, 2021
Keywords: 06A6, 06F15, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] graphs, Boolean sum, symplectic dimension, geometric dimension, tournaments, inversion index
Funding:
    Source : OpenAIRE Graph
  • Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-0007
  • Funder: French National Research Agency (ANR); Code: ANR-10-LABX-0070

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 781 times.
This article's PDF has been downloaded 730 times.