Difference graphs Original Research Article

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={H1,…,Hn}, 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 Hi and Hj are “sufficiently different”. More precisely, given an integer threshold k, we consider three definitions, according to which (i,j) is an edge iff (1) |Hi⧹Hj|+|Hj⧹Hi|⩾2k, (2) max{|Hi⧹Hj|,|Hj⧹Hi|}⩾k, and (3) min{|Hi⧹Hj|,|Hj⧹Hi|}⩾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.