DIMACS TR: 2000-33

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
DIMACS Home Page