Difference graphs

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_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|≥2k, (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 = Ω(logn) 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.