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
H={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
⧹
H
j
|+|
H
j
⧹
H
i
|⩾2
k, (2) max{|
H
i
⧹
H
j
|,|
H
j
⧹
H
i
|}⩾
k, and (3) min{|
H
i
⧹
H
j
|,|
H
j
⧹
H
i
|}⩾
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=
Ω(
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.