(Non)uniqueness of the common-factor graph

Question

Let $S=\{x_1,\ldots,x_k\}$ be a set of $k$ distinct natural numbers, a subset of $\{1,\ldots,n\} = \mathbb{N}_{\le n}$. Define the common-factor graph $G(S)$ as the (undirected) graph with a node for each $x_i$, and an arc between $x_i$ and $x_j$ if they share a common factor: $\operatorname{gcd}(x_i,x_j) > 1$. I'm interested in the degree to which an unlabeled common-factor graph $G$ determines $S$.

Here are two examples:

---

         
          ^{$n=100$, $k=10$, $S=\{2,5,16,25,67,69,70,76,82,99\}$.}

---

         
          ^{$n=100$, $k=10$, $S=\{3,21,24,40,59,65,83,86,94,98\}$.}

---

Q1. Is every simple graph $G$ the common-factor graph of some $S$?

I am not seeing obvious obstructions.

Q2. Given $G$ and $n$, how can one find a set $S$ such that $G=G(S)$, or report there is no such $S \subseteq \mathbb{N}_{\le n}$?

Of course it would be nice to have an algorithm that is faster than trying all possible $\binom{n}{k}$ subsets $S$.

This is one formulation of a uniqueness question; I doubt it is the most perspicacious.

Q3. If $S$ is a random $k$-subset of $\mathbb{N}_{\le n}$, given $G=G(S)$, what is the expected number of distinct $S$ that also realize $G$, perhaps as function of $\mu=k/n$ (where $k=|S|$)?

For small $\mu$, there will be many $S$, and for $\mu=1$, $S=\mathbb{N}_{\le n}$ is determined.

Added. Not the best example, but here are two sets $S_1$ and $S_2$ that yield isomorphic common-factor graphs:

---

         
          ^{$S_1=\{1,\ldots,16\} \setminus \{6\}$, $S_2=\{1,\ldots,16\} \setminus \{12\}$. $S_1 \equiv S_2$.}

---

Answer 1

The answer to Q1 is yes. We proceed by induction on $|E(G)|$. For the base case, assign distinct primes to each vertex.

For the inductive step, choose a non-isolated vertex $v$. By induction, $G-v$ is the common-factor graph of some set of numbers $S$. Let $v_1, \dots, v_\ell$ be the neighbours of $v$ in $G$, and suppose that these vertices correspond to $x_1, \dots, x_\ell$ in $S$. Choose primes $p_1, \dots, p_\ell$ such that $p_i$ does not divide any member of $S$. We get a representation of $G$ by replacing each $x_i$ with $p_ix_i$ and representing $v$ by $p_1p_2 \cdots p_\ell$.

Answer 2

A small change to Tony Huynh's proof gives a reasonably efficient algorithm for Q2.

Label the nodes as 1 through $k$. Select $2k$ distinct primes, listed as $p_1,...,p_k$ and $q_1,...,q_k$.

Let $s_i$ equal the product of $p_iq_i$ and $\Pi_{j\in T_i}p_i$, where $T_i$ is the set of neighboring vertex labels to $i$.

(By the way, we are using the $q_i$ to ensure that the $s_i$ are all distinct, in the situation that two nodes are neighbors and also share all the same neighbors.)

Answer 3

If your n is small and you still seek solutions to finding a set S which yields a gcd graph, clique labelling is a good way to start.

Pick a set of relatively prime integers (labels) $e_i$, so that each edge gets at least one label. Now you can assign a different label to each edge, and then at each vertex multiply the numbers on the incident edges, and you have your graph representation. If two edges get the same label, then all the vertices involved have a common factor e greater than 1, so these vertices must be part of a clique contained in the graph. (In the event this results in two or more vertices getting the same number, you can use the suggestion of Bill Bradley and multiply the number at one vertex further by $f_j$ coprime to every $e_i$ and $f_i$ being used.)

Now one can organize the graph into maximal cliques (possibly sharing edges) and assign the same number to all edges of a clique, as long as no two maximal cliques get the same number (and if two non maximal cliques do get the same number, they need to be merged into a larger clique to keep things tidy.) So if a graph G is given a clique cover C such that G is (edgewise) the union of the members of C, one now reduces the number of the set of integer labels needed to the number of (irredundant) cliques in C, with edges getting multiple distinct labels depending on which cliques in C share edges. (For distinctness, one may need to add to this number the size of D, the set of distinct $f_j$ being used.)

Not that it leads to a faster algorithm, but if you are in a position where you can rapidly estimate the size of a minimal clique cover, you can now translate your other problems to counting subsets of coprime numbers less than n, for which there are references on MathOverflow.

Gerhard "These Problems Form Nice Groupings" Paseman, 2018.05.14.

Answer 4

This is a start at rephrasing and answering Joseph's Q3. My interpretation is that he wants to know how to split the set of size k subsets of n into equivalence classes such that two such k-sets S and T are equivalent iff their gcd graphs are the same.

Starting small, all such 1-sets are equivalent, and for k=2 we can look at the divisibility lattice up to n to count which pairs are coprime and which pairs share a common factor. As n gets larger, more pairs will be coprime, so about ($6/\pi^2$) fraction will have no edge.

One can continue in this way for k up to before about O(log n), when the number of graph classes start to outnumber the number of distinct subsets. The distribution for small k and large n may be of interest. We can record that the complete graph on k vertices can be realized with the first k even numbers. If one tries a different set (say one vertex e is not even), one has to find different primes in common with enough other vertices that the label starts to grow past 2k. As an example, even if k-1 are multiples of 3 and a different k-1 many are even, you still need roughly values up to about 6k to distinguish the remaining vertices, as well as a prime bigger than 3 to connect the odd vertex with the other vertex not a multiple of 6.

Some graphs are easy to analyze. A complete graph on k vertices is achievable for k up to n/2, while the complement graph with no edges stops being realized after k exceeds $\pi(n)$. For many graphs that are realizable, switching two labels can yield in a different realization. It is hard to know for which k one starts seeing unique graphs (as in a recent problem of Bernardo Recaman), but a good guess is about the time one runs out of subsets to express a graph of k vertices, which is O(log n).

For k near n, one usually has v many independent vertices where v is often near $\pi(n) - \pi(n/2)$. When $v$ is strictly less than that number, one has two different realizations for the graph by switching one prime labelling a vertex for an unused prime label. I rashly conjecture that there is a constant c (with c not far from 1) so that the probability that a given set S is in an equivalence class with a different set T to be 1- O(exp(-cn)).

Edit 2018.05.15.

As observed in a comment below, if j and k are distinct integers less than n with rad(j) = rad(k), then any set S which has j and not k will have the same gcd graph as S union {k} takeaway {j}. Thus any set S of integers less of n cannot have a unique gcd graph unless for every j in S, k at most n and rad(k)=rad(j) implies k is also in S.

Further, 1 and primes p larger than n/2 will be isolated points if they are in the graph of S, so for S to have a unique graph means all or none of these numbers must be in the graph. More generally, let p be a large prime (with $p^2$ greater than n) and j the largest integer with jp less than n, and let q be any other prime in (n/(j+1), n/j). One can swap kq and kp in the graph, for all k from 1 up to j, and this will preserve S only if we have [kp in S iff kq in S]. In particular, for all primes p in (n/3, n/2), we either have all of 2p in S or none of 2p in S. So the conditions on S to have a gcd graph unique among all subsets of the first n numbers is getting rather strong.

End Edit 2018.05.15.

Gerhard "A Subset Of Semi-random Musings" Paseman, 2018.05.14.