Some lower bounds for the $L$-intersection number of graphs

Abstract

‎For a set of non-negative integers~$L$‎, ‎the $L$-intersection number of a graph is the smallest number~$l$ for which there is an assignment of subsets $A_v subseteq {1,dots‎, ‎l}$ to vertices $v$‎, ‎such that every two vertices $u,v$ are adjacent if and only if $|A_u cap A_v|in L$‎. ‎The bipartite $L$-intersection number is defined similarly when the conditions are considered only for the vertices in different parts‎. ‎In this paper‎, ‎some lower bounds for the (bipartite) $L$-intersection number of a graph for various types $L$ in terms of the minimum rank of graph are obtained‎. ‎To achieve the main results we employ the inclusion matrices of set systems and show that how the linear algebra techniques give elegant proof and stronger results in some cases.