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

Document Type : Research Paper

Authors

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

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.

Keywords

Main Subjects

References

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.
Bulletin of the Iranian Mathematical Society
Volume 43, Issue 1
February 2017
Pages 69-78

Files

History

  • Receive Date: 11 January 2015
  • Revise Date: 10 October 2015
  • Accept Date: 10 October 2015

Share

How to cite

Statistics