Journal of Combinatorics

Volume 11 (2020)

Number 4

Rank of incidence matrix with applications to digraph reconstruction

Pages: 657 – 679

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n4.a5

Authors

Aymen Ben Amira (Department of Mathematics, College of Sciences, King Saud University, Riyadh, Saudi Arabia; and Department of Mathematics, Faculty of Sciences, University of Sfax, Tunisia)

Jamel Dammak (Department of Mathematics, Faculty of Sciences, University of Sfax, Tunisia)

Abstract

The incidence matrix $W_{t \, k}$ is defined as follow: Let $V$ be a finite set, with $v$ elements. Given non-negative integers $t, k, W_{t \, k}$ is the $\binom{v}{t}$ by $\binom{v}{k}$ matrix of $0$’s and $1$’s, the rows of which are indexed by the $t$-element subsets $T$ of $V$, the columns are indexed by the $k$-element subsets $K$ of $V$, and where the entry $W_{t \, k}(T,K)$ is $1$ if $T \subseteq K$ and is $0$ otherwise.

R.M. Wilson proved that for $t\leq \min (k, v-k)$, the rank of $W_{t \, k}$ modulo a prime $p$ is $\sum{t}{i=0} \binom{v}{i} - \binom{v}{i-1}$ where $p$ does not divide the binomial coefficient $\binom{k-i}{t-i}$.

In this paper, we begin by giving an analytic expression of the rank of the matrix $W_{t \, k}$ when $t = t_0 + t_1 p + t_2 p^2$, with $t_0, t_1, t_2 \in [0, p - 1]$ and we characterize values of $t$ and $k$ such that $\operatorname{dim} Ker({}^t W_{t \, k}) \in \lbrace 0 , 1 \rbrace$. Next, using this result we generalize a result in the $(\leq 6)$-reconstruction of digraphs due to G. Lopez.

Keywords

digraph, isomorphism, $\lbrace k \rbrace$-hypomorphic, graph, incidence matrix

2010 Mathematics Subject Classification

05C50, 05C60

Received 22 December 2016

Accepted 23 November 2019

Published 9 October 2020