bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 33 | |
visits | member for | 4 years, 1 month |
seen | Apr 10 at 21:04 | |
stats | profile views | 1,140 |
I am interested in graph theory and combinatorial optimization.
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 |
Dec 17 |
comment |
4-coloring maps of pentagons
I also think this case seems likely to be known, but sometimes these things can be surprising -- it is not known, for example, whether or not there is a 5-chromatic triangle-free graph of maximum degree 5. |
Dec 15 |
comment |
Partitioning a matrix with bounded row sums
Yes, that's what I mean. Here is the link for the original Alon-Tarsi paper springerlink.com/content/u627qn50r7013363 , but you might get more out of it by looking at the papers which cite it, for example onlinelibrary.wiley.com/doi/10.1002/jgt.20500/abstract . The proof of their result, which relates to list colourings, uses combinatorial nullstellensatz, which is useful but intimidating. Better to look at what you can do using their theorem as a black box, first. |