1,168 reputation
914
bio website andrewdouglasking.com
location Vancouver
age 34
visits member for 5 years
seen 23 hours ago
I am interested in graph theory and combinatorial optimization.

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)<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