Reputation
1,246
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
13 15
Newest
 Yearling
Impact
~105k people reached

  • 0 posts edited
  • 0 helpful flags
  • 97 votes cast
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.