1,145 reputation
813
bio website andrewdouglasking.com
location Vancouver
age 34
visits member for 4 years, 7 months
seen 2 days ago
I am interested in graph theory and combinatorial optimization.

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.
Dec
24
answered When your paper makes a borderline case for a top journal