Difference Graphs

Authors: E. Boros, V. Gurvich and R. Meshulam

ABSTRACT

Intersection and measured intersection graphs are quite common in the literature. In this paper we introduce the analogous concept of measured difference graphs: Given an arbitrary hypergraph \$\cH = \{H_1,...,H_n\}\$, let us associate to it a graph on vertex set \$[n]=\{1,2,...,n\}\$ in which \$(i,j)\$ is an edge iff the corresponding sets \$H_i\$ and \$H_j\$ are ``sufficiently different''. More precisely, given an integer threshold \$k\$, we consider three definitions, according to which \$(i,j)\$ is an edge iff (1) \$|H_i \setminus H_j| + |H_j \setminus H_i| \geq 2k\$, (2) \$max\{|H_i \setminus H_j|,|H_j \setminus H_i|\} \geq k\$, and (3) \$min\{|H_i \setminus H_j|,|H_j \setminus H_i|\} \geq k\$. It is not difficult to see that each of the above define hereditary graph classes, which are monotone with respect to \$k\$. We show that for every graph \$G\$ there exists a large enough \$k\$ such that \$G\$ arises with any of the definitions above. We prove that with the first two definitions one may need \$k=\Omega(\log n)\$ in any such realizations of certain graphs on \$n\$ vertices. However, we do not know a graph \$G\$ which could not be realized by the last definition with \$k=2\$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-33.ps.gz