1,508 reputation
820
bio website
location
age 26
visits member for 3 years, 7 months
seen 21 hours ago

If you have any good math exercises to share feel free to contribute them on http://exwiki.org


2d
comment Graph containing every trees of size $n$ as subgraphs
@manuellafond It was presented by Szemerédi at the Erdos conference last year.
Jun
29
comment Complexity of counting the number of triangles of a graph
@EricTowers No. It even turns out that a faster triangle counting algorithm would result in a faster matrix multiplication algorithm!
May
28
comment $n^n$ cannot be expressed as a recurrence with polynomial coefficents
@vadim123 Hm.. I don't see how may I use that. Could you explain a bit more?
May
27
comment number of symmetries of an arbitrary graph
Then I suppose it would be good if you could describe your graphs by a formal construction.
May
27
comment number of symmetries of an arbitrary graph
If you're dealing with concrete graphs then you can use the program nauty to compute the automorphism group. If you are dealing with a specific class of graphs then maybe you can prove they have some automorphisms by the way you construct them.
May
15
comment Eigenvalues of the distance-k graph of a graph
@jamisans It appears that the distance graphs of the graphs you are studying are vertex transitive, hence (after showing this) you could apply the same argument as done on MO for $G_{n,k}.$
May
12
comment Eigenvalues of the distance-k graph of a graph
@jamisans First thing to look is if they were strongly-regular in which case the property holds (as described above) Can you perhaps post your graphs somewhere?
May
12
comment Eigenvalues of the distance-k graph of a graph
@jamisans I've edited the post and added the edges of the respective graphs. BTW there are many graphs with this property from what I can see with a computer search
May
3
comment Even bi-coloring of regular graphs
@Johannes Yes. I did not exclude disconnected graphs.
May
2
comment Even bi-coloring of regular graphs
@Johannes See the edited post.
May
2
comment Even bi-coloring of regular graphs
@jp26,@Johannes Given this it makes more sense to classify graphs that do not admit a non-trivial coloring
May
1
comment Even bi-coloring of regular graphs
@Johannes Sure - one just needs to skip the subset containing all vertices in the function isGood. Doing this one finds out that apparently there are 11 such graphs of order 9, 42 on 10 vertices and 161 on 11 vertices.
May
1
comment Even bi-coloring of regular graphs
@Johannes If I understand you correctly, you want 4-regular graphs such that they allow the described coloring? If so, then you can use the program geng (within Sagemath) for the first part and check(for small values) all possible 2-colorings of such graphs.
Apr
20
comment Determing sequence from its Dirichlet series
@Sasha Yes, I've checked these two pages before asking but somehow I am lacking the intuition to apply these ideas. Hence, do you mind elaborating a bit more please?
Apr
20
comment Odd Town Problem.
Check here for a proof with linear algebra exwiki.org/mw/index.php?title=The_Oddtown_theorem
Mar
31
comment Conjugacy classes of a subgroup of index 2.
Thank you for your explanation. Somehow I downvoted your question and I cannot upvote unless you make an edit to this post. Hence could you make a minor change so that I can correct the vote?
Mar
30
comment Conjugacy classes of a subgroup of index 2.
Hm.. what exactly do you mean by "all orbits of H\cdot x$ under conjugation with $H$?
Mar
30
comment Conjugacy classes of a subgroup of index 2.
@GerryMyerson No I don't know that theorem. How can it be applied in this case?
Mar
3
comment Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.
The claim that a simple graph of order $n$ and at least $n-1$ edges iimplies that $G$ is connected is wrong.
Mar
1
comment How do I find the lowest $k$ for which a graph is $k$-partite?
There is no way to solve this problem in polynomial time. There are various ways to approach this problem depending on the real motivation of this question.