Drawing (graphs) by numbers: a minimality question - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:06:16Z http://mathoverflow.net/feeds/question/19261 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19261/drawing-graphs-by-numbers-a-minimality-question Drawing (graphs) by numbers: a minimality question Hans Stricker 2010-03-25T02:16:29Z 2010-03-26T13:31:00Z <p>Every simple graph $G$ can be represented ("drawn") by numbers in the following way:</p> <ol> <li><p>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. <br/></p></li> <li><p>Assign to each maximal clique $C_j$ a unique prime number $p_j$ which is coprime to every number in $V$.</p></li> <li><p>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.</p></li> </ol> <blockquote> <p>Then $v_i$, $v_j$ are adjacent iff $N_i$ and $N_j$ are not coprime,</p> </blockquote> <p>i.e. there is a (maximal) clique they both belong to. <strong>Edit:</strong> 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.</p> <p>Being free in assigning the numbers $n_i$ and $p_j$ lets arise a lot of possibilites, but also the following question:</p> <blockquote> <p><strong>QUESTION</strong></p> <p>Can the numbers be assigned <em>systematically</em> such that the greatest $N_i$ is minimal (among all that do the job) &#x2014; and if so: how?</p> </blockquote> <p>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 <a href="http://mathoverflow.net/questions/19076/bringing-number-and-graph-theory-together-a-conjecture-on-prime-numbers/19080#19080" rel="nofollow">answered </a> - questions like "Can the numbers be assigned such that the set $\lbrace N_i \rbrace_{i=1,..,n}$ fulfills such-and-such conditions?"</p> http://mathoverflow.net/questions/19261/drawing-graphs-by-numbers-a-minimality-question/19324#19324 Answer by Niel de Beaudrap for Drawing (graphs) by numbers: a minimality question Niel de Beaudrap 2010-03-25T16:14:23Z 2010-03-25T16:14:23Z <p>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.</p> <p>The abstract: I suspect the problem of computing the smallest maximum <em>N<sub>j</sub></em> is intractible, and suggest approaches to obtaining upper and lower bounds for <em>N<sub>j</sub></em>&nbsp;. I also make brief remarks about the case of low clique number.</p> <h3>Reformulation</h3> <p>Let <em>K</em> be the set of maximal cliques <em>C<sub>j</sub></em>&nbsp;, and consider the bipartite graph graph <em>H</em> with vertex-set <em>V(G)</em> &cup; <em>K</em>, 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 <em>H</em> by (co-)prime integers. Instead of considering products of such (co-)prime integers, we may consider the sum of their logarithms. So:</p> <ul> <li>weight the vertices of <em>H</em> with real numbers &omega;(<em>v</em>) = ln(<em>p</em>) for distinct primes <em>p</em>;</li> <li>define the "weight" &Omega;(<em>v</em>) of a neighborhood of a vertex <em>v</em> as the sum of &omega;(<em>x</em>) for <em>x</em> ranging over <em>v</em> and its neighbors. For vertices <em>v</em> &isin; <em>V(G)</em>, its neighbors are the maximal cliques <em>C<sub>j</sub></em> to which it belongs in <em>G</em>; for vertices <em>C</em> &isin; <em>K</em>, its neighbors are all of the vertices in <em>G</em> which <em>C</em> contains.</li> </ul> <p>We are interesting in minimizing $$\large \Omega(G) \equiv \max_{v \in V(G)} \Omega(v)$$ for <em>v</em> &isin; <em>V(G)</em> subject to the above definitions/constraints. The minimum <em>N<sub>j</sub></em> which you describe above is then e<sup>&Omega;(<em>G</em>)</sup>.</p> <p>Now, the weights &omega;(<em>v</em>) for <em>v</em> &isin; <em>V(H)</em> form a vector of logarithms of primes. There's no reason to take any coefficient to be larger than ln(<em>p<sub>h</sub></em>), where <em>h</em> = |<em>V(H)</em>| and <em>p<sub>h</sub></em> is the <em>h</em><sup>th</sup> prime. So we may as well fix the column vector <strong>p</strong> = ( ln 2, ln 3, ...&nbsp;, ln <em>p<sub>h</sub></em> )<sup>T</sup>, and describe the weight function &omega; 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(<em>H</em>) is the adjacency matrix of <em>H</em>, and $\mathfrak S_h$ is the group of permutation matrices on &#8477;<sup><em>h</em></sup>.</p> <h3>Remarks on the reformulation</h3> <p>Evaluating &Omega;*(<em>G</em>) 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 <strong>NP</strong> complete.) A better question is whether you can get "nice" upper or lower bounds for &Omega;*(<em>G</em>).</p> <ul> <li><p>You can obtain a lower bound for &Omega;*(<em>G</em>) 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 &#8477;<sup><em>h</em></sup>. You can then exploit the fact that the maximum is the <em>uniform norm</em> of the [restriction to &#8477;<sup><em>V(G)</em></sup> of the] vector &omega;(<em>H</em>) = A(<em>H</em>) &Pi; <strong>p</strong>&nbsp;; 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.</p></li> <li><p>Obviously, you're more interested in upper bounds for &Omega;*(<em>G</em>). The function <em>f(x)</em> = ln(<em>p<sub>x</sub></em>) grows asymptotically like ln(<em>x</em>) + ln(ln <em>x</em>); therefore, the contribution of a large log-prime weight to some sum &Omega;(<em>v</em>) 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.<p> The weights of the clique-vertices <em>C<sub>j</sub></em> contribute to many different neighborhood weights &Omega;(<em>v</em>). 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 (<em>i.e.</em> 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 (<em>i.e.</em> for a large subset <em>S</em> of <em>V(G)</em>, each vertex in <em>S</em> belongs to approximately half of a large collection of cliques). It may be worthwhile to investigate the graph of incidence of maximal cliques.</p></li> </ul> <p>A final remark: in the case of a bipartite graph, the maximal cliques are all edges, in which case the graph <em>H</em> is just a subdivision of <em>G</em>. In this case, attributing weights to the vertices <em>v</em> &isin; <em>V(G)</em> 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.</p> http://mathoverflow.net/questions/19261/drawing-graphs-by-numbers-a-minimality-question/19403#19403 Answer by Niel de Beaudrap for Drawing (graphs) by numbers: a minimality question Niel de Beaudrap 2010-03-26T10:47:27Z 2010-03-26T13:31:00Z <p>As an alternative to my earlier computational answer for particular graphs <em>G</em>, here is a worst-case description of the asymptotic growth of the minimum size of the integers <em>N<sub>j</sub></em>&nbsp;</p> <p>Let <em>h</em> be the sum of |<em>V(G)</em>| and the number of maximal cliques in <em>G</em> (bounded above by |<em>E(G)</em>|, which is saturated for bipartite graphs, whose edges are the maximal cliques). Let <em>c</em> be the maximum number of maximal cliques to which a vertex <em>v</em> &isin; <em>V(G)</em> may belong. Because <em>p<sub>h</sub></em> &le; <em>h</em> (ln(<em>h</em>) + ln ln(<em>h</em>)), 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 <em>e.g.</em> in Cayley graphs <em>G</em>, every vertex belongs to the same number of maximal cliques, this asymptotic growth cannot be avoided, as there will exist vertices <em>v</em> for which <em>N<sub>v</sub></em> will consist exclusively of a product of primes <em>p<sub>t</sub></em>, for <em>t</em> bounded below by a constant fraction of <em>h</em>.</p> <p>One can construct bipartite Cayley graphs in which the degree of each vertex is a constant fraction of <em>n</em> = |<em>V(G)</em>|. We then have <em>h</em> = &alpha; <em>n</em> for some 0 &lt; &alpha; &lt; 1; and <em>h</em> = |<em>V(G)</em>| + |<em>E(G)</em>| &isin; O(<em>n</em><sup>2</sup>), 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 <em>N<sub>j</sub></em> grow much more quickly than <em>e.g.</em> the factorial function.</p>