Impact

~94k
people reached

- 0 posts edited
- 0 helpful flags
- 97 votes cast

Mar
5 |
comment |
Linear intersection number and coloring (not chromatic) number
What happens if you replace the colouring number with the minimum degree $+1$, or the maximum degree $+1$, or the chromatic number? |

Feb
12 |
comment |
Chromatic number of graphs of tangent closed balls
A clarification: Choose the sphere $S$ to be smallest, and subject to that choose it to be extreme. I claim without proof that if a sphere kisses 12 others of equal or greater radius, then all 13 spheres have equal radius. Furthermore the sphere kissed by 12 others has its centre in the convex hull of the other 12 centres, and therefore is not extreme (of these 13 spheres) in any direction. |

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

Feb
6 |
comment |
Combinatorial Proof of Weak Perfect Graph Theorem.
Thanks Petr, updated the 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]$. |

Jul
29 |
comment |
Hitting all cycles with three disjoint vertex sets
Even any graph containing $K_4$ fails. |

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

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

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