User jernej - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T11:49:29Z http://mathoverflow.net/feeds/user/1737 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104415/a-generalization-of-the-triangle-counting-problem-for-simple-weighted-graphs A generalization of the triangle counting problem for simple weighted graphs Jernej 2012-08-10T14:44:49Z 2013-05-03T09:22:00Z <p>One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. </p> <p>Consider now the following variant of the triangle counting problem. </p> <p>Given is a simple graph $G$ of order $n$ with a weight function defined on the edge set $$w:E(G) \mapsto \mathbb{Z}^{+}.$$ A triangle of $G$ with edges $e_1,e_2,e_3$ is said to be <em>valid</em> if the edge weights are pairwise coprime. That is $$\gcd(w(e_1),w(e_2)) = \gcd(w(e_1),w(e_3)) = \gcd(w(e_2),w(e_3)) = 1.$$ </p> <p>What am I wondering is the following </p> <blockquote> <p>Can you count the number of valid triangles of a weighted graph $G$ in subcubic time?</p> </blockquote> <p>Note that if all edge weights are 1 we are dealing with the classical triangle counting problem.</p> <p>Intuitively I believe that this is not possible since for a fixed vertex $v$ one has to check the gcd for $O(n^2)$ neighbours of $v$ but then again, the matrix multiplication trick is also counter-intuitive in its own way. </p> <p>So I would like to hear a more refined answer why this cannot be achieved or perhaps how it can be.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n Upper bounds for the sum of primes <= n Jernej 2011-04-29T13:50:26Z 2013-04-26T12:54:20Z <p>Let $s(n)$ denote the sum of primes less than or equal to n. Clearly, $s(n)$ is bounded from above by the sum of the first $n/2$ odd integers $+1$. $s(n)$ is also bounded by the sum of the first $n$ primes, which is asymptotically equivalent to $\frac{n^2}{2\log{n}}$. It should thus be possible to find estimates for $s(n)$ using the fact that for an $\epsilon > 0$ and $n$ large enough $s(n) &lt; (1+\epsilon)\frac{n^2}{\log{n}}.$</p> <p>I would like to know if there are any known sharp upper bounds for $s(n)$. That is, I am looking for a function $f(n)$ such that for every $n > N_0$ $$s(n) \leq f(n)$$</p> <p>As a way of relaxing the question, $s(n)$ could be regarded as the sum of the primes in the interval $[c,n]$ given a constant $c$.</p> http://mathoverflow.net/questions/120536/is-the-empty-graph-a-tree Is the empty graph a tree? Jernej 2013-02-01T19:33:47Z 2013-02-26T22:49:50Z <p>This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. </p> <p>The question is the following.</p> <blockquote> <p>How many spanning trees does the empty graph $E$ have?</p> </blockquote> <p>According to Sage it has 1, while Mathematica claims $\tau(E) = 0.$ Now the only subgraph of $E$ is $E$ hence this question can be rephrased as</p> <blockquote> <p>Is $E$ a tree?</p> </blockquote> <p>One characterization says that a tree is a connected graph with $n$ vertices and $n-1$ edges and would imply that $E$ is not a tree. However if we define a tree as a connected acyclic graph then $E$ is clearly a tree.</p> <p>It appears that as far as Kirchhoff is concerned any value would do since $$\rm{adj}(\mathcal{L}(E)) = \mathcal{L}(E) = k\mathcal{L}(E)$$ for any $k.$</p> <p>Hence what I am wondering is</p> <blockquote> <p>Are there any wider reasons in defining $E$ to (not) be a tree?</p> </blockquote> http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees Minimal graphs with a prescribed number of spanning trees Jernej 2012-04-10T12:45:21Z 2013-02-18T21:15:09Z <p>As its long ago since Erd&#337;s died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I find very interesting.</p> <blockquote> <p>Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having precisely $n$ spanning trees. What is the asymptotic behaviour of $\alpha$ ?</p> </blockquote> <p><strong>Motivation.</strong> I was introduced to the question through this <a href="http://rjlipton.wordpress.com/2009/06/24/the-inverse-spanning-tree-problem/" rel="nofollow">post</a> on Dick Lipton's blog. As it turns out, the question was posed already in 1970 by the Czech graph theorist J. Sedlacek (On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515–517)</p> <p><strong>What is known?</strong></p> <p>Sedlacek was able to show that for every (not so) large $n$</p> <p>$\alpha(n) \leq \frac{n+6}{3}$ if $n \equiv 0 \pmod{3}$ and $\alpha(n) \leq \frac{n+4}{3}$ if $n \equiv 2 \pmod{3}.$</p> <p>Following is a summary of what I was able to find out.</p> <p>Since the equation $n = ab+ac+bc$ is solvable for integers $1 \leq a &lt; b &lt; c$ for all but a finite number of integers $n$ (see <a href="http://mathoverflow.net/questions/6388/prime-numbers-p-not-of-the-form-ab-bc-ac-0-a-b-c-and-related-questi" rel="nofollow">this</a> post) it can be deduced (by considering the graph $\theta_{a,b,c}$ which has $ab+ac+bc$ spanning trees) that for large enough $n \not \equiv 2 \pmod{3}$ </p> <p>$$\alpha(n) \leq \frac{n+9}{4}.$$</p> <p>Moreover, the only fixed points of $\alpha$ are 3, 4, 5, 6, 7, 10, 13 and 22.</p> <p>By generalizing the approach and considering the graphs $\theta_{x_1,\ldots,x_k}$ one could try to lower the constant in the fraction of the inequality by an arbitrary amount. As it <a href="http://mathoverflow.net/questions/33411/a-generalisation-of-the-equation-n-ab-ac-bc" rel="nofollow">turns out</a> it is not know weather every large $n$ is then expressible as $n = x_1\cdots x_k(\frac{1}{x_1} + \cdots + \frac{1}{x_k})$ for suitable integers $1 \leq x_1 &lt; \cdots &lt; x_k.$</p> <p>Even if that method would work out, the bound would most probably still be suboptimal. According to the graph (created by randomly generating graphs and calculating the number of their spanning trees) it seems reasonable to conjecture that</p> <p><strong>Conjecture.</strong></p> <blockquote> <p>$$\alpha(n) = o(\log{n})$$</p> </blockquote> <p><img src="http://shrani.si/f/1G/lc/2yL7fZJd/graf.png" alt="alt text"></p> <p>The conjecture is clearly justifiable for highly composite numbers $n$ (consider the graph obtained after identifying a common vertex of the cycles $C_{x_1},\ldots,C_{x_k}$ for suitable odd factors $x_1, \ldots,x_k$ of $n$) but It fails for $n$'s that are primes.</p> <p>It is evident to me that I lack the tools necessary for attacking this conjecture so any kind of suggestions (where to look for a possible answer, what kind of tools should I learn..) related to it are very welcome!</p> <p>Edit. If anyone is willing to work on this problem, I'd be glad to collaborate since I'd benefit much from it! </p> http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs/116474#116474 Answer by Jernej for Spanning trees in planar graphs Jernej 2012-12-15T18:26:52Z 2013-02-07T13:39:26Z <p>Edit. As it turned out I was not using the right switch for <em>plantri</em>. </p> <p>This is therefore not an answer anymore but rather an extended comment for the case $n=11.$</p> <p>As it turns out the minimal number of spanning trees of a 3-connected planar graph of order 11 is 3965 and is attained by the graph on the figure bellow.</p> <p><img src="http://shrani.si/f/3f/IS/jiP8yvQ/pmin.png" alt="alt text"></p> <p>As for the non-planar 3-connected graph I am yet to compute the answer. I'll post the result here as soon as it gets computed.</p> http://mathoverflow.net/questions/119070/generating-non-isomorphic-graphs-by-adding-edges-to-a-given-graph Generating non-isomorphic graphs by adding edges to a given graph Jernej 2013-01-16T13:29:15Z 2013-01-17T11:49:59Z <p>Hello!</p> <p>This question is in a way related to the one I posted on <a href="http://math.stackexchange.com/questions/266444/generating-non-isomorphic-graph-by-adding-two-edges-to-a-fixed-graph" rel="nofollow">math.se</a>. Since the question there did not produce any final answer I am trying my luck here!</p> <p>I am given a fairly large graph $G$ and subsets $A,B \subseteq V(G)$ where $|A| \leq |B|.$ I need to extend $G$ so that every vertex $v \in A$ is <em>matched</em> with precisely one vertex in $B.$ By matched I mean that $v$ is adjacent to a vertex in $v' \in B$ and no other vertex of $A$ is adjacent to $v'.$</p> <p>The way I am doing this now is that for each fixed vertex $v \in A$ I compute the orbits of the stabilizer $\rm{Aut}(G)_v$ and then only add edges to representatives of orbits of elements of $B$ that are still "free." </p> <p>The problem with this approach is that we still obtain isomorphic graphs after we repeat the above procedure on the new graphs and for the next unmatched vertex. To patch this I also keep a list of canonical labelings for each graph as to ensure that each step gives only non isomorphic graphs.</p> <p>Now the problem is that the described approach is inefficient for my concrete case $(|A| = 40, |B| = 48).$ Since $G$ is highly-symmetric I am fairly confident that the number of all non-isomorphic graphs obtained by matching all vertices in $A$ is manageable but computing automorphism groups and canonical labelings after every iteration appears to slow down things a lot.</p> <p>Hence I am wondering if there is any other more efficient way to do this? Perhaps something based on computing the canonical labeling of $G$ at the start and then adding edges as to preserve the labeling? </p> <p>I am not really knowledgeable of what can be done but since I would really like to generate these graphs I'd be thankful for any constructive suggestion!</p> http://mathoverflow.net/questions/116884/structure-of-almost-all-bipartite-graphs Structure of almost all bipartite graphs Jernej 2012-12-20T17:17:00Z 2012-12-20T17:17:00Z <p>I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true that</p> <blockquote> <p>Almost all bipartite graphs of order $2n$ have bipartitons of size $n$?</p> </blockquote> <p>Is there any known result of this type? Is there anything related to other invariants in almost all bipartite graphs (max degree, number of edges)?</p> <p>Also, as far as I know there are no asymptotic enumerations of the number of bipartite graphs hence I am wondering if there are any (nontrivial) upper/lower bounds for the number of bipartite graphs of order $n,$ perhaps taking other invariants into account as well?</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112354#112354 Answer by Jernej for Important open problems that have already been reduced to a finite but infeasible amount of computation Jernej 2012-11-14T06:40:01Z 2012-11-14T06:56:27Z <p>I am not sure if this fits all the stated criterions but since it is a neat problem here it goes..</p> <p>Is there a 57-regular graph $X$ of order 3250 , girth 5 and diameter 2?</p> <p>$X$ is known as a <a href="http://en.wikipedia.org/wiki/Moore_graph" rel="nofollow">Moore</a> graph</p> <p>A lot is known about $X$ (automorphism group has order less than 350), independence number is at most 400, the chromatic polynomial is $(x-57)(x+8)^{1520}(x-7)^{1729}$, but the search space of all potential graphs is still too large to be computed with an algorithm.</p> http://mathoverflow.net/questions/108809/the-missing-moore-graphs-uniqueness (The) missing Moore graph(s) - uniqueness Jernej 2012-10-04T11:59:39Z 2012-10-04T12:42:36Z <p>In the related literature one often sees the phrase "The missing Moore graph" which (to me) tacitly implies that the missing Moore graph (if exists) is unique.</p> <p>Is there a result of this type or is or is this just a limitation of words that do not express the fact that there could be nonisomorphic graphs of diameter 2 and degree 57?</p> http://mathoverflow.net/questions/108042/is-this-a-counterexample-to-a-conjecture-about-independent-domination-in-cartesia/108052#108052 Answer by Jernej for Is this a counterexample to a conjecture about independent domination in cartesian graph products? Jernej 2012-09-25T13:37:54Z 2012-09-26T11:26:28Z <p>To summarize a bit:</p> <ul> <li>$\gamma(G)$ is defined as the usual <a href="http://mathworld.wolfram.com/DominatingSet.html%20" rel="nofollow">domination number</a> of a graph $G$</li> <li>$i(G)$ is defined as the smallest cardinality of a dominating set that is also an independent set</li> </ul> <p>Your graph $C$ is the disjoint union of $K_{3,3}$ and $K_1.$</p> <p>Clearly $\gamma(C) = 3$ and $i(C) = 4.$ For disjoint graphs $G,H$ we have $$(G \cup H) \square (G \cup H) = (G \square G) \cup (G \square H) \cup (H \square G) \cup (H \square H)$$</p> <p>which gives for $C = K_{3,3} \cup K_1$</p> <p>$$C \square C = K_{3,3} \square K_{3,3} \cup K_{3,3} \cup K_{3,3} \cup K_1.$$</p> <p>And thus $$\gamma(C \square C) = \gamma(K_{3,3} \square K_{3,3}) + 2\gamma(K_{3,3})+\gamma(K_1) = 11.$$</p> <p>This would indeed imply that $\gamma(C \square C) = 11 &lt; \gamma(C)i(C) = 12.$ Making the conjecture false for disconnected graphs. </p> <p><strong>Edit</strong>. In this <a href="http://www.sciencedirect.com/science/article/pii/S0166218X12002466#br000020" rel="nofollow">paper</a> the authors construct an infinite family of graphs that are a counterexample to the claim of conjecture 9.6. The constructed family of graphs is disconnected but they remark it can be made connected. </p> http://mathoverflow.net/questions/101857/what-is-the-effect-of-adding-one-edge-on-the-number-of-spanning-trees-of-a-given/101919#101919 Answer by Jernej for What is the effect of adding one edge on the number of spanning trees of a given graph ? Jernej 2012-07-11T07:07:13Z 2012-07-11T07:07:13Z <p>Sometimes, when dealing with concrete graphs, this bound can be handy. </p> <p>Let $f(G) = max_{u \not \sim v} C(G/uv)$ where $G/uv$ is obtained after contracting two non adjacent vertices $u,v$ of $G$ into a single vertex.</p> <p>From the deletion contraction recurrence we know that $$C(G') = C(G+e) = C(G)+C( (G+e)/e) \leq C(G)+f(G)$$ from where you can easily get a bound for $\frac{C(G)}{C(G')}$</p> <p>In the same manner you can obtain a lower bound for $\frac{C(G)}{C(G')}.$</p> http://mathoverflow.net/questions/100816/maximal-class-of-simple-graphs-of-order-n-with-mutually-distinct-numbers-of-spa Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees Jernej 2012-06-27T22:26:53Z 2012-07-06T09:37:06Z <p>This problem in some ways related to <a href="http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees" rel="nofollow">this</a> post.</p> <blockquote> <p>Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the growth rate of $|A_n|.$ </p> </blockquote> <p>The question was raised by J.Sedlacek in his paper entitled: <em>On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.</em> </p> <p>Sedlacek was able to show that $|A_n| = \omega(n)$ and remarked that it is not known if $|A_n| = \omega(n^2).$</p> <p>Following are some observations about $|A_n|.$</p> <ol> <li><p>Clearly $|A_n| \leq n^{n-2}$ and $|A_n| \leq |A_{n+1}|$</p> <ul> <li>Playing with prime partitions a bit it is possible to show that</li> </ul> <p>$$|A_n| = \omega(\sqrt{n}e^{\frac{2\pi}{\sqrt{3}}\sqrt{n/\log{n}}})$$</p> <ul> <li>The following table can be computed using sage+nauty:</li> </ul></li> </ol> <p>$$\begin{array}{ccc} n &amp; |A_n| &amp; \frac{n^{n-2}}{|A_n|}\\ 1 &amp; 1 &amp; 1 \\ 2 &amp; 1 &amp; 1 \\ 3 &amp; 2 &amp; 1.5 \\ 4 &amp; 5 &amp; 3.2 \\ 5 &amp; 16 &amp; 7.8 \\ 6 &amp; 65 &amp; 19.9\\ 7 &amp; 386 &amp; 43.5\\ 8 &amp; 3700 &amp; 70.8 \\ 9 &amp; 55784 &amp; 85.7\\ 10 &amp; 1134526 &amp; 88.1 \\ 11 &amp; 27053464 &amp; 87.1 \\ \end{array}$$</p> <p>The bound mentioned under 2. was obtained using a construction of graphs with cut vertices. Since almost all graphs are blocks it is (in a way) reasonable to ask</p> <blockquote> <p><strong>Question.</strong> Is there a construction (using blocks) that can improve bound 2.?</p> </blockquote> <p>I believe that this should also be provable:</p> <blockquote> <p><strong>Conjecture.</strong> $|A_n| = \omega(k^n)$ for all $k \in \mathbb{N}.$</p> </blockquote> <p>In case this turns out to be a hard problem I would at least like to extend table 3. further. I am currently computing $|A_n|$ by generating all connected graphs of order $n$ with at least $n$ edges, computing their spanning trees and count distinct such numbers. One optimization could be derived by using the fact that $A_n \subset A_{n+1}$ but this is just a minor thing. I therefore leave the following question for the end:</p> <blockquote> <p><strong>Question.</strong> How can we compute $|A_n|$ quickly?</p> </blockquote> http://mathoverflow.net/questions/96612/neat-results-from-algebraic-graph-theory Neat results from algebraic graph theory Jernej 2012-05-10T21:04:15Z 2012-05-11T01:21:49Z <p>Studying algebraic graph theory, I've stumbled across a wide range of results that I found pretty stunning and also useful. I'd like to share them here and ask for your favorite result from this area?</p> <p>Let $G$ be a simple graph $A$ and $L$ its adjacency and Laplacian matrix $\lambda_1\leq \cdots \leq\lambda_n$ and $\mu_1 \leq \cdots \leq \mu_n$ the respective eigenvalues of $A$ and $L$.</p> <ol> <li><p>(Wilf, Hoffman) For a nontrivial graph $G$ $$1+\frac{\lambda_n}{-\lambda_1} \leq \chi(G) \leq 1+\lambda_n$$</p></li> <li><p>(Sachs,Harary) Let $G$ be a graph of odd girth $2r+1.$ Let $p(x) = \sum_{i=0}^n c_{n-i} x^i$ be the characteristic polynomial of $A.$ Then $$c_3 = \cdots = c_{2r-1} = 0$$ and $\frac{-c_{2r+1}}{2}$ is the number of $(2r+1)$-cycles in G.</p></li> <li><p>(Folklore) The number of triangles in $G$ equals $tr(A^3)/6.$ Since matrix multiplication can be done in $O(n^k)$ for $k \leq 2.37$ this presents an improvement over the straightforward approach for counting triangles in graphs that is currently the fastest way to compute the number of triangles in simple graphs.</p></li> <li><p>(Kirchhoff) The number of spanning trees in G is $\frac{1}{n}\mu_2 \cdots \mu_n$</p></li> <li><p>(McKay) $diam(G) \geq \frac{4}{n\mu_2}$</p></li> </ol> <p>Do you have any neat results like this to share?</p> http://mathoverflow.net/questions/33411/a-generalisation-of-the-equation-n-ab-ac-bc A generalisation of the equation n = ab + ac + bc Jernej 2010-07-26T15:38:54Z 2012-05-10T00:52:58Z <p>In a result I am currently studying (completely unrelated to number theory) I had to examine the solvability of the equation $n = ab+ac+bc$ where $n,a,b,c$ are positive integers $0 &lt; a &lt; b &lt; c.$</p> <p>As it turned <A HREF="http://mathoverflow.net/questions/6388/prime-numbers-p-not-of-the-form-ab-bc-ac-0-a-b-c-and-related-questi" rel="nofollow">out</A> the set of numbers not expressible in the above way is finite.</p> <p>Generalizing the equation to four variables and checking the solutions of the equation $n = abc+abd+acd+bcd$ for $0 &lt; a &lt; b &lt; c &lt; d$ I've noticed that it looks like there exists a number $n_0$ such that for $n > n_0$ $n$ is expressible as $abc+abd+acd+bcd.$ The fact that a similar pattern occurs for five variables motivates me to ask the following question:</p> <p><b> Question. </b> Given a positive integer $m$ is there a number $n_0$ such that every $n > n_0$ is expressible as $n = x_1\cdots x_m(\frac{1}{x_1} + \cdots + \frac{1}{x_m})$ where $0 &lt; x_1 &lt; x_2 &lt;\ldots &lt; x_m$.</p> <p>The question is way too much for my (non-existent) knowledge of number theory. Perhaps there is a known result regarding such equations or, it can be somehow inductively derived from the case $m = 3.$ Any pointers in this direction are appreciated!</p> http://mathoverflow.net/questions/87425/definition-of-convex-cycles Definition of convex cycles Jernej 2012-02-03T12:29:28Z 2012-04-10T01:46:17Z <p>Consider the following definition.</p> <p>Let $C$ be a cycle of a simple graph $G$. We say that $C$ is <em>convex</em> if for any pair of distinct vertices $u,v \in V(C)$ $$d_C(u,v) &lt; d_{G-C}(u,v).$$</p> <p>Is there any other name for such cycles? I was trying to find out some references/literature presenting results related to such cycles but I haven't found anything useful. I am mostly interested in the questions of whether such cycles have any other characterization and what is the structure of graphs that have many such cycles.</p> http://mathoverflow.net/questions/87425/definition-of-convex-cycles/93564#93564 Answer by Jernej for Definition of convex cycles Jernej 2012-04-09T13:22:46Z 2012-04-09T13:22:46Z <p>In the paper entitled Convex cycle bases and Cartesian products by Hellmuth, Leydold and Stadler, I found the following characterization of convex cycles </p> <p>Let $G$ be a simple graph and $C \subseteq G$ a cycle. If $|C|$ is odd then $C$ is convex if and only if for every edge $e = xy \in C$ there exist a unique vertex $z \in C$ such that </p> <p>$$d_G(x,z) = d_G(y,z) = \frac{|C|-1}{2} \hbox{ and } S_{xz} = S_{yz} = 1.$$</p> <p>If $|C|$ is even then $C$ is convex if and only if for every edge $e = xy \in C$ there is a unique edge $f = uv \in C$ such that</p> <ol> <li>$d_G(x,u) = d_G(y,v) = \frac{|C|}{2}-1$</li> <li>$d_G(x,v) = d_G(y,u) = \frac{|C|}{2}$</li> <li>$S_{xu} = S_{yv} = 1$</li> <li>$S_{xv} = S_{yu} = 2$</li> </ol> <p>Where $S_{xy}$ denotes the number of shortest paths between $x$ and $y.$</p> http://mathoverflow.net/questions/92827/almost-all-graphs-have-a-subgraph-from-a-large-class-of-graphs-with-constant-orde Almost all graphs have a subgraph from a large class of graphs with constant order Jernej 2012-04-01T17:37:23Z 2012-04-05T13:41:41Z <p>I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting. </p> <p>I suspect the question might have a very trivial answer using some of the relatively modern tools of which I am unaware.</p> <p>Denote by $T_k$ the set of all trees on $k$ vertices (up to isomorphism). Let $c$ be a positive integer and let $T$ be a subset of $T_c$ such that $$|T| > \frac{|T_c|}{2}$$</p> <p>For $n \geq c$ let $p_n$ be the probability that a tree, chosen uniformly at random from $T_n$ contains as a subgraph at least one tree from $T.$</p> <p>Is the following statement true or false?</p> <blockquote> <p>$p_n \rightarrow 1$ as $n \rightarrow \infty \; \; (1)$ ?</p> </blockquote> <p>It seems to me that the following does not hold if we consider labeled trees, but I am not sure how to smartly compute the ratio $\frac{T_n'}{T_n}$ where $T_n'$ is the subset of all trees from $T_n$ such that every graph in $T_n'$ has some subgraph from $T.$</p> <p>Is the above statement true? Is there any way to relax the inequality? If not, is there a way to (non trivially) restrict the inequality so that $(1)$ holds?</p> http://mathoverflow.net/questions/21088/upper-bound-for-abc-in-terms-of-abbcac Upper bound for a+b+c in terms of ab+bc+ac Jernej 2010-04-12T11:39:06Z 2011-12-01T19:40:55Z <p>I am given a triple of positive integers $a,b,c$ such that $a \geq 1$ and $b,c \geq 2$.</p> <p>I would like to find an upper bound for $a+b+c$ in terms of $n = ab+bc+ac$. Clearly $a+b+c &lt; ab+bc+ac = n$.</p> <p>Is there any sharper upper bound that could be obtained (perhaps asimptotically)?</p> http://mathoverflow.net/questions/72608/laplacian-spectrum-for-product-graphs Laplacian spectrum for product graphs Jernej 2011-08-10T18:40:19Z 2011-10-14T17:22:18Z <p>Let $G$ and $H$ be simple graphs. </p> <p>I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong product as defined here <a href="http://en.wikipedia.org/wiki/Graph_product" rel="nofollow">http://en.wikipedia.org/wiki/Graph_product</a> .</p> <p>Given that $\lambda_1, \ldots, \lambda_n$ and $\mu_1, \ldots \mu_m$ are the eigenvalues of the Laplacians of $G$ and $H$ respectively, it is well known that the eigenvalues of the carteisan product of $G$ and $H$ are $$\lambda_i + \mu_j \quad \hbox{for} \quad i = 1,\ldots,n \quad \hbox{and} \quad j = 1, \ldots,m.$$</p> <p>I am interested in the relation between the eigenvalues of $G$ and $H$ with respect to the eigenvalues of the other mentioned products.</p> <p>The same problem has already been considered for the spectrum of the adjacency matrix and solved under the general setting of the NEPS operation.</p> <p>I suspect the same problem for the spectrum of the Laplacian eigenvalue to be slightly harder (as I think this would somehow have to characterize when is the lexicographical product of $G$ and $H$ connected) but I am not sure as I was not able to find any literature related to this matter.</p> <p>Anyone happens to know the answer or could possibly provide some literature on this matter?</p> http://mathoverflow.net/questions/76204/counting-matrices-with-different-determinants Counting matrices with different determinants Jernej 2011-09-23T13:02:46Z 2011-09-23T19:47:13Z <p>Let $A$ and $B$ be two matrices of order $n$ over a finite subset of integers $S$ such that $A$ and $B$ are positive-definite, nonsingular and symmetric.</p> <p>I am interested in proprieties about $A$, $B$ that would allow me to conclude that $det(A) \not = det(B),$ without actually computing the determinant.</p> <p>Motivation: I would like to bound (from bellow) the number of such matrices (having some additional structure) such that they have mutually different determinants.</p> <p>I assume this problem is hard in general, but any pointers to relevant literature would be appreciated.</p> <p>Thanks!</p> http://mathoverflow.net/questions/69900/asymptotics-for-the-number-of-ways-to-sum-primes-such-that-the-sum-is-n Asymptotics for the number of ways to sum primes such that the sum is <= n Jernej 2011-07-09T19:03:55Z 2011-07-21T04:46:04Z <p>Hello!</p> <p>Given $n$ I would like to find a lower bound (or a tight asymptotics) for the number $s(n)$ of solutions to $$p_1 + \ldots + p_k \leq n \quad (1)$$ where $k$ is arbitrary and $p_1 \leq \ldots \leq p_k$ are odd prime numbers. I have edited the answer and gave three attempts I tried to use in order to find an asymptotics for $s(n)$ and the reason I failed to obtain an answer. I'll be thankful if someone can give further insights into the problem.</p> <p>I have attempted to solve the problem in the following ways:</p> <ol> <li><p>By considering the set of primes $P$ in the interval $[2,\ldots,\sqrt{n}]$ whose size is at least $\frac{\sqrt{n}}{\log{n}}.$ We then analyze the number of combinations with repetition allowed from a set of $\frac{\sqrt{n}}{\log{n}}+1$ numbers where we pick $\sqrt{n}$ numbers. <strong>This estimate gives a worse bound than just considering the number of all partitions into odd primes of $n$.</strong> Is there any way to modify this reasoning in order to yield a better bound? Perhaps using another function instead of $\sqrt(n)?$</p></li> <li><p>If $p_p(n)$ denotes the number of partitions of $n$ into odd prime parts then we're basically tring to bound $\displaystyle \sum_{i=2}^n p_p(i).$ Since $p_p(i) \sim e^{C\sqrt{i/\log(i)}}$ for a constant $C$ one could use the integral bounding the summation to obtain a lower bound. Since $p_p(i)$ is not integrable one has to use a bound for it. The only reasonable bound I see is $e^{\sqrt{i/log{i}}} > e^\sqrt[3]{i}$.<strong>Again, applying this bound, and considering the bound from the resulting integral we see that it is inferior to the one for the number of partitions of $n$ into odd primes.</strong> Is there any better bound for $p_p(i)$ or perhaps a superior way to analyze the integral?</p></li> <li><p>The generating function with the number of partitions of $n$ into prime as coefficients is $G(x) = \prod_{i\geq 1} \frac{1}{1-x^{p_i}}$ where $p_i$ is the $i$'th prime. So basically I am estimating the coefficients of the generating function that is obtained after applying the operation of convolution to $G(x).$ The book <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html" rel="nofollow">http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html</a> contains a section entitled "saddle point method" related to the asymptotic estimate of coefficients for generating functions of that kind, but my knowledge of the related field is to scarce to really apply this method.</p></li> </ol> <p>Anyone happens to see a superior solution to my problem?</p> http://mathoverflow.net/questions/69900/asymptotics-for-the-number-of-ways-to-sum-primes-such-that-the-sum-is-n/70859#70859 Answer by Jernej for Asymptotics for the number of ways to sum primes such that the sum is <= n Jernej 2011-07-20T23:50:00Z 2011-07-20T23:50:00Z <p>The question has been answered on math.stackexchange, the answer here is just for the sake of completeness.</p> <p>From <a href="http://math.stackexchange.com/questions/52737/estimating-an-integral" rel="nofollow">http://math.stackexchange.com/questions/52737/estimating-an-integral</a> we see that an asymptotically equivalent estimate is $2\sqrt{n\log{n}}\;e^{\sqrt{n/\log{n}}}.$</p> http://mathoverflow.net/questions/59837/randomly-contracting-edges-of-a-graph-expected-number-of-vertices Randomly contracting edges of a graph - expected number of vertices? Jernej 2011-03-28T13:58:31Z 2011-07-16T09:05:22Z <p>Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.</p> <p>I would like to compute (or at least obtain a lower bound) for $E[|V(G')|]$ in terms of some known graph invariants (number of edges, degree sequence, connectivity,..)</p> <p>I am sure I am not the first one that studied such a probabilistic space and since I couldn't find any estimates for $E[|V(G')|]$ in my textbook I am asking: is there any simple identity/estimate for $E[|V(G')|]$ ? Is there any reference to a paper studying this quantity?</p> <p><strong>Edit</strong>: I have removed the completely wrong attempt to estimate $E[|V(G')|]$.</p> http://mathoverflow.net/questions/20955/the-missing-euler-idoneal-numbers The missing Euler Idoneal numbers Jernej 2010-04-10T20:37:30Z 2011-07-13T17:16:17Z <p>It is known that if GRH holds there does not exist additional Idoneal numbers. (see www.mast.queensu.ca/~kani/papers/idoneal.pdf this paper puts on the question of correctnes for Wikipedia and Wolfram MathWorld since they state there could only be ONE additional Idoneal number)</p> <p>What I am interested in is whether there are any certain properties that an additional idoneal number X should satisfy. I am trying to prove a theorem which would only work if X has three odd divisors. Is anything like that known or easy to derive?</p> <p>I would like to find a precise reference to the fact that any idoneal number not in the currently known finite list has to have at least three odd prime factors (this should hold, as long as the answer by Pete is valid. Pete also suggested looking into the book primes of the form x^2 + ny^2 but my knowledge of number theory is too limited to derive the stated fact from there)</p> <p><strong>EDIT</strong>: Removed misinterpreted sentence about GRH and idoneal numbers. Added request for reference. I will give 100 bounty points to the first concise reference of this fact.</p> http://mathoverflow.net/questions/70055/graphs-of-order-n-with-a-laplacian-eigenvalue-of-multiplicity-n-1 Graphs of order n with a Laplacian eigenvalue of multiplicity n-1. Jernej 2011-07-11T20:52:51Z 2011-07-11T21:14:21Z <p>I suspect this could be an easy one but I am not an expert in algebraic graph theory.</p> <p>Let $Q(G)$ define the Laplacian matrix for a simple graph $G$. It is well known that n is an eigenvalue of $Q(K_n)$ with multiplicity $n-1$. I was wondering if graphs $G$ of order $n$ such that $Q(G)$ has an eigenvalue of multiplicity $n-1$ have been characterized. </p> <p>More specifically, is there any other graph of order $n$ besides $K_n$ such that respective Laplacian matrix has an eigenvalue of multiplicity $n-1$ ?</p> <p>I think an answer could perhaps be found here <a href="https://springerlink3.metapress.com/content/a01321p632887837/resource-secured/?target=fulltext.pdf&amp;sid=rrxkjv553gcfwriiuwfaip55&amp;sh=www.springerlink.com" rel="nofollow">https://springerlink3.metapress.com/content/a01321p632887837/resource-secured/?target=fulltext.pdf&amp;sid=rrxkjv553gcfwriiuwfaip55&amp;sh=www.springerlink.com</a> but needless to say I do not have access to the paper.</p> http://mathoverflow.net/questions/58408/number-of-k-partitions-of-n-into-odd-prime-parts Number of $k$-partitions of $n$ into odd prime parts Jernej 2011-03-14T10:38:49Z 2011-07-09T19:26:03Z <p>Browsing through OESIS I have found that if $p_p(n)$ denotes the number of partitions of $n$ into prime parts then $p_p(n) = O(e^{\frac{2 \Pi}{\sqrt{3}}\sqrt{n/\log n}})$.</p> <p>I am interested in the asymptotic behaviour of a more specific function - $p(n,k)$ defined as the number of partitions of $n$ into $k$ parts such that every part is an odd prime. (for example one such partition of 13 would be 7+3+3)</p> <p>Is there any known literature for looking up such identities? Or perhaps, is there an easy way to derive an asymptotic bound for $p(n,k)$ ? </p> http://mathoverflow.net/questions/69680/asymptotics-for-the-number-of-partitions-of-n-into-odd-prime-parts/69722#69722 Answer by Jernej for Asymptotics for the number of partitions of $n$ into odd prime parts Jernej 2011-07-07T14:17:28Z 2011-07-07T14:23:26Z <p>I think I found the answer I was looking for in some old paper by Erdos. <a href="http://www.renyi.hu/~p_erdos/1942-02.pdf" rel="nofollow">http://www.renyi.hu/~p_erdos/1942-02.pdf</a></p> <p>On page 448 he says:</p> <p>Let $a_1 &lt; a_2 &lt; ...$ be an infinite sequence of integers of density $\alpha$ such that the a's have no common factor. Denote by $p'(n)$ the number of partitions of $n$ into the a's. Then $$\log(p'(n)) = c(\alpha n)^{1/2}.$$ where $c = \pi \sqrt{\frac{2}{3}}$</p> <p>I just have to make sure what precisely he meant with the term density as in the classical sense <a href="http://en.wikipedia.org/wiki/Asymptotic_density" rel="nofollow">http://en.wikipedia.org/wiki/Asymptotic_density</a> density of a sequence is defined as a number and in this case the asymptotic identity he derived makes no sense. If someone knows what is the precise definition of density in this case, let me know it as a comment please!</p> http://mathoverflow.net/questions/69680/asymptotics-for-the-number-of-partitions-of-n-into-odd-prime-parts Asymptotics for the number of partitions of $n$ into odd prime parts Jernej 2011-07-06T23:13:26Z 2011-07-07T14:23:26Z <p>Hello!</p> <p>I am interested in the asymptotic behavior of the function $p_o(n)$ defined as the number of partitions of $n$ into odd prime parts A099773 - <a href="http://oeis.org/A099773" rel="nofollow">http://oeis.org/A099773</a> .</p> <p>I couldn't find any paper or book studying the mentioned quantity but the amount of literature available to me is quite limited and I am wondering if someone could tell me what the asymptotic behavior of $p_o(n)$ is and perhaps point out a relevant reference for me to read.</p> <p>Thanks!</p> http://mathoverflow.net/questions/58836/connected-graphs-that-are-not-2-connected Connected graphs that are not 2 connected Jernej 2011-03-18T13:13:11Z 2011-03-18T13:19:15Z <p>In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics. </p> <p>For example it is stated that the number of all unlabeled graph is $\sim 2^{ n \choose 2}/n!$ and that almost all graphs are blocks. They also state that it's very likely that for all natural numbers $n$ almost all graphs are $n-$ connected (do not know if that is already proven or not).</p> <p>The book is quite old and I assume there are many new results in this field. I am interested in the asymptotics for the number of graphs that are connected but not $2-$ connected. That is connected graphs with more than one block. In the mentioned book I was not able to find any function asymptotic to this quantity but I believe there could be some new result covering my question.</p> <p>Anyone happens to be aware of it?</p> http://mathoverflow.net/questions/58425/number-of-partitions-of-n-with-different-product Number of partitions of $n$ with different product Jernej 2011-03-14T13:06:02Z 2011-03-15T17:35:51Z <p>Let $S_n$ denote the set of partions of $n$ such that every part is greater than 1. Partitions $(x_1,\ldots,x_k), (y_1,\ldots,y_l) \in S_n$ are said to have almost equal product if $$\prod_{i=1}^k (x_i+1) = \prod_{i=1}^l (y_i+1)$$.</p> <p>For example if $n = 14$ the partitions (3,3,8) and (2,5,7) are almost equal since (3+1)(3+1)(8+1) = (2+1)(5+1)(7+1).</p> <p>Now if we denote by $S'_n$ the largest subset of $S_n$ not containing almost equal partitons,then I would like to find the asymptotic value of $|S'_n|$. I believe $|S'_n|$ is at least subexponential in $n$ but do not know how to prove this. Is there any way to perhaps find a bound on the number of pairs of almost equal partitions and take it from there?</p> http://mathoverflow.net/questions/24526/good-papers-books-essays-about-the-thought-process-behind-mathematical-research/24557#24557 Comment by Jernej Jernej 2013-03-19T17:52:37Z 2013-03-19T17:52:37Z There is also a 41mins long talk by Hamming <a href="http://www.youtube.com/watch?v=a1zDuOPkMSw" rel="nofollow">youtube.com/watch?v=a1zDuOPkMSw</a> if you don't like to read the transcript. http://mathoverflow.net/questions/123846/applications-of-line-graphs Comment by Jernej Jernej 2013-03-12T09:51:01Z 2013-03-12T09:51:01Z Delio, can you cite one of these sociological papers? http://mathoverflow.net/questions/123846/applications-of-line-graphs Comment by Jernej Jernej 2013-03-07T11:08:21Z 2013-03-07T11:08:21Z Just a suggestion. Find a suitable interpretation of vertex/edge colorings. And then play with the fact that the chromatic index of a graph is the chromatic number of its line graph. http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees Comment by Jernej Jernej 2013-02-17T13:32:11Z 2013-02-17T13:32:11Z The $x$-axis represents $n$ while the $y$ axis represents $\alpha(n)$ http://mathoverflow.net/questions/121243/determinant-of-fibonacci-sum-graphs Comment by Jernej Jernej 2013-02-11T21:44:13Z 2013-02-11T21:44:13Z The diagonal is of course zero since I am first constructing a graph and then computing the adjacency matrix. http://mathoverflow.net/questions/121243/determinant-of-fibonacci-sum-graphs Comment by Jernej Jernej 2013-02-11T19:15:22Z 2013-02-11T19:15:22Z I always get zero with the following sage program for constructing the graph <a href="http://pastebin.com/0t9GHHzM" rel="nofollow">pastebin.com/0t9GHHzM</a> http://mathoverflow.net/questions/121501/determinant-of-fibonacci-sum-graphs Comment by Jernej Jernej 2013-02-11T17:57:42Z 2013-02-11T17:57:42Z The claim will follow immediately if you are able to show that your graph has no cycles of odd length! http://mathoverflow.net/questions/102031/mclaughlin-graph/102044#102044 Comment by Jernej Jernej 2013-02-09T13:51:40Z 2013-02-09T13:51:40Z When I try to run the first example in gap it stops with this error in the first line - Variable: 'AtlasGenerators' must have a value. Do you happen to see why? http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs/116474#116474 Comment by Jernej Jernej 2013-02-07T12:46:44Z 2013-02-07T12:46:44Z Weird. I'll try to run the program again and see why the proposed graph is not found. It clearly looks like a counterexample to the stated answer! http://mathoverflow.net/questions/120536/is-the-empty-graph-a-tree Comment by Jernej Jernej 2013-02-01T20:31:25Z 2013-02-01T20:31:25Z @G&#252;nter Rote Sage simply computes the subdivision of the Laplacian matrix and its determinant. http://mathoverflow.net/questions/119062/hamiltonian-cycles-in-power-graphs Comment by Jernej Jernej 2013-01-17T12:52:10Z 2013-01-17T12:52:10Z That's a very nice question! I have tested the conjecture for values of $n$ up to 500 and it holds. http://mathoverflow.net/questions/119070/generating-non-isomorphic-graphs-by-adding-edges-to-a-given-graph Comment by Jernej Jernej 2013-01-17T11:30:33Z 2013-01-17T11:30:33Z @BrendanMcKay the base graph has an automorphism group of order 2^85 * 3^32 * 5^16 * 7^16 http://mathoverflow.net/questions/119070/generating-non-isomorphic-graphs-by-adding-edges-to-a-given-graph Comment by Jernej Jernej 2013-01-16T18:55:09Z 2013-01-16T18:55:09Z @GerhardPaseman A and B are indeed disjoint. And there are no edges between! I don't see any reasons why such a matching would not exists since $B$ is larger then $A.$ Yes, all I really want are nonisomorphic extensions that match $A$ to $B$. BTW, may I ask you about system designs? http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs Comment by Jernej Jernej 2013-01-16T12:41:41Z 2013-01-16T12:41:41Z @utdiscant In case you haven't noticed the conjecture does not hold! http://mathoverflow.net/questions/116800/similarity-measure-between-2-bi-partite-graph Comment by Jernej Jernej 2012-12-20T17:22:55Z 2012-12-20T17:22:55Z I suggest you ask this sort of questions on cs.stackexchange.com. As for your question you could use some hybrid function based on the generalized degree sequence of a weighted graph + graph isomorphism + wiener index. But it is hard to give you good suggestions without knowing the full requirements.