bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 9 months |
seen | Dec 2 at 0:46 | |
stats | profile views | 1,245 |
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. |