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