Andrew D. King
Reputation
1,246
Top tag
Next privilege 2,000 Rep.
 Feb 22 revised Distribution of distances in permutations deleted 24 characters in body Feb 20 comment Vector chromatic number and Lovasz theta I don't have an answer, but such a graph would definitely be imperfect and I would be extremely surprised if it were vertex-transitive. Feb 20 revised Distribution of distances in permutations Gave proof for expected value Feb 20 comment Distribution of distances in permutations Yes, the permutations were generated randomly. The histogram represents 1,000,000 trials. Feb 19 revised Distribution of distances in permutations added 309 characters in body Feb 19 answered Distribution of distances in permutations Feb 7 comment complexity of dominating sets of regular graphs Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 Feb 5 comment Is the empty graph a tree? By the way, Jernej, when making contributions to Sage, boring technical questions are of the utmost importance, particularly when recursion is involved! Feb 5 comment Is the empty graph a tree? I agree, and would point out, in case anyone is uncomfortable with "disconnected" and "connected" not forming a dichotomy, that neither do "closed" and "open". Jan 15 comment Hypergraph Chromatic Number vs Degree, Clique-Size Just for the record, Bruce and I now have an easier proof of this theorem posted on arXiv, but it still uses a combination of structural and probabilistic arguments. Jan 12 awarded Organizer Jan 12 revised counting triangle free graphs edited tags Jan 11 comment If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well? Perhaps it would be useful to insist that $\psi(G-v)$ cannot have the same value for all $v$. Jan 8 comment Coloring a graph by Maximum Independent Set extraction Yes, everything you are saying is correct. In these examples, notice that when we don't have a good colouring, it is because we take a maximum stable set that does not intersect every "hard to colour" region of the graph. In these cases the "hard to colour" region is a large clique, but you could also think of it as an induced subgraph with high chromatic number. The reason that Reed's approach gets a nice bound for the fractional chromatic number is that it doesn't just take any MIS, but rather it takes every MIS with equal probability. Jan 7 answered Coloring a graph by Maximum Independent Set extraction Dec 10 answered Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$??? Nov 26 answered Upper bound on Shannon capacity based on independence number Sep 10 comment number of totally different path between two nodes in graph theory As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected. Aug 21 comment How many mathematicians are there? @Pete Georgia Tech might single-handedly make Georgia an overachieving state, but even 10,000 seems low. Aug 21 comment How many mathematicians are there? The definition would also exclude Jack Edmonds.