1,145 reputation
814
bio website andrewdouglasking.com
location Vancouver
age 34
visits member for 4 years, 8 months
seen 8 hours ago
I am interested in graph theory and combinatorial optimization.

Oct
31
awarded  Nice Answer
Oct
16
comment Is a rigid cycle a chordal graph?
No to the second question, as exhibited by a graph on five vertices and eight edges with minimum degree 3.
Jul
2
awarded  Curious
Mar
12
awarded  Yearling
Feb
6
comment Combinatorial Proof of Weak Perfect Graph Theorem.
Thanks Petr, updated the link.
Feb
6
revised Combinatorial Proof of Weak Perfect Graph Theorem.
updated link
Jan
8
comment How dense is the set of asymmetric graphs?
Is there a simple justification for your first sentence?
Dec
6
comment Expected Value for a Connected Graph
It's easier to think about this in the equivalent model of giving each vertex a uniform random real in $[0,1]$.
Nov
9
awarded  Good Question
Oct
1
answered Does the notion of graphs with vertex multiplicity exist?
Jul
29
comment Hitting all cycles with three disjoint vertex sets
Even any graph containing $K_4$ fails.
Jun
25
awarded  Tumbleweed
May
21
comment Removing edges from Erdős–Rényi graph to make two nodes disconnected
You seem to be saying that if $c = \ln n$, then the maximum degree is going to be at most $2 \ln n / \ln \ln n$. I guess that's not the case?
Apr
6
comment The probability distribution for vertex degree in a unit disc graph generated from random points on a plane
If you use an arbitrarily large plane, or even better, a sphere or torus, shouldn't the degree of a vertex just be Poisson-distributed? I don't really understand the second paragraph, so maybe it could use some clarification. Colourings of random geometric graphs has been studied quite a lot, including by user RJK, who will probably come by in the near future with a more intelligent response.
Apr
5
comment Clique number of a $k$th power of a graph in terms of maximum degree?
Yes; they are related but not equivalent problems, because you could have vertices that are not in your clique, but help to connect vertices. I think the numbers should be close but not equal. (Aside from this question, I have found a better way to solve the problem I was working on.)
Apr
3
revised Clique number of a $k$th power of a graph in terms of maximum degree?
added 151 characters in body
Apr
3
asked Clique number of a $k$th power of a graph in terms of maximum degree?
Mar
29
comment counting k-cliques not also (k+1) on random graphs
Parallel to Brendan's comment, if $k$ is larger than order $\log(n)$, the probability of $\omega(G)$ being $k+1$ is vanishingly small compared to the probability of $\omega(G)$ being $k$. I recommend looking at Chapter 7 of Random Graphs by Janson, Luczak and Rucinski. Note that since you have half the edges, looking at the size of a maximum stable set is equivalent to looking at the size of a maximum clique. You should also look at Section 1.4 if you are unfamiliar with the asymptotic equivalence of $G(n,p)$ and $G(n,m)$.
Mar
24
comment If a graph embeds in the projective plane or the torus is there a bound on the number of edge crossings it has in the plane?
There is another way to read it: What is the smallest function $f$ of $n$ such that any toroidal graph on $n$ vertices can be drawn in the plane with at most $f(n)$ crossings?
Mar
13
comment Disjoint Maximum Independent Sets in $alpha$-critical graphs
I'm pretty sure (*) fails emphatically. As evidence, consider the case in which the edges form a perfect matching. Here $n$ is the maximum stable set still, but since $n>m$ the graph is disconnected. Moreover it fails for $(m,n)=(1,2)$, and I think you should be able to prove that it fails in general using strong induction and observing the new maximum stable set when you remove an edge.