Reputation
1,251
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
13 15
Newest
 Yearling
Impact
~105k people reached

  • 0 posts edited
  • 0 helpful flags
  • 97 votes cast
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.
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...