Andrew D. King
Reputation
1,251
Top tag
Next privilege 2,000 Rep.
 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. Mar 13 comment Partitioning the vertex set of a graph with a large independent set In that case, doesn't Colin provide a valid counterexample? Mar 12 comment regular hyper graph construction Generating them how? Steiner triple systems are 3-uniform and regular, for an example. 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)