4,484 reputation
725
bio website cs.ox.ac.uk/people/…
location Oxford, United Kingdom
age 51
visits member for 4 years, 2 months
seen 7 hours ago

1d
comment Induced subgraphs of small strongly regular graphs
7000 cases does not look as scary as 375000 cases, but still is not small. It depends of course on how big will be search trees when we extend...
1d
comment Induced subgraphs of small strongly regular graphs
Do you really need to reconstruct the whole $N(v)$ in these cases? Or just enough vertices to get a subgraph with 19 eigenvalues not equal to 2?
1d
comment Induced subgraphs of small strongly regular graphs
Did you check that each of these 7 graphs is a subgraph of one of the six 8-vertex graphs from your list of possible subgraphs for $N(v)\cap N(w)$? Anyhow, one may try to extend the neighbourhood $N_v(w)$ of $w$ in $N(v)$ and reconstruct the missing edges between $N_v(w)$ and the other 14 vertices. If it gives you something without eigenvalue 2, you're done, as you get at least 19-vertex subgraph this way.
1d
comment Induced subgraphs of small strongly regular graphs
thus you are saying that 375219 can pruned quite a bit, right? Or it's 266 subgraphs of these 6 graphs on 8 vertices?
1d
comment Induced subgraphs of small strongly regular graphs
I don't know if the condition that the neighbourhood of each vertex in each of these 375s219 subgraphs is a subgraph of one of these 6 graphs on 8 vertices is satisfied automatically, or you already checked it. But it's worth looking at, just in case.
1d
comment Induced subgraphs of small strongly regular graphs
Is the number 266 simply the total number of 8-vertex graphs of maximal degree 2?
1d
comment Induced subgraphs of small strongly regular graphs
So, how about $u\neq w\not\in N(u)$, but $w\in N(v)$? This is what you can extract from that 375219 examples...
2d
comment Induced subgraphs of small strongly regular graphs
No, I meant just that - but how do these cases depend upon $u$ and $w$ being adjacent?
2d
comment Induced subgraphs of small strongly regular graphs
Can you use your candidates to enumerate possibilities for $N(v)\cap N(u)\cap N(w)$, for $u,w\in N(v)$ ?
2d
comment Induced subgraphs of small strongly regular graphs
@Jernej : basically, it might be possible to reconstruct all the possibilities for $N(v)$ using your lists (provided they aren't very long...). And this would be almost it (again, depending upon how long the resulting list is).
2d
comment Induced subgraphs of small strongly regular graphs
in my old papers I reconstructed subgraphs induced on the common neighbours of a pair of non-adjacent vertices. But it was always the case that I knew much more about $N(v)$ than here.
Jan
26
comment Irreducibility of a polynomial
oops, sorry, voted to reopen.
Jan
26
comment Can all unit-distance graphs have their vertices at algebraic integers?
@Ilya: ah, right. And not only into a 6-wheel, but any subgraph of the hexagonal lattice. I wonder if this is the complete answer.
Jan
26
comment Can all unit-distance graphs have their vertices at algebraic integers?
@Ilya: good point. This means that $G$'s with a homomorphisms to 6-cycle is a good class, in terms of the original question. (No idea why such graphs are interesting though) :-)
Jan
26
comment Can all unit-distance graphs have their vertices at algebraic integers?
How about adding a bit of intuition, say do you know such $f$ for the triangle? (and if yes, then one immediately has $f$ for the 3-colourable graphs).
Jan
26
comment When can the group of permutations generated by the translations of a group be identical with the group of all permutations on this group?
en.wikipedia.org/wiki/Cayley%27s_theorem ?
Jan
24
comment Can a graph be reconstructed from its cycle lengths?
It seems that if you know this sequence and the adjacency matrix of the graph, then you can compute the matching polynomial, which is #P-complete.
Jan
23
comment Open access journals in number theory
IMHO a publication of a close to final version on arxiv.org is good enough for all practical purposes.
Jan
23
comment accelerate convex optimization by proximal projection
can't you just stop your quadratic optimisations early?
Jan
23
comment research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$
it's not clear what kind of order on permutations you are talking about, and, indeed, what the entries of these tables are.