5
$\begingroup$

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

  1. 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.

  2. Assign to each maximal clique $C_j$ a unique prime number $p_j$ which is coprime to every number in $V$.

  3. 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?"

$\endgroup$
1
  • 2
    $\begingroup$ Since you're only using multiplicative properties of integers, and coprimeness, you're really just assigning sets of integers to the vertices and cliques, and coprimeness translates into disjointness. As far as the minimality, you're assigning weights of $\log p_i$ to the integer $i$, where $p_i$ is the $i$-th prime. $\endgroup$ Mar 25, 2010 at 14:30

2 Answers 2

3
$\begingroup$

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 Nj is intractible, and suggest approaches to obtaining upper and lower bounds for Nj . I also make brief remarks about the case of low clique number.

Reformulation

Let K be the set of maximal cliques Cj , 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 vV(G), its neighbors are the maximal cliques Cj to which it belongs in G; for vertices CK, 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 vV(G) subject to the above definitions/constraints. The minimum Nj which you describe above is then eΩ(G).

Now, the weights ω(v) for vV(H) form a vector of logarithms of primes. There's no reason to take any coefficient to be larger than ln(ph), where h = |V(H)| and ph is the hth prime. So we may as well fix the column vector p = ( ln 2, ln 3, ... , ln ph )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(px) 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 Cj 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 vV(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.

$\endgroup$
2
  • $\begingroup$ Thanks! I didn't think of "discrete optimization" but that's what my question seems to be about. (You are providing so many details, it's hard for me to follow.) $\endgroup$ Mar 25, 2010 at 18:01
  • $\begingroup$ Sorry (?). For whatever reason, I often find it difficult to give impressionist depictions of mathematical ideas. $\endgroup$ Mar 26, 2010 at 9:27
3
$\begingroup$

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 Nj 

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 vV(G) may belong. Because phh (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 Nv will consist exclusively of a product of primes pt, 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(n2), 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 Nj grow much more quickly than e.g. the factorial function.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.