Impact
~105k
people reached
- 0 posts edited
- 0 helpful flags
- 97 votes cast
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)<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. |