Originators: Endre Boros, Vladimir Gurvich, Roy Meshulam (presented by Amanda Olsen - REGS 2010)
Definitions: From sets S1,…,Sn, we define a graph with vertex set v1,…,vn. We consider several models for forming this graph, using a parameter k and a function ρ of two variables. The function ρ may be "average", "max", or "min", where avg(a,b) = (a+b)/2. In the (ρ,k)-model, we make vi adjacent to vj if and only if ρ( |Si-Sj | , |Sj-Si | ) ≥ k. We say that a graph G is (ρ,k)-realizable if there is a family of sets that produces (a graph isomorphic to) G under the (ρ,k)-model. In that case, the sets corresponding to the vertices are viewed as "labels".
Background: When k=2 and the labels all have size 2, the functions avg, max, and min always agree, so the three models generate the same graphs from the labels. Because the three models are equivalent, when k=2 and the labels all have size 2 we simply use 2-realizable instead of (ρ,2)-realizable.
In this case, the vertices for two labels are adjacent if and only if the labels are disjoint. Thus the notion of 2-realizable graphs generalizes the Kneser graph K(n,2), which is the disjointness graph for the family of 2-element subsets of [n]. Disjointness graphs are well studied, and there are natural parameters measuring the difficulty of representing a graph as a disjointness graph. For example, the Kneser index of a graph G is the least r such that G can be obtained as a disjointness graph of r-sets. Instead, we study the (ρ,k)-model when k and the label sizes are not both 2. Note that (ρ,k)-realizability is preserved by taking induced subgraphs, since adjacency of two vertices depends only on the labels assigned to those two vertices.
Problem 1: For a fixed label size r, determine the minimal forbidden induced subgraphs for the family of (ρ,k)-realizable graphs representable using labels of size r.
Comments: Special cases are of interest. Perhaps the problem is simpler when k=r or when k=2 or for a particular choice of ρ. There is also the possibility of allowing the sizes of the labels to vary, as in the question below:
Question 2 [BGM]: Is every graph (min,2)-realizable?
Comments: When the labels all have size 2, they can be viewed as edges in a multigraph (repeated labels are allowed), and then the graph generated is the complement of that multigraph. Thus the family of 2-realizable graphs is the family of complements of line graphs of multigraphs.
References:
[BGM] E. Boros, V. Gurvich, R. Meshulam, Difference Graphs, Discrete
Mathematics (2004) 59 - 64).