bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 5 months |
seen | Aug 11 at 20:54 | |
stats | profile views | 1,185 |
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 |