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 1 hour ago

10h
comment On Shannon Capacity of graph
so your last sentence in the question makes no sense.
10h
comment On Shannon Capacity of graph
As I already said, $\lim_n\theta(G)^n=\infty$, (unless your graph has no edges), so it is not in $\mathbb{N}$.
10h
revised On Shannon Capacity of graph
added 18 characters in body
10h
comment On Shannon Capacity of graph
There is Haemers bound on $\Theta(G)$ that is sometimes better than Lovazs's one, cf. en.wikipedia.org/wiki/Shannon_capacity_of_a_graph
10h
comment On Shannon Capacity of graph
you should also talk about $\lim_n \theta(G^{...n})^{1/n}$. Indeed, $\theta(G)^n\to\infty$ as $n\to \infty$.
10h
comment On Shannon Capacity of graph
you need $(\alpha())^{1/n}$ under the limit.
2d
revised Induced subgraphs of small strongly regular graphs
rewritten from scratch
Jan
29
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...
Jan
29
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?
Jan
29
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.
Jan
29
revised Induced subgraphs of small strongly regular graphs
added 98 characters in body
Jan
28
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?
Jan
28
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.
Jan
28
comment Induced subgraphs of small strongly regular graphs
Is the number 266 simply the total number of 8-vertex graphs of maximal degree 2?
Jan
28
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...
Jan
28
revised Induced subgraphs of small strongly regular graphs
deleted 80 characters in body
Jan
28
answered Induced subgraphs of small strongly regular graphs
Jan
28
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?
Jan
28
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)$ ?
Jan
28
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).