Reputation
1,966
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
10 24
Impact
~42k people reached

Mar
6
asked Bounding probability of some events with bounded depdendence
Feb
26
comment Probabilistic method: vertex disjoint cycles in digraphs
@ManuelLafond Interesting. Where did you find this proof? I think one can fix it by using the asymmetric LLL perhaps at the expense of a worse constant.
Feb
26
comment Probabilistic method: vertex disjoint cycles in digraphs
@ManuelLafond I've spoken with the author and he confirmed its a mistake. One would somehow have to include this event C as well.
Feb
25
asked Probabilistic method: vertex disjoint cycles in digraphs
Feb
19
comment Does there exists a $k$-critical graph having connectivity $2$ for every $k\geq 3$?
Note that by definition, $K_k$ is $2$-connected for any $k > 2.$
Feb
18
comment For every r exists large enough n such that any graph…
Which propositions are you allowed to use then?
Feb
17
comment Finding the spanning subgraphs of a complete bipartite graph
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
Feb
17
comment Finding the spanning subgraphs of a complete bipartite graph
@chowching You can but the formula will most likely require using computer computations.
Feb
17
comment Finding the spanning subgraphs of a complete bipartite graph
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
Feb
17
comment min degree at least $n+1/2$, every edge on Hamilton cycle
I guess you must visualize this thing. Just to be sure $G/e$ denotes the graph obtained by contracting the edge $e$?
Feb
17
comment min degree at least $n+1/2$, every edge on Hamilton cycle
That should be enough. If you extend the hamiltonian cycle in $G'$ to a cycle of $G$ it uses the edge $e$
Feb
17
answered Finding the spanning subgraphs of a complete bipartite graph
Feb
15
revised Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$
deleted 69 characters in body
Feb
15
comment Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$
@ctlaltdefeat Good point. Edited my answer.
Feb
10
comment Isomorphic but not equivalent actions of a group G
@RobArthan Some lectures notes from a class I have.
Feb
10
asked Isomorphic but not equivalent actions of a group G
Feb
10
comment Graph Theory Function (Thomassen)
Btw doesn't the claim follows quickly from 1 and 2? By lemma $2$ you get a minor with large average degree provided that your graph has large girth. By picking a suitably large girth , the min degree is then large enough so that the average degree satisfies the conditions of lemma 1 giving you the desired complete graph as a minor. Where exactly do you get stuck?
Feb
10
comment Graph Theory Function (Thomassen)
@Lindsey I have a recollection of seeing this thing proven in Diestel's book.
Feb
8
answered Prove that for every connected graph $G$ of order $n$ and diameter $d$ , $\chi(G)\leq n-d+1$
Feb
7
comment A question about the interlacing of symmetric matrices (graph interlacing)
Hm.. that makes sense, thanks!