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