1,140 reputation
813
bio website andrewdouglasking.com
location Vancouver
age 34
visits member for 4 years, 4 months
seen Jul 15 at 1:07
I am interested in graph theory and combinatorial optimization.

Mar
12
comment Partitioning the vertex set of a graph with a large independent set
(I am assuming TOM means $v_1,\ldots, v_m$ are a stable set and $v_{m+1},\ldots,v_{2m}$ are a clique. Is that the case?)
Mar
12
comment Partitioning the vertex set of a graph with a large independent set
Colin, then take $m=1$ and remove two vertices, one of which is the isolated vertex.
Mar
12
awarded  Yearling
Mar
10
revised Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)
added 11 characters in body
Mar
9
revised Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)
Improved the lower bound with a new example
Mar
8
answered Does the cubic planar graph with 6 3-faces and 6 7-faces have a name?
Mar
7
asked Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)
Feb
26
comment Repertory of the different sorts of operads
Am I the only one who came in here to change "operad" to "operand"?
Feb
22
comment Distribution of distances in permutations
Take real numbers $r(1)\ldots r(n)$ chosen uniformly from $[0,1]$. Then construct a permutation $\pi$ with the property that for all $i$, $\pi(i) < \pi(j)$ if and only if $r(i)<r(j)$. Since the random reals are independently identically distributed and all distinct with probability 1, $\pi$ is a uniformly random permutation. In fact, we do not need to choose uniformly from $[0,1]$ -- we only need i.i.d. and distinct with probability 1. But for the purposes of the proof, the uniform distribution is appropriate.
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