=Paper=
{{Paper
|id=Vol-2925/short7
|storemode=property
|title=A note on the Boolean dimension of a graph and other related parameters
|pdfUrl=https://ceur-ws.org/Vol-2925/short7.pdf
|volume=Vol-2925
|authors=Maurice Pouzet,Hamza Si Kaddour,Bhalchandra D. Thatte
|dblpUrl=https://dblp.org/rec/conf/algos/PouzetKT20
}}
==A note on the Boolean dimension of a graph and other related parameters==
https://ceur-ws.org/Vol-2925/short7.pdf
A NOTE ON THE B OOLEAN DIMENSION OF A GRAPH AND OTHER
RELATED PARAMETERS
Maurice Pouzet
Univ. Lyon, Université Claude-Bernard Lyon1
CNRS UMR 5208, Institut Camille Jordan
43, Bd. du 11 Novembre 1918, 69622 Villeurbanne, France
Department of Mathematics and Statistics
University of Calgary, Calgary, Alberta, Canada
Hamza Si Kaddour
Univ. Lyon, Université Claude-Bernard Lyon1
CNRS UMR 5208, Institut Camille Jordan
43, Bd. du 11 Novembre 1918, 69622 Villeurbanne, France
Bhalchandra D. Thatte ∗
Departamento de Matemática
Universidade Federal de Minas Gerais (UFMG)
Av. Antonio Carlos, 6627
Caixa Postal 702, Região Pampulha
Belo Horizonte - MG, CEP: 31270-901, Brasil
A BSTRACT
We consider Boolean, binary and symplectic dimensions 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 binary
dimension to the mrank2 of a graph.
Keywords Graphs ⋅ Tournaments
1 Preliminaries
Let F2 be the 2-element field, identified with the set {0, 1}. Let U be a vector space over F2 , and B be a bilinear form
over U . This form is symmetric if B(x, y) = B(y, x) for all x, y ∈ U . A vector x ∈ U � {0} is isotropic if B(x, x) = 0;
two vectors x, y are orthogonal if B(x, y) = 0. The form B is said to be alternating if each x ∈ U is isotropic, in
which case (U, B) is called a symplectic space. The form is a scalar product if U has an orthonormal base (made
of non-isotropic and pairwise othogonal vectors). If U has finite dimension, say k, we identify it with Fk2 , the set of
all k-tuples over {0, 1}; we suppose that the scalar product of two vectors x ∶= (x1 , . . . , xk ) and y ∶= (y1 , . . . , yk ) is
�x � y� ∶= x1 y1 + ⋅ ⋅ ⋅ + xk yk .
∗
Supported by CAPES Brazil (Processo: 88887.364676/2019-00); the stay of this author was supported by LABEX MILYON
(ANR-10-LABX-0070) of Université de Lyon within the program "Investissements d’Avenir (ANR-11-IDEX-0007)" operated by the
French National Research Agency (ANR).
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The graphs we consider are undirected and have no loop. That is a graph is a pair (V, E) where E is a subset of [V ]2 ,
the set of 2-element subsets of V . Elements of V are the vertices and elements of E are its edges. The graph G be given,
we denote by V (G) its vertex set and by E(G) its edge set. For u, v ∈ V (G), we write u ∼ v if there is an edge joining
u and v. For a vertex v ∈ V (G), we denote by N (v) the set of vertices in G adjacent with v. We are going to define
three notions of dimension of a graph. The graph does not need to be finite, but our main results are for finite graphs.
Definition 1.1. Let B∶ U × U → F2 be a symmetric bilinear form. Let G be a graph. We say that ∶ V (G) → U is
a representation of G in (U, B) if for all u, v ∈ V (G), u ≠ v, we have u ∼ v if and only if B( (u), (v)) = 1. The
binary dimension of G is the least cardinal for which there exists a symmetric bilinear form B on a vector space U of
dimension and exists a representation of G in (U, B). The symplectic dimension of G is the least cardinal for which
there exists a symplectic space (U, B) in which G has a representation. When the bilinear form is a scalar product, a
representation is called a Boolean representation. The Boolean dimension of G is the least cardinal for which G has a
Boolean representation in a space of dimension equipped with a scalar product.
For the Boolean representation and the Boolean dimension, we have the following equivalent definition (Proposition 3.1
of [2]).
Definition 1.2. Let G be a graph. A Boolean representation is a family V ∶= (Vi )i< of subsets of V such that u ∼ v if
and only u and v belong to an odd number of Vi ’s. The Boolean dimension is the minimum cardinality of the family V
for which such a representation exists. The Boolean dimension of G is denoted by b(G).
This notion of Boolean dimension has been considered by Belkhechine et al. [2, 3] (see also [1, 7]) The symplectic
dimension has also been considered by other authors, for example, [5, 6].
2 Boolean dimension of trees
In this section, we show that there is a nice combinatorial interpretation for the Boolean dimension of trees.
We mention the following result [Belkhechine et al. [3]]
Lemma 2.1. Let G ∶= (V, E) be a graph, with V ≠ �. Let f ∶ V → Fm2 be a boolean representation of G. Let S ⊆ V
such that S ≠ �. Suppose that for all A ⊆ S, A ≠ �, there exists v ∈ V � A such that �N (v) ∩ A� is odd. Then
{f (x) � x ∈ A} is linearly independent.
This suggests the following definition.
Definition 2.2 (Belkhechine et al. [3]). Let G ∶= (V, E) be a graph. A set U ⊂ V is called independent (mod 2) if
for all B ⊆ U, B ≠ �, there exists u ∈ V � B such that �NG (u) ∩ B� is odd, where NG (u) denotes the neighbourhood
of u in G; otherwise U is said to be dependent (mod 2). Let a(G) denote the maximum size of an independent
set (mod 2) in G. From now, we omit (mod 2) unless it is necessary to talk about independence in the graph
theoretic sense.
Definition 2.3. Let T ∶= (V, E) be a tree. A star decomposition ⌃ of T is a family {S1 , . . . , Sk } of subtrees of T such
that each Si is isomorphic to K1,m (a star) for some m ≥ 1, the stars are mutually edge-disjoint, and their union is
T . For a star decomposition ⌃, let t(⌃) be the number of trivial stars in ⌃ (stars that are isomorphic to K1,1 ), and
let s(⌃) be the number of nontrivial stars in ⌃ (stars that are isomorphic to K1,m for some m > 1). We define the
parameter m(T ) ∶= min⌃ {t(⌃) + 2s(⌃)} over all star decompositions ⌃ of T . A star decomposition ⌃ of T for which
t(⌃) + 2s(⌃) = m(T ) is called an optimal star decomposition of T .
Theorem 2.4. For all trees T , we have a(T ) = b(T ) = m(T ).
We know that a(G) ≤ b(G) for all graphs G, and b(T ) ≤ m(T ) for all trees T . See Belkhechine et al. [3] for details.
The proof of Theorem 2.4 will depend on the following propositions.
Definition 2.5. A cherry in a tree T is a maximal subtree S isomorphic to K1,m for some m > 1 that contains m end
vertices of T . We refer to a cherry with m edges as an m-cherry.
Proposition 2.6. Let T ∶= (V, E) be a tree that contains a cherry. If all proper subtrees T ′ of T satisfy a(T ′ ) = m(T ′ ),
then a(T ) = m(T ).
Proof. Let x ∈ V be the center of a k-cherry in T , with NT (x) = {u1 , . . . , uk , w1 , . . . , w` }, where d(ui ) = 1 for all i,
and d(wi ) > 1 for all i. Here d(x) denotes the degree of vertex x. For each i = 1 to `, let Ti be the maximal subtree that
contains wi but does not contain x.
First, we show that any optimal star decomposition of T in which x is not the center of a star can be transformed into an
optimal star decomposition in which x is the center of a star. Consider an optimal star decomposition ⌃ in which x is
not the center of a star. Therefore, edges xui are trivial stars of ⌃. Now if k > 2 or if there is a trivial star xwi in ⌃,
then we could have improved t(⌃) + 2s(⌃) by replacing all trivial stars containing x by their union, which is a star
centered at x. Hence, assume that k = 2 and each wi is the center of a nontrivial star Si , which contains the edge xwi .
Now replace each Si by Si′ ∶= Si − xwi , and add a new star centered at x with edge set {xw1 , . . . , xw` , xu1 , xu2 }. The
new decomposition is also optimal.
Now consider an optimal star decomposition ⌃ in which x is the center of a star. The induced decompositions on Ti
are all optimal since ⌃ is optimal. Let for each i ∈ {1, . . . , `}, let Ai be a maximum size independent set in Ti . Hence
�Ai � = a(Ti ) = m(Ti ) for all i, and m(T ) = 2 + ∑i m(Ti ) = 2 + ∑i a(Ti ). We show that A ∶= {x, u1 } ∪ (∪i Ai ) is a
maximum size independent set in T .
Consider a non-empty set B ⊆ A. We show that there exists v ∈ V such that �NT (v) ∩ B� is odd. If x ∈ B, then we take
v = u2 . If B = {u1 }, then we take v = x. In all other cases, Bi ∶= B ∩ Vi is non-empty for some i, and x ∈� B. We find
v ∈ Vi � Bi such that �NTi ∩ Bi � is odd. Now �NT (v) ∩ B� is odd since x ∈� B and v is not adjacent to u1 . Moreover,
�A� = m(T ).
Proposition 2.7. Let T ∶= (V, E) be a tree that contains a vertex y of degree 2 adjacent to a vertex z of degree 1. If
a(T − z) = m(T − z), then a(T ) = m(T ).
Proof. First, we show that m(T ) = m(T − z) + 1. If there is an optimal star decomposition of T − z − y in which x is
the center of a star, then m(t − z) = m(T − z − y) and m(T ) = m(T − z) + 1, else m(T − z) = m(T − z − y) + 1 and
m(T ) = m(T − z − y) + 2.
Now we consider a maximum size independent set A′ in T − z. We have �A′ � = a(T − z) = m(T − z). We define
A ∶= A′ ∪ {y} if y ∈� A′ ; and A ∶= A′ ∪ {z} if y ∈ A′ . We show that A is independent in T .
Case 1: y ∈� A′ , hence y ∈ A and z ∈� A. Let B ⊆ A, B ≠ �.
If y ∈ B, then �NT (z) ∩ B� is odd.
If y ∈� B, then B ⊆ A′ , hence there exists v ∈ V (T − z) such that �NT −z (v) ∩ B� is odd, and �NT (v) ∩ B� is odd.
Case 2: y ∈ A′ , hence z ∈ A. Let B ⊆ A, B ≠ �.
If z ∈� B, then B ⊆ A′ . Find v ∈ V (T − z) � B such that �NT −z (v) ∩ B� is odd. Hence �NT (v) ∩ B� is odd.
Now suppose that z ∈ B. If B = {z}, then NT (y) ∩ B is odd. Otherwise, consider (B � {z}), which is a subset of A′ .
Find v ∈ V (T − z) � (B � {z}) such that �NT −z (v) ∩ (B � {z})� is odd. If v ≠ y, then �NT (v) ∩ B� is odd. and x ∈ B.
In this case, let B ′ ∶= (B � {z}) ∪ {y}. This is a subset of A′ . Find u ∈ V (T − z) � B ′ such that �NT −z (u) ∩ B ′ � is odd.
Since B ′ contains x and y, we conclude that u is not adjacent to any of y and z, hence �NT (u) ∩ B� is odd.
Thus we have shown that A is independent. We have a(T ) ≥ �A� = �A′ � + 1 = m(T − z) + 1 = m(T ). Since a(T ) cannot
be more than m(T ), we have a(T ) = m(T ).
Proof of Theorem 2.4. If a tree T has 2 vertices, then a(T ) = m(T ) = 1. Each tree with at least 3 vertices contains a
cherry or a vertex of degree 2 adjacent to a vertex of degree 1. (This is seen by considering the second-to-last vertex of a
longest path in a tree.) Now induction on the number of vertices, using Propositions 2.6 and 2.7 implies the result.
Remark 2.8. Fallat and Hogben [4] consider the problem of minimum rank of graphs, and obtain a combinatorial
description for the minimum rank of trees. The connection between minimum rank and the binary dimension is made
clear in the next section for arbitrary graphs. Here we only state that in case of trees, the Boolean dimension, binary
dimension and the minimum rank coincide, thus the formula given above for the Boolean dimension gives yet another
combinatorial description for the minimum rank of a tree.
3 Binary and symplectic dimensions
A graph G is called reduced if it has no isolated vertices and no two vertices have the same neighbourhood. Our
definition is that from Godsil and Royle [6], where it is noted that there are slightly different definitions of ’reduced’ in
the literature.
Let A(G) denote the adjacency matrix of G. We denote the rank of a matrix M over F2 by rank2 (M ), and define
rank2 (G) ∶= rank2 (A(G)). Let Dn be the set of n × n matrices with non-diagonal entries 0 and diagonal entries 0 or 1.
Suppose that �V (G)� = n. We define mrank2 (G) ∶= min{rank2 (D + A(G)) � D ∈ Dn }. In the following propositions,
we relate the binary and symplectic dimensions of a graph G to its rank and mrank, respectively.
Proposition 3.1. Let G be a reduced graph on n vertices with adjacency matrix A(G). The symplectic dimension of G
is equal to rank2 (G).
Proof. The argument is essentially based on [6], where it is shown that there exists a symplectic representation in a
vector space over F2 of dimension r ∶= rank2 (G).
As shown in [6], it is possible to write
A(G) = � �,
M HT
H N
where the matrix M is the adjacency matrix of a reduced r-vertex graph of rank r, and H = RM , and N = RH T =
RM RT , which expresses the rows of the (n − r) × n matrix (H N ) as a linear combination of the rows of the r × n
matrix (M H T ). Rewriting, we have
A(G) = � � = � � M �I RT � ,
M M RT I
RM RM RT R
where the matrix I is the r × r identity matrix. Thus M determines a non-degenerate symplectic form on Fr2 given by
B(x, y) ∶= xT M y. Taking the columns of the r × n matrix (I RT ) as the vertices of G, we obtain a representation of
G in (Fr2 , B). Hence the symplectic dimension of G is at most r.
Now suppose that there is a symplectic representation of G in (Fk2 , B) for some symplectic form B on Fk2 . We show
that k ≥ r.
Writing (V (G)) ∶= {x1 , . . . , xn }, where x1 , . . . , xn are column vectors representing the vertices of G with respect to
the standard basis, we can write A(G) = X T M X, where M is the symmetric k × k matrix of the form B with respect
to the standard basis {e1 , . . . , ek } (i.e., Mij = B(ei , ej )), and X ∶= (x1 �xn ).
Now let X ∶= (P Q), where P is a k × k matrix (the first k columns of X) and Q is a k × (n − k) matrix (the last n − k
columns of X). Therefore,
A(G) = � T � M (P Q) = � T � (M P
PT PT
M Q) .
Q Q
Thus we have expressed the rows of A(G) as linear combinations of the rows of the k × n matrix (M P M Q), which
implies that k ≥ r.
Proposition 3.2. Let G be a reduced graph on n vertices with adjacency matrix A(G). The binary dimension of G is
equal to mrank2 (G).
Proof. The proof of this proposition is similar to that of Proposition 3.1.
Let D ∈ Dn . Suppose that the rank of D + A(G) = r. As in Proposition 3.1, we write
D + A(G) = � �,
M HT
H N
where the matrix M is a symmetric matrix of rank r (it is the adjacency matrix of a graph which possibly has loops
but no multiple edges), and H = RM , and N = RH T = RM RT , which expresses the rows of (H N ) as a linear
combination of the rows of (M H T ). Rewriting, we have
D + A(G) = � � = � � M �I RT � ,
M M RT I
RM RM RT R
where the matrix I is the r × r identity matrix. Thus M determines a non-degenerate bilinear form on Fr2 given by
B(x, y) ∶= xT M y. Taking the columns of (I RT ) as the vertices of G, we obtain a representation of G in (Fr2 , B).
Hence the binary dimension of G is at most r, which further implies that the binary dimension of G is at most
mrank2 (G) (by taking D that minimises rank2 (D + A(G))).
Next we show that the binary dimension is at least mrank2 (G).
Let B be a bilinear form on Fk2 , and suppose that there exists a representation of G in (Fk2 , B). We write (V (G)) ∶=
{x1 , . . . , xn }, where xi are column vectors with respect to the standard basis of Fk2 . Hence, for some D, we have
D + A(G) = X T M X, where M is the symmetric matrix of the bilinear form B. As in Proposition 3.1, we write
D + A(G) = � T � M (P Q) = � T � (M P
PT PT
M Q) ,
Q Q
where P and Q are obtained from X as before.
Thus we have expressed the rows of D + A(G) as linear combinations of the rows of the k × n matrix (M P M Q),
which implies that k ≥ rank2 (D + A(G)) ≥ mrank2 (G). Hence the binary dimension of G is at least mrank2 (G).
Acknowledgements
The third author would like to thank Institut Camille Jordan, Université Claude Bernard Lyon 1 for hospitality and
support. Support from CAPES Brazil (Processo: : 88887.364676/2019-00) and Labex MILYON: ANR-10-LABX-0070
are gratefully acknowledged.
References
[1] Houmen Belkhechine. Indécomposabilité des graphes et des tournois. Thèse de doctorat, Université de Sfax et
Université Claude-Bernard. 15 Juillet 2009.
[2] Houmen Belkhechine, Moncef Bouaziz, Imed Boudabbous and Maurice Pouzet. Inversion dans les tournois. C.R.
Acad. Sci. Paris, Ser. I 348 (2010) 703–707.
[3] Houmen Belkhechine, Moncef Bouaziz, Imed Boudabbous and Maurice Pouzet. Inversions in tournaments.
Unpublished manuscript, 2012.
[4] Shaun M Fallat and Leslie Hogben. The minimum rank of symmetric matrices described by a graph: a survey.
Linear Algebra and its Applications 426 (2007), no. 2-3, 558–582.
[5] Max H. Garzon. Symplectic embeddings of graphs. Journal of Combinatorial Mathematics and Combinatorial
Computing 2 (1987), 193–207.
[6] Chris D Godsil and Gordon F Royle. Chromatic number and the 2-rank of a graph. Journal of Combinatorial
Theory, Series B 81 (2001), no. 1, 142–149.
[7] Maurice Pouzet. Boolean dimension of a graph and inversions in tournaments, 2017, Slides of a talk to "40 Years
of Graphs and Algorithms". Workshop in honor of Michel Habib. October 10-12, 2018, Irit, Paris.