Drawing (graphs) by numbers: a minimality question - MathOverflow

Drawing (graphs) by numbers: a minimality question

2010-03-25T02:16:29Z

Every simple graph $G$ can be represented ("drawn") by numbers in the following way:

Assign to each vertex $v_i$ a number $n_i$ such that all $n_i$, $n_j$ are coprime whenever $i\neq j$. Let $V$ be the set of numbers thus assigned.
Assign to each maximal clique $C_j$ a unique prime number $p_j$ which is coprime to every number in $V$.
Assign to each vertex $v_i$ the product $N_i$ of its number $n_i$ and the prime numbers $p_k$ of the maximal cliques it belongs to.

Then $v_i$, $v_j$ are adjacent iff $N_i$ and $N_j$ are not coprime,

i.e. there is a (maximal) clique they both belong to. Edit: It's enough to assign $n_i = 1$ when $v_i$ is not isolated and does not share all of its cliques with another vertex.

Being free in assigning the numbers $n_i$ and $p_j$ lets arise a lot of possibilites, but also the following question:

QUESTION

Can the numbers be assigned systematically such that the greatest $N_i$ is minimal (among all that do the job) — and if so: how?

It is obvious that the $n_i$ in the first step have to be primes for the greatest $N_i$ to be minimal. I have taken the more general approach for other - partly answered - questions like "Can the numbers be assigned such that the set $\lbrace N_i \rbrace_{i=1,..,n}$ fulfills such-and-such conditions?"

Answer by Niel de Beaudrap for Drawing (graphs) by numbers: a minimality question

2010-03-25T16:14:23Z

I'm not sure this qualifies as an answer, but I hope these remarks are useful to you; they re-present your problem in a format which is likely to be answerable by experts in discrete optimization.

The abstract: I suspect the problem of computing the smallest maximum N_j is intractible, and suggest approaches to obtaining upper and lower bounds for N_j . I also make brief remarks about the case of low clique number.

Reformulation

Let K be the set of maximal cliques C_j , and consider the bipartite graph graph H with vertex-set V(G) ∪ K, and adjacency defined by $$ v~C_j \;\in\; E(H) \;\;\;\iff\;\;\;\; v \in C_j \;.$$ Your weighting scheme then amounts to a weighting of the vertices of H by (co-)prime integers. Instead of considering products of such (co-)prime integers, we may consider the sum of their logarithms. So:

weight the vertices of H with real numbers ω(v) = ln(p) for distinct primes p;
define the "weight" Ω(v) of a neighborhood of a vertex v as the sum of ω(x) for x ranging over v and its neighbors. For vertices v ∈ V(G), its neighbors are the maximal cliques C_j to which it belongs in G; for vertices C ∈ K, its neighbors are all of the vertices in G which C contains.

We are interesting in minimizing $$\large \Omega(G) \equiv \max_{v \in V(G)} \Omega(v)$$ for v ∈ V(G) subject to the above definitions/constraints. The minimum N_j which you describe above is then e^Ω(G).

Now, the weights ω(v) for v ∈ V(H) form a vector of logarithms of primes. There's no reason to take any coefficient to be larger than ln(p_h), where h = |V(H)| and p_h is the h^th prime. So we may as well fix the column vector p = ( ln 2, ln 3, ... , ln p_h )^T, and describe the weight function ω in terms of permutations of the coefficients of this vector. So really, we would like to obtain $$ \Omega^\ast(G) \;\;=\; \large \min_{\Pi \in \mathfrak S_h} \;\max_{v \in V(G)} \big(\mathbf{e}_v^\top A(H) \: \Pi \;\mathbf{p} \big)$$ where A(H) is the adjacency matrix of H, and $\mathfrak S_h$ is the group of permutation matrices on ℝ^h.

Remarks on the reformulation

Evaluating Ω*(G) is likely to be difficult, as in computationally intractible. (Disclaimer: I am not an expert on such problems, and I have not given this instance a lot of thought; but some similar problems are NP complete.) A better question is whether you can get "nice" upper or lower bounds for Ω*(G).

You can obtain a lower bound for Ω*(G) by taking a convex relaxation. For instance, instead of optimizing over $\mathfrak S_h$, oprimize over the convex closure of that set, which is the set of doubly-stochatic matrices over ℝ^h. You can then exploit the fact that the maximum is the uniform norm of the [restriction to ℝ^V(G) of the] vector ω(H) = A(H) Π p ; as such, it is a convex function (as the uniform norm satisfies the triangle inequality). It should be possible to optimize this function efficiently using steepest descent techniques.
Obviously, you're more interested in upper bounds for Ω*(G). The function f(x) = ln(p_x) grows asymptotically like ln(x) + ln(ln x); therefore, the contribution of a large log-prime weight to some sum Ω(v) is not much different than the contribution of a slightly larger log-prime weight. Optimizing the location of the larger primes among themselves is then unlikely to be useful; in practise it is more useful to optimize the location of the smaller primes.
The weights of the clique-vertices C_j contribute to many different neighborhood weights Ω(v). This suggests that a reasonable approach is to allocate the smallest log-prime weights to cliques according (roughly) to the number of vertices they contain. Obviously this will fail if there is a very large clique which "interacts" with very few other cliques (i.e. shares vertices in common with few other cliques), and there exists elsewhere a large congregation of cliques which each share something like half of their elements with other cliques (i.e. for a large subset S of V(G), each vertex in S belongs to approximately half of a large collection of cliques). It may be worthwhile to investigate the graph of incidence of maximal cliques.

A final remark: in the case of a bipartite graph, the maximal cliques are all edges, in which case the graph H is just a subdivision of G. In this case, attributing weights to the vertices v ∈ V(G) does not aid in the representation of the graph. For graphs with low clique number, it may be worthwhile to investigate a similar scheme where only the edges or maximal cliques are given weights, or more generally where almost every vertex is given weight 1.

Answer by Niel de Beaudrap for Drawing (graphs) by numbers: a minimality question

2010-03-26T10:47:27Z

As an alternative to my earlier computational answer for particular graphs G, here is a worst-case description of the asymptotic growth of the minimum size of the integers N_j

Let h be the sum of |V(G)| and the number of maximal cliques in G (bounded above by |E(G)|, which is saturated for bipartite graphs, whose edges are the maximal cliques). Let c be the maximum number of maximal cliques to which a vertex v ∈ V(G) may belong. Because p_h ≤ h (ln(h) + ln ln(h)), we can bound $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(h^c \log^c(h)\Big). $$ This bound is asymptotically saturated by placing the largest prime weights on the vertex in the largest number of maximal cliques, and those maximal cliques of which it is a part, which is obviously a bad thing to do. But e.g. in Cayley graphs G, every vertex belongs to the same number of maximal cliques, this asymptotic growth cannot be avoided, as there will exist vertices v for which N_v will consist exclusively of a product of primes p_t, for t bounded below by a constant fraction of h.

One can construct bipartite Cayley graphs in which the degree of each vertex is a constant fraction of n = |V(G)|. We then have h = α n for some 0 < α < 1; and h = |V(G)| + |E(G)| ∈ O(n²), so that $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(n^{2\alpha n} \log^{\alpha n}(n)\Big) $$ for such graphs. Thus there exist graphs for which the coefficients N_j grow much more quickly than e.g. the factorial function.