User jernej - MathOverflow

A generalization of the triangle counting problem for simple weighted graphs

2012-08-10T14:44:49Z

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.

Consider now the following variant of the triangle counting problem.

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 valid 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.$$

What am I wondering is the following

Can you count the number of valid triangles of a weighted graph $G$ in subcubic time?

Note that if all edge weights are 1 we are dealing with the classical triangle counting problem.

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.

So I would like to hear a more refined answer why this cannot be achieved or perhaps how it can be.

Upper bounds for the sum of primes <= n

2011-04-29T13:50:26Z

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) < (1+\epsilon)\frac{n^2}{\log{n}}.$

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)$$

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

Is the empty graph a tree?

2013-02-01T19:33:47Z

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.

The question is the following.

How many spanning trees does the empty graph $E$ have?

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

Is $E$ a tree?

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.

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

Hence what I am wondering is

Are there any wider reasons in defining $E$ to (not) be a tree?

Minimal graphs with a prescribed number of spanning trees

2012-04-10T12:45:21Z

As its long ago since Erdő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.

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$ ?

Motivation. I was introduced to the question through this post 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)

What is known?

Sedlacek was able to show that for every (not so) large $n$

$ \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}. $

Following is a summary of what I was able to find out.

Since the equation $n = ab+ac+bc$ is solvable for integers $1 \leq a < b < c$ for all but a finite number of integers $n$ (see this 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}$

$$\alpha(n) \leq \frac{n+9}{4}.$$

Moreover, the only fixed points of $\alpha$ are 3, 4, 5, 6, 7, 10, 13 and 22.

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 turns out 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 < \cdots < x_k.$

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

Conjecture.

$$\alpha(n) = o(\log{n})$$

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.

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!

Edit. If anyone is willing to work on this problem, I'd be glad to collaborate since I'd benefit much from it!

Answer by Jernej for Spanning trees in planar graphs

2012-12-15T18:26:52Z

Edit. As it turned out I was not using the right switch for plantri.

This is therefore not an answer anymore but rather an extended comment for the case $n=11.$

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.

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.

Generating non-isomorphic graphs by adding edges to a given graph

2013-01-16T13:29:15Z

Hello!

This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!

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 matched 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'.$

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

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.

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.

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?

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!

Structure of almost all bipartite graphs

2012-12-20T17:17:00Z

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

Almost all bipartite graphs of order $2n$ have bipartitons of size $n$?

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)?

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?

Answer by Jernej for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T06:40:01Z

I am not sure if this fits all the stated criterions but since it is a neat problem here it goes..

Is there a 57-regular graph $X$ of order 3250 , girth 5 and diameter 2?

$X$ is known as a Moore graph

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.

(The) missing Moore graph(s) - uniqueness

2012-10-04T11:59:39Z

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.

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?

Answer by Jernej for Is this a counterexample to a conjecture about independent domination in cartesian graph products?

2012-09-25T13:37:54Z

To summarize a bit:

$\gamma(G)$ is defined as the usual domination number of a graph $G$
$i(G)$ is defined as the smallest cardinality of a dominating set that is also an independent set

Your graph $C$ is the disjoint union of $K_{3,3}$ and $K_1.$

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)$$

which gives for $C = K_{3,3} \cup K_1$

$$ C \square C = K_{3,3} \square K_{3,3} \cup K_{3,3} \cup K_{3,3} \cup K_1.$$

And thus $$\gamma(C \square C) = \gamma(K_{3,3} \square K_{3,3}) + 2\gamma(K_{3,3})+\gamma(K_1) = 11.$$

This would indeed imply that $\gamma(C \square C) = 11 < \gamma(C)i(C) = 12.$ Making the conjecture false for disconnected graphs.

Edit. In this paper 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.

Answer by Jernej for What is the effect of adding one edge on the number of spanning trees of a given graph ?

2012-07-11T07:07:13Z

Sometimes, when dealing with concrete graphs, this bound can be handy.

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.

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')}$

In the same manner you can obtain a lower bound for $\frac{C(G)}{C(G')}.$

Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

2012-06-27T22:26:53Z

This problem in some ways related to this post.

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

The question was raised by J.Sedlacek in his paper entitled: On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.

Sedlacek was able to show that $|A_n| = \omega(n)$ and remarked that it is not known if $|A_n| = \omega(n^2).$

Following are some observations about $|A_n|.$

Clearly $|A_n| \leq n^{n-2}$ and $|A_n| \leq |A_{n+1}|$
- Playing with prime partitions a bit it is possible to show that
$$ |A_n| = \omega(\sqrt{n}e^{\frac{2\pi}{\sqrt{3}}\sqrt{n/\log{n}}}) $$
- The following table can be computed using sage+nauty:

$$\begin{array}{ccc} n & |A_n| & \frac{n^{n-2}}{|A_n|}\\ 1 & 1 & 1 \\ 2 & 1 & 1 \\ 3 & 2 & 1.5 \\ 4 & 5 & 3.2 \\ 5 & 16 & 7.8 \\ 6 & 65 & 19.9\\ 7 & 386 & 43.5\\ 8 & 3700 & 70.8 \\ 9 & 55784 & 85.7\\ 10 & 1134526 & 88.1 \\ 11 & 27053464 & 87.1 \\ \end{array} $$

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

Question. Is there a construction (using blocks) that can improve bound 2.?

I believe that this should also be provable:

Conjecture. $|A_n| = \omega(k^n)$ for all $k \in \mathbb{N}.$

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:

Question. How can we compute $|A_n|$ quickly?

Neat results from algebraic graph theory

2012-05-10T21:04:15Z

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?

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

(Wilf, Hoffman) For a nontrivial graph $G$ $$1+\frac{\lambda_n}{-\lambda_1} \leq \chi(G) \leq 1+\lambda_n$$
(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.
(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.
(Kirchhoff) The number of spanning trees in G is $\frac{1}{n}\mu_2 \cdots \mu_n$
(McKay) $diam(G) \geq \frac{4}{n\mu_2}$

Do you have any neat results like this to share?

A generalisation of the equation n = ab + ac + bc

2010-07-26T15:38:54Z

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 < a < b < c.$

As it turned out the set of numbers not expressible in the above way is finite.

Generalizing the equation to four variables and checking the solutions of the equation $n = abc+abd+acd+bcd$ for $0 < a < b < c < 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:

Question. 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 < x_1 < x_2 <\ldots < x_m$.

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!

Definition of convex cycles

2012-02-03T12:29:28Z

Consider the following definition.

Let $C$ be a cycle of a simple graph $G$. We say that $C$ is convex if for any pair of distinct vertices $u,v \in V(C)$ $$ d_C(u,v) < d_{G-C}(u,v).$$

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.

Answer by Jernej for Definition of convex cycles

2012-04-09T13:22:46Z

In the paper entitled Convex cycle bases and Cartesian products by Hellmuth, Leydold and Stadler, I found the following characterization of convex cycles

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

$$ d_G(x,z) = d_G(y,z) = \frac{|C|-1}{2} \hbox{ and } S_{xz} = S_{yz} = 1.$$

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

$ d_G(x,u) = d_G(y,v) = \frac{|C|}{2}-1 $
$d_G(x,v) = d_G(y,u) = \frac{|C|}{2}$
$ S_{xu} = S_{yv} = 1$
$ S_{xv} = S_{yu} = 2$

Where $S_{xy}$ denotes the number of shortest paths between $x$ and $y.$

Almost all graphs have a subgraph from a large class of graphs with constant order

2012-04-01T17:37:23Z

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.

I suspect the question might have a very trivial answer using some of the relatively modern tools of which I am unaware.

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} $$

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

Is the following statement true or false?

$p_n \rightarrow 1$ as $n \rightarrow \infty \; \; (1)$ ?

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

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?

Upper bound for a+b+c in terms of ab+bc+ac

2010-04-12T11:39:06Z

I am given a triple of positive integers $a,b,c$ such that $a \geq 1$ and $b,c \geq 2$.

I would like to find an upper bound for $a+b+c$ in terms of $n = ab+bc+ac$. Clearly $a+b+c < ab+bc+ac = n$.

Is there any sharper upper bound that could be obtained (perhaps asimptotically)?

Laplacian spectrum for product graphs

2011-08-10T18:40:19Z

Let $G$ and $H$ be simple graphs.

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 http://en.wikipedia.org/wiki/Graph_product .

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

I am interested in the relation between the eigenvalues of $G$ and $H$ with respect to the eigenvalues of the other mentioned products.

The same problem has already been considered for the spectrum of the adjacency matrix and solved under the general setting of the NEPS operation.

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.

Anyone happens to know the answer or could possibly provide some literature on this matter?

Counting matrices with different determinants

2011-09-23T13:02:46Z

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.

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.

Motivation: I would like to bound (from bellow) the number of such matrices (having some additional structure) such that they have mutually different determinants.

I assume this problem is hard in general, but any pointers to relevant literature would be appreciated.

Thanks!

Asymptotics for the number of ways to sum primes such that the sum is <= n

2011-07-09T19:03:55Z

Hello!

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.

I have attempted to solve the problem in the following ways:

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. This estimate gives a worse bound than just considering the number of all partitions into odd primes of $n$. Is there any way to modify this reasoning in order to yield a better bound? Perhaps using another function instead of $\sqrt(n)?$
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}$.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. Is there any better bound for $p_p(i)$ or perhaps a superior way to analyze the integral?
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 http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html 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.

Anyone happens to see a superior solution to my problem?

Answer by Jernej for Asymptotics for the number of ways to sum primes such that the sum is <= n

2011-07-20T23:50:00Z

The question has been answered on math.stackexchange, the answer here is just for the sake of completeness.

From http://math.stackexchange.com/questions/52737/estimating-an-integral we see that an asymptotically equivalent estimate is $2\sqrt{n\log{n}}\;e^{\sqrt{n/\log{n}}}.$

Randomly contracting edges of a graph - expected number of vertices?

2011-03-28T13:58:31Z

Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.

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,..)

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?

Edit: I have removed the completely wrong attempt to estimate $E[|V(G')|]$.

The missing Euler Idoneal numbers

2010-04-10T20:37:30Z

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)

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?

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)

EDIT: 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.

Graphs of order n with a Laplacian eigenvalue of multiplicity n-1.

2011-07-11T20:52:51Z

I suspect this could be an easy one but I am not an expert in algebraic graph theory.

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.

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$ ?

I think an answer could perhaps be found here https://springerlink3.metapress.com/content/a01321p632887837/resource-secured/?target=fulltext.pdf&sid=rrxkjv553gcfwriiuwfaip55&sh=www.springerlink.com but needless to say I do not have access to the paper.

Number of $k$-partitions of $n$ into odd prime parts

2011-03-14T10:38:49Z

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}})$.

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)

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)$ ?

Answer by Jernej for Asymptotics for the number of partitions of $n$ into odd prime parts

2011-07-07T14:17:28Z

I think I found the answer I was looking for in some old paper by Erdos. http://www.renyi.hu/~p_erdos/1942-02.pdf

On page 448 he says:

Let $a_1 < a_2 < ...$ 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}}$

I just have to make sure what precisely he meant with the term density as in the classical sense http://en.wikipedia.org/wiki/Asymptotic_density 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!

Asymptotics for the number of partitions of $n$ into odd prime parts

2011-07-06T23:13:26Z

Hello!

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 - http://oeis.org/A099773 .

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.

Thanks!

Connected graphs that are not 2 connected

2011-03-18T13:13:11Z

In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics.

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

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.

Anyone happens to be aware of it?

Number of partitions of $n$ with different product

2011-03-14T13:06:02Z

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)$$.

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

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?

Comment by Jernej

2013-03-19T17:52:37Z

There is also a 41mins long talk by Hamming youtube.com/watch?v=a1zDuOPkMSw if you don't like to read the transcript.

Comment by Jernej

2013-03-12T09:51:01Z

Delio, can you cite one of these sociological papers?

Comment by Jernej

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.

Comment by Jernej

2013-02-17T13:32:11Z

The $x$-axis represents $n$ while the $y$ axis represents $\alpha(n)$

Comment by Jernej

2013-02-11T21:44:13Z

The diagonal is of course zero since I am first constructing a graph and then computing the adjacency matrix.

Comment by Jernej

2013-02-11T19:15:22Z

I always get zero with the following sage program for constructing the graph pastebin.com/0t9GHHzM

Comment by Jernej

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!

Comment by Jernej

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?

Comment by Jernej

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!

Comment by Jernej

2013-02-01T20:31:25Z

@Günter Rote Sage simply computes the subdivision of the Laplacian matrix and its determinant.

Comment by Jernej

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.

Comment by Jernej

2013-01-17T11:30:33Z

@BrendanMcKay the base graph has an automorphism group of order 2^85 * 3^32 * 5^16 * 7^16

Comment by Jernej

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?

Comment by Jernej

2013-01-16T12:41:41Z

@utdiscant In case you haven't noticed the conjecture does not hold!

Comment by Jernej

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.