1,130 reputation
812
bio website andrewdouglasking.com
location Vancouver
age 33
visits member for 4 years, 1 month
seen Apr 10 at 21:04
I am interested in graph theory and combinatorial optimization.

Jan
11
comment If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?
Perhaps it would be useful to insist that $\psi(G-v)$ cannot have the same value for all $v$.
Jan
8
comment Coloring a graph by Maximum Independent Set extraction
Yes, everything you are saying is correct. In these examples, notice that when we don't have a good colouring, it is because we take a maximum stable set that does not intersect every "hard to colour" region of the graph. In these cases the "hard to colour" region is a large clique, but you could also think of it as an induced subgraph with high chromatic number. The reason that Reed's approach gets a nice bound for the fractional chromatic number is that it doesn't just take any MIS, but rather it takes every MIS with equal probability.
Jan
7
answered Coloring a graph by Maximum Independent Set extraction
Dec
10
answered Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$???
Nov
26
answered Upper bound on Shannon capacity based on independence number
Sep
10
comment number of totally different path between two nodes in graph theory
As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected.
Aug
21
comment How many mathematicians are there?
@Pete Georgia Tech might single-handedly make Georgia an overachieving state, but even 10,000 seems low.
Aug
21
comment How many mathematicians are there?
The definition would also exclude Jack Edmonds.
Aug
8
comment Is there any relationship between a tree(graph theory) and semi-metric?
Let the distance between $x$ and $y$ be the square of the sum of the weights on the path between them. Then, as you can see with a path on three vertices where both edges have weight 1, the triangle inequality does not hold. Think of any semi-metric you can form on a subset of $\mathbb R^1$. Then you can form that on an edge-weighted path.
Aug
7
answered How to partition a graph into N groups with M elements nearest?
Jun
18
comment Is there a polynomial upper bound for number of holes over following class of graphs?
No. Subdivide each edge. This leaves a triangle-free graph with Poly($n$) vertices, and at least as many holes.
Jun
1
comment Regular graph of order 50, degree 7 and Automorphism group of order 288000. How to check if it is Cayley
What is the structure of the subgraph induced by the neighbourhood of a vertex?
May
29
comment An example of when nauty, on two different platforms, gives different canonical labels for the same input graph?
Is this comment tongue-in-cheek, or has the implementation somehow been verified using formal methods? (Or do you just mean, if such an example was known it would have been fixed?)
Apr
25
awarded  Notable Question
Apr
16
comment A maximum discrepancy hypergraph 2-colouring problem
Because not every vertex is in two sets $S_i$ and $S_j$. In fact, even if no vertex is in two such sets, I don't see how the problem is trivial.
Apr
16
comment Defining fuzzy properties of crisp graphs
Agreed. The problem of how to find a good graph clustering is subject to a lot of debate, and is very closely related to this problem. Given a clustering scoring function $f$, and letting $f_o$ be the optimal score of any clustering (vertex partition) of $G$, probably $f_o/f(G)$ would be a good measurement of cliqueness. But in the end, finding the function $f$ is really a matter of taste and context.
Apr
16
comment A maximum discrepancy hypergraph 2-colouring problem
Oh yes, you're right. But there may be parallel edges, and you would have to add some fake structure to ensure that every $V_i$ matching has size 8.
Apr
16
answered Defining fuzzy properties of crisp graphs
Apr
13
comment A maximum discrepancy hypergraph 2-colouring problem
Maybe there is some equivalence, but I don't see it.
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.