1
$\begingroup$

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?)

$\endgroup$
4
  • $\begingroup$ In a $d$-regular graph $G$, you can use $E(G)$ as the alphabet to demonstrate that $sc(G) \leq d$ and $\ell(G) \leq |E(G)|$. I think both bounds are tight if $G$ is triangle-free. $\endgroup$
    – D. Ror.
    Feb 24, 2017 at 16:11
  • $\begingroup$ @DannyRorabaugh You can do a cube graph with 8 letters: 123 - 456 - 457 - 458 -126 - 127 - 128 - 345. So at least here $\ell(G) \leq |V(G)|$. $\endgroup$
    – Wolfgang
    Feb 24, 2017 at 16:50
  • $\begingroup$ Oops, I was thinking of connecting subsets that DO have a letter in common. Never mind. $\endgroup$
    – D. Ror.
    Feb 24, 2017 at 17:18
  • $\begingroup$ The case @DannyRorabaugh mentioned is known as the intersection number. There is also another related problem, where there is an edge iff the corresponding sets overlap (i.e., intersect but are not strictly contained in each other). $\endgroup$ Mar 23, 2017 at 12:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.