bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 10 months |
seen | 2 days ago | |
stats | profile views | 1,260 |
I am interested in graph theory and combinatorial optimization.
Nov 21 |
comment |
SWAT vs Rioters (cops vs robbers variant)
If it is no, then see what happens for chordal graphs, then graphs of bounded treewidth. |
Nov 21 |
comment |
SWAT vs Rioters (cops vs robbers variant)
Just a few thoughts. First, it is probably best, at least to start, to insist that $S$ and $R$ are increasing functions. It seems like the graph should be SWAT-win if SWAT can eradicate the rioters given any initial configuration. Characterizing SWAT-win graphs in a very general way seems very difficult, so I would start with the obvious first steps: Trees, cycles, outerplanar graphs. Then a first question becomes: Given a weighted graph and initial numbers of SWAT/Rioters, can we determine if it is SWAT-win in polynomial time? I suspect the answer is no, but I'm not sure. |
Nov 8 |
comment |
probability distribution of hitting nodes on a finite graph random walk
Also sometimes known as small world graphs. |
Oct 24 |
answered | A k-1 edge connected k regular graph is matching covered |
Oct 18 |
comment |
Has anyone seen this graph?
In particular this graph is the smallest simple cubic graph with no perfect matching. |
Oct 17 |
comment |
What is this subclass of $k$-colorable graphs called?
I would call such a graph edge-maximal $k$-colourable. This property can be useful in induction on the number of non-edges in a graph. |
Aug 31 |
awarded | Necromancer |
Jul 27 |
comment |
Can you prove that hypergraphs with n-1 edges are partially 2 colorable?
Good! I was a little worried that Hall's theorem was the theorem you wanted to avoid. |
Jul 27 |
answered | Can you prove that hypergraphs with n-1 edges are partially 2 colorable? |
Jul 7 |
awarded | Critic |
Jun 15 |
comment |
Fast removal of weighted edges in a graph in a way such that all shortest paths are preserved
So is this equivalent to computing all-pairs shortest path, then deleting all edges not contained in some shortest path? And I don't really understand the question... use the Floyd-Warshall algorithm if you want it to be simple, and use this Sudakov result you mention if you want it to be fast. I highly doubt that you would easily be able to construct the edge set faster than that, but I may be wrong. |
Jun 13 |
answered | Combinatorial Proof of Weak Perfect Graph Theorem. |
Apr 22 |
comment |
Probability of having a bounded ratio of two types of balls in each of 'S' bins after random partitioning of a fixed number of balls
I agree with Peter. For certain values of $S$, $L$, and $A$, the Chernoff bound seems like it would be more than sufficient. |
Mar 13 |
awarded | Yearling |
Feb 12 |
comment |
Maximal clique intersection graphs
Thanks for this link... it may be useful for me, as I am also interested in maximal clique graphs (for different reasons). |
Feb 9 |
answered | Reasonable “Random” matrices to test numerical algorithms |
Feb 8 |
comment |
Is there evidence whether undergraduate math courses improve problem-solving?
Kevin, the section on the LSAT that math types tend to do particularly well on is "analytical reasoning". I can tell you from experience that if you have a fair amount of experience working through mathematical proofs, you should find this section incredibly easy. |
Feb 8 |
comment |
What is the shortest Ph.D. thesis?
I can think of at least one preeminent mathematician who does not have a Ph.D. at all. I don't think that really falls into the same set of trivia, though. |
Jan 21 |
comment |
12 and 13-bit balanced Gray codes
You mean binary Gray code? There is a construction in the Wikipedia article for Gray codes. |
Jan 19 |
comment |
definition of “exact neighborhood” [optimization]
I'm not familiar with the terminology but it's not really my area of expertise. It certainly seems like a strange choice of words, given how analogous it is to convexity. |