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.
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. |