From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that have no letters in common. For the occasion, we'll call such a graph a subset graph (knowing that usually the term is used in a different sense).
Special cases would be the Kneser graphs, where $V$ is the complete set of $k$-subsets. Obviously any finite simple graph can be realized as a subset graph if only we make $N$ big enough, maybe even $N>n$. So it makes sense to define for a given graph $G$ its "lexicalicity" $\ell(G)$ as the smallest possible such $N$. I am not sure whether it is useful to also define the "subset cardinality" $sc(G)$ as the smallest possible $k$ in such a construction, as that might be at the expense of $N$ becoming much bigger than $\ell(G)$, which would (intuitively) make the structure less interesting. Question:
- Are there classes of graphs for which a construction featuring $\ell(G)$ also features $sc(G)$?
I am only interested in regular graphs here and guess anyway that the higher the "symmetry" of $G$, the smaller $\ell(G)$ and $sc(G)$.
The idea is in fact inspired by the construction mentioned here. I am probably not the first person thinking about that, so I'll ask first what is known about $\ell(G)$. In particular:
What about $\ell(G)$ if $G$ is the complement of a Kneser graph?
For a strongly regular graph $G$, is $\ell(G)$ bounded in terms of its parameters? (Or can it even be derived from the parameters?)
