bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 5 months |
seen | Aug 11 at 20:54 | |
stats | profile views | 1,192 |
I am interested in graph theory and combinatorial optimization.
Apr 13 |
comment |
A maximum discrepancy hypergraph 2-colouring problem
Note that even if we replace 8 with $2k$ and ask the corresponding question for large $k$, the Local Lemma and random partitioning doesn't work: Prob that $S_i$ fails is $> 1/(2k+1)$, and each $S_i$ can be non-independent with up to $(2k+1)(2)(2k-1)$ other sets. |
Apr 13 |
asked | A maximum discrepancy hypergraph 2-colouring problem |
Apr 9 |
comment |
Area ratio of a minimum bounding rectangle of a convex polygon
Right, in other words that the rectangle actually contains the polygon. |
Apr 8 |
answered | Area ratio of a minimum bounding rectangle of a convex polygon |
Mar 12 |
comment |
Gluing two graphs
I think you need to be more specific about your requirements. When you say there are no multiple edges, do you mean that you ignore multiple edges, or that if you identify $u$ with $a$ and $v$ with $b$, then at most one of $uv$, $ab$ is an edge? I assume you are just ignoring multiple edges. If the two sets are cliques or stable sets, then the operation is clique sum or stable set sum. Otherwise you need to be more specific about what vertex mappings are allowed (i.e. if you are identifying $V_1$ and $V_2$, which bijection you use.) |
Mar 12 |
awarded | Yearling |
Feb 28 |
comment |
Meeting management
I agree that random constructions are a fool's venture; one must pack these partitions into $K_{60}$ with density almost 1/2. Thanks for the insight Kevin. I'm surprised one can go for 11 days under slightly different circumstances. |
Feb 27 |
comment |
Meeting management
PS Jim you posted an answer where a comment would be more appropriate. |
Feb 27 |
comment |
Meeting management
Actually I wrote some code on Friday that attempted to generate a solution randomly. It failed spectacularly. I suspect that this schedule is actually impossible, and maybe some structural analysis could prove it. For example, take "person" $v_1$ and a Monday schedule 1-6, 7-12, etc. For the next four days, $v_1$ will meet with 20 other people, and there are 54 available. $v_1$ can't meet with 5 people from any other group, because they would all have to be on different days, so $v_1$ meets with $\leq 4$ people from each other group... |
Feb 25 |
comment |
Meeting management
For some reason I can't edit the question, but here goes: There are 60 people. On each of five days, the people are partitioned into ten groups of six for day-long meetings. Is it possible to find a set of five partitions such that no two people meet twice? |
Feb 25 |
answered | How to find central vertex in a graph? |
Feb 22 |
comment |
Finding local patterns in a circular list
Sorry, I meant $O(1)$ time, and $(1-\epsilon)n$ nodes. |
Feb 22 |
comment |
Finding local patterns in a circular list
Well, here is a vague set of sufficient conditions: - the pattern always holds somewhere on a circular list - the pattern always holds somewhere on a linear list with property $x$. - given a circular list or a linear list with property $x$, we can find, in $O(\plog n)$ time, a linear sublist with property $x$ containing at most $(1-\epsilon)$ of the nodes. |
Feb 21 |
comment |
A k-1 edge connected k regular graph is matching covered
Yes, I just added the missing details. Additionally I originally said "stable set polytope" when I meant to say "perfect matching polytope". Hope this helps. |
Feb 21 |
revised |
A k-1 edge connected k regular graph is matching covered
added 1113 characters in body |
Jan 6 |
comment |
Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function
So in other words, the line for $y$ is "glued to" the window, and you move the window along the $x$-axis? |
Jan 6 |
comment |
Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function
Can you use $\Theta(n)$ storage? Why not just make a queue of squares of differences. When you advance the window by 1, simply add the new square difference and subtract the square distance that disappears from the window. This is constant time per step once you spend $O(n)$ time setting up the initial window. Or do you mean that the window is moved to some position arbitrarily far away? |
Dec 9 |
comment |
Characteristics of locally triangle-free graph
This is a comment instead of an answer since I omit so many details. It's fairly easy to see that $G$ can be any tree. Fix a root and lay out the tree in such a way that the angle between any two children of a vertex is very small. If you do this with increasingly small angles as you move away from the root, you can complete the triangulation using points on an arc very far away from the tree, so that the tree is at the centre of the circle containing the arc. I believe it should be straightforward to modify the construction so that $G$ can actually be any acyclic graph. |
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. |