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

Document Type : Research Paper


1 Department of Mathematical Sciences‎, ‎Isfahan University of Technology‎, ‎84156-83111‎, ‎Isfahan‎, ‎Iran.

2 Department of Mathematical Sciences, Isfahan University of Technology, 84156-83111, Isfahan, Iran


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


Main Subjects

N. Eaton, Some results in graph Ramsey theory and graph representations, PhD Thesis, Emory University, 1992.
N. Eaton, Intersection representation of complete unbalanced bipartite graphs, J. Combin. Theory Ser. B 71 (1997), no. 2, 123--129.
N. Eaton, R. J. Gould, and V. Rodl, On p-intersection representations, J. Graph Theory 21 (1996), no. 4, 377--392.
N. Eaton and D. A. Grable, Set intersection representations for almost all graphs, J. Graph Theory 23 (1996), no. 3, 309--320.
N. Eaton and V. Rodl, Graphs of small dimensions, Combinatorica 16 (1996), no. 1, 59--85.
P. Frankl and L. Babai, Linear algebra methods in combinatorics, preliminary version 2, Department of Computer Science, University of Chicago, 1992.
M. S. Jacobson, A. E. Kezdy, and D. B. West, The 2-intersection number of paths and bounded-degree trees, J. Graph Theory 19 (1995), no. 4, 461--469.
S. Jukna, On set intersection representations of graphs, J. Graph Theory 61 (2009), no. 1, 55--75.
S. Jukna and A. S. Kulikov, On covering graphs by complete bipartite subgraphs, Discrete Math. 309 (2009), no. 10, 3399--3403.
L. Lovasz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1--7.
L. Lovasz and K. Vesztergombi, Geometric representations of graphs, in: Paul Erdos and his mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud. 11, pp. 471--498, Janos Bolyai Math. Soc. Budapest, 2002.
T. D. Parsons and T. Pisanski, Vector representations of graphs, Discrete Math. 78 (1989), no. 1--2, 143--154.
S. Parter, On the eigenvalues and eigenvectors of a class of matrices, SIAM J. Appl. Math. 8 (1960) 376--388.
P. Pudlak and V. Rodl, A combinatorial approach to complexity, Combinatorica 12 (1992), no. 2, 221--226.
A. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1990), no. 1, 81--93.