Reputation
340
Top tag
Next privilege 500 Rep.
Access review queues
Badges
1 11
Newest
 Tumbleweed
Impact
~4k people reached

  • 0 posts edited
  • 0 helpful flags
  • 36 votes cast
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
Absolutely, I will update my post tonight to link to this answer!
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
@dtldarek Thanks, that's a great answer! For those interested, I worked through this in a lot more (painstaking!) detail here: boldlyforward.wordpress.com/2015/07/16/…
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
@john I'm not sure what you think I'm looking for, but I would actually prefer that you use your brain to answer. I don't care, and didn't specify, what type of proof you use, the point is just that coming up with a way to test the batteries isn't sufficient, you also need to prove that you can't do it in fewer trials. So if you can "easily" do it, I'd love to see it in an answer.
Jul
15
comment Brain teaser solution in Graph Theory / Ramsey Theory
Very helpful answer, but I agree with Greg, I'm not seeing the final conclusive step to the proof, and it doesn't even require a tie. Imagine for instance you have four vertices connected in a ring. They each have degree two, so we color them black. The remaining four are connected as two disjoint pairs, so each has a degree one, and is colored white. But each white connects to another white, so this configuration of six edges works. Of course, that doesn't prove that you can guarantee finding a match with six tries as required by the riddle, but I don't think this answer has proven you can't.
Jul
15
comment Brain teaser solution in Graph Theory / Ramsey Theory
@Sisi Good catch, thanks!
Jun
3
comment Name of the highest power of 2 smaller than or equal to a given number
Order of magnitude is spot on, but you do need to be clear that's is base-two, because almost evey body will interpret it as base 10.
Apr
30
comment Constructor theory distinguishability
Seems like a reasonable idea. I haven't gone back to validate your proof, but it appears sound. Thanks!
Feb
24
comment Big-O complexity of iterating over every substring
@Tryss: Thanks, would you be able to explain this a little? In fact, I actually need to add a third nested loop, which iterates j/2 times, so I'm not sure how to extrapolate from your answer to a more general solution.
Mar
1
comment Understanding group presentation as a quotient
Wow, nice answer, thanks for putting in the time! I'm going to have to put in some time studying it some more to understand it, but I think I was able to follow each step, just haven't quite pulled it all together into a conclusion yet. Also, I think there's a typo in the last paragraph: you have $fef$ listed twice in $\hat{G}$.
Feb
26
comment Show that group action is homomorphism to Symmetric group
Oh, ok. So my original formulation for the condition of homomorphism was off. I think it makes sense now, thanks!
Feb
26
comment Show that group action is homomorphism to Symmetric group
Actually, I take that back, $A_g(x)$ is not a permutation of $X$, it's an element of $X$. So how can you compose a permutation/function, $A_g$ with an element of a set, $A_f(x)$?
Feb
26
comment Show that group action is homomorphism to Symmetric group
@SpamIAm: Thanks, but I think you over estimate me. I have the axioms written out as $A(e,x) = x$ for all $x$ (where $e$ is the identity of $G$) and $A(g, A(f,x)) = A(g+f, x)$, but it's still not clear to me why this defined a homomorphism.
Feb
26
comment Show that group action is homomorphism to Symmetric group
(Thanks for updating from $h$ to $A$). So the steps to change right side, $A(g+f,x)$ into $A_g * A_f(x)$ are clear, but is that necessarily equal to $A_g(x) * A_f(x)$. I know $A_g(x)$ and $A_g$ are both permutations of X, but are they they same?
Feb
26
comment Show that group action is homomorphism to Symmetric group
@ThomasAndrews: Thanks, I've updated the question to use $A$ in place of $h$: I'm not sure why I started using $h$, must be misread something somewhere. So if $A$ is the group action, we have $A : G \times X \to X$, to it $A$ takes a two-tuple $(g,x)$ with $g \in G$ and $x \in X$.
Feb
21
comment Notation for nested sigmas (summations)
Oh, that's right, I forgot you can iterate over a set of tuples. But it doesn't really resolve the question of how to neatly define the set from which they draw, which is kind of the big problem in the originally posted example.
Feb
19
comment Enumerating cases for conditional probability
Thanks. That's nearly what I came up with as described in the question, but it is not any more clear to me why you don't need $\binom{8}{4}$ included somewhere as this is the total number of ways in which you can choose which four bits are set and which four are cleared.
Sep
11
comment Name for the sense of how many items are present
Perfect, thanks!
Jul
31
comment Non-binary Hamming codes?
Thanks for all the info, it was sufficient for me to realize that I did not have as good of an understanding of the topic as I thought. "SEC" is "single error correcting", i.e., distance-3.
Jul
31
comment Variations of the Hamming code.
I think it's worth mentioning/emphasizing that simply cutting off the first $s$ bits of the codeword only works for canonical Hamming codes (i.e., where the generator matrix begins with the identity matrix). In that case, any data word beginning with $s$ zeroes is guaranteed to produce a codeword which also begins with $s$ zeroes. But for non-canonical Hamming codes, this is not necessarily the case. Non-canonical codes can still be shortened, but it is somewhat more complicated.
Jul
31
comment Non-binary Hamming codes?
Rats, looks like I have more learning to do =). When you say it wouldn't be a Hamming code over the larger-base field, do you mean it doesn't function as SEC, or just that it is not strictly a Hamming code (for instance, because it is not a perfect code)? Because I've tested it pretty thorougly and it seems to function well as SEC. But based on your $[13, 10, 3]$ code, it looks like I'm nowhere near optimal data rate.