Abstract

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. x y ∶= x1y1 + ⋅ ⋅ ⋅ + xkyk. ∗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).

Keywords

• Graphs ⋅ Tournaments

-

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 F2k, 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 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 ≠ such that S ≠ . Suppose that for all A ⊆ S, A ≠ {f (x) x ∈ A} is linearly independent.

This suggests the following definition.

. Let f ∶ V → F2m be a boolean representation of G. Let S ⊆ V , there exists v ∈ V A such that N (v) ∩ A is odd. Then 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} ∪ (∪iAi) 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

M A(G) = H

HT N , where the matrix M is the adjacency matrix of a reduced r-vertex graph of rank r, and H = RM , and N = RHT = 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 HT ). Rewriting, we have

A(G) =

M RM

M RT I RM RT = R

M I

RT , 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 r G in (F2, B). Hence the symplectic dimension of G is at most r.

Now suppose that there is a symplectic representation 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) = XT 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,

of G in (F2k, B) for some symplectic form B on F2k. We show P T

QT A(G) =

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

M D + A(G) = H

HT 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 = RHT = RM RT , which expresses the rows of (H N ) as a linear combination of the rows of (M HT ). Rewriting, we have 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 F2k, and suppose that there exists a representation of G in (F2k, B). We write (V (G)) ∶= k {x1, . . . , xn}, where xi are column vectors with respect to the standard basis of F2 . Hence, for some D, we have D + A(G) = XT M X, where M is the symmetric matrix of the bilinear form B. As in Proposition 3.1, we write P T

QT

M 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.