\input zb-basic
\input zb-ioport
\iteman{io-port 02041895}
\itemau{Boros, Endre; Gurvich, Vladimir; Meshulam, Roy}
\itemti{Difference graphs.}
\itemso{Discrete Math. 276, No.1-3, 59-64 (2004).}
\itemab
Summary: 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 $\cal H=\{ H_1,\dots ,H_n\}$, let us associate to it a graph on vertex set $[n]=\{1,2,\dots ,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 if and only if (1) $|H_i \setminus H_j|+|H_j \setminus H_i|\geqslant 2k$, (2) $\max\{|H_i \setminus H_j|,|H_j \setminus H_i|\} \geqslant k$, and (3) $\min\{|H_i \setminus H_j|,|H_j \setminus H_i|\} \geqslant k$. It is not difficult to see that each of the above defines 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$.
\itemrv{~}
\itemcc{}
\itemut{Graph realization; Intersection graphs; Difference graphs}
\itemli{doi:10.1016/S0012-365X(03)00321-2}
\end