User karl waugh - MathOverflow

Answer by Karl Waugh for Combinatorial Morse functions and random permutations

2012-01-20T16:08:26Z

Attempting to answer the final question, I think the following should do it but I'm not 100% certain.

By hand we can see that if n=1, that exactly 2 out of the 6 permutations satisfy the condition, making 1 a maxima. If we move to n=2, then we have to make sure 1 and 3 are both maxima, 2 being a minima will follow from these.

If we look at just the movement of numbesr 0, 1 and 2, and 'restrict' the permutations to these - aka if they go to 0, 4, 3 then we can treat that as 0, 2, 1 by lowering values until they're in the range - then it isn't hard to see that thus 1/3rd of permutations make 1 a maxima, and that a 1/3rd will make 3 a maxima. Thus $p_2 \le 1/9$.

A similar arguement should be able to show that $p_n \le (1/3)^n$ which will satisfy your claim.

Answer by Karl Waugh for Can you hide a letter without losing information?

2011-09-25T15:31:07Z

This is just a thought, and I am going to re-check I have understood the problem first: Your protocol (binary solution) works because in $T$ the triples $(x, z, y)$ appear with every combination of $x$ and $y$ exactly once and because for every $w \in \Sigma^8$ there exists an element of $T$ such that $w$ contains at least one $xzy$ as a substring. So if $z$ is replaced by $\Delta$ then $w$ contains $x \Delta y$ and so $x \Delta y$ uniquely defines $\Delta$ as $z$ for a triple $(x, z, y) \in T$.

And you're claiming that this is extended beyond $k = 2$.

So assuming I understand that correctly, what you need to make it work for bigger alphabets, is again a table $T$ consisting of triples $(x, z, y)$, with $x, y \in \Sigma^k$ where every combination of $x$ and $y$ occur, and for some $B(k)$ every $w \in \Sigma^{B(k)}$ contains some $xzy$ as a substring. Then there should be some Ramsey style theorem to find $B(k)$. Can you clarify why your original method doesn't extend to larger alphabets?

Another thought is if you can create a table $T$ for any $k$ with $\mid \Sigma \mid = 2$, then for $ \mid \Sigma'\mid = 2^n$ and $k'$ why don't you take $k = n k'$ and then generate $T$,and $T$ contains triples $(x, z, y)$ such that every combination of $x$ and $y$ occurs with a unique $z$ in between, then each $x \in \Sigma^{k}$ is equivalent to an $x' \in \Sigma'^{k'}$ as $k = nk'$. You actually can replace a 'short string' if this works,ie. of length $n$. I'm not 100% sure if this actually works, but I think if you increase $B$ then the substring relation should still hold.

Answer by Karl Waugh for Icon Arrangement on Desktop

2011-08-18T23:29:01Z

If you added another condition on the problem, namely that rather than just requiring a single occurrence of a rectangle of i elements, but instead to require all non-symmetrical occurrences

(so for i=3, you require there to be a 3 x 1 rectangle containing 3 elements as well as a 2x2 rectangle containing 3 elements)

(for i=4 a 4x1 rectangle, a 3x2 rectangle with an L shape in it and a 2x2 full rectangle) etc.

I believe that would reduce the problem to "placing" each of these rectangles in the 'big square' so that they all agree. Which if easily solved would place lower bounds on the problem as it stands.

This might not help but I feel it should. (I'm sorry this isn't an actual answer but I can't post it as a comment)

my other feeling is that if you wrap around it might be easier to solve?

Answer by Karl Waugh for Expected number of pinballs to light up all 3 channels

2010-09-21T12:08:03Z

After 3 balls you are either at all lit up, or 1 lit up. Hand calculations give these probabilities at 2/9ths and 7/9ths respectively. If you throw another ball you can't be all lit up, so throw 2 more in. There are 9 ways these 2 balls can land. 3 of these options will take all lit up to all lit up (namely they both fall in the same hole) and 2 of these options will take 1 lit up to all lit up (they fall in one whole then the other - both ways round). And as there are either all lit up or 1 lit up at this stage this is all that can happen.

So if the probability of all lit up at the one possible time is p, then at the next possible time is 3p/9 + 2(1-p)/9 = p+2/9

this value converges on a quarter as (1/4 + 2)/9 = (9/4)/9 = 1/4

Colourings of Graphs with extra conditions

2010-07-08T16:20:35Z

As a phd-student I've wandered into a question of colourings of graphs and wondered what was known about them.

Given a finite graph G, where the maximum degree of a vertex is d, I'm interested in colourings where not only are no adjacent vertices the same colour, but also that no vertex has two neighbours of the same colour. [in other words, a vertex and all vertices adjacent to it, are all coloured distinctly]

It's easy to see that the number of colours is at least d + 1, and I'm interested in when this is this actual number of colours needed. (although information on the general case is also of interest)

Also within my work I am mainly looking at regular graphs. But again, that is merely the cases I'm working with and information, thoughts, references on the general case would be muchly appreciated.

To pose it as specific questions:

When can a graph G be coloured, as above, with only d + 1 colours?

When can a regular graph G be coloured, as above, with only d + 1 colours?

Is it NP-Complete to find such colourings? (I feel it is because it seems similar to edge colourings)

Answer by Karl Waugh for Intervals with large numbers of primes

2010-05-26T18:17:42Z

In some sense you're going to want to take n small as the difference between $\pi$(n) and $\pi$(n+k) is going to shrink as n gets large.

I know there are some results where the difference between $\pi$(n) and li(n) is bounded, so combinations of those may give you a bound. Wikipedia (ever reliable source) claims that

|$\pi (n) - li(n) $|$ \le \frac{\sqrt{x}ln(n)}{8\pi}$

is a result of Lowell Schoenfeld. (it says it assumes the Riemann hypothesis, so take it or leave it as you will) but then you could bound $\pi(n+k) - \pi(n)$. I don't know how well this works

Answer by Karl Waugh for Given n k-element subsets of n, is there a small subset A of n which intersects them all?

2010-05-19T16:20:42Z

Do you want to know the size of A without having to look at what is in C, just looking at n and k?

If you do, you can easily find a few bounds on the size of A.

Lets call the sets in C, $C_1, C_2$ etc. and if we define $C_1 = {1, 2, ... k }$ and then $C_2 = {k+1, k+2, ... 2k }$ etc obviously upto $C_{\lfloor \frac{n}{k} \rfloor}$ and define the rest of them to be whatever you like (as long as you use the last few elements). Then if A intersects all of the sets in C, then it must contain at least 1 element from the first k, one from the second k etc. so must have at least n/k elements.

If you actually have particular sets of C and would like to find the A as small as possible, then you could try some algorithm that tries to home in on the set. Something such as:

Relabel 1, 2, ... n such that 1 appears in more (or the same) number of sets in C as 2 does, and so on. So set $A_1 = {1, 2, ... n }$ So given $A_i$, take the highest element x of $A_i$ such that for each set $C_i$ with x in $C_i$ then $A \cap C_i \ge 2$. Then set $A_{i+1} = A_i - x$.

I hope those two ideas help.

Answer by Karl Waugh for Definition of a strange attractor.

2010-05-08T16:55:07Z

"Sensitive dependence on initial conditions" is the term I remember most clearly. Which I believe is defined as, for any epsilon (e) and delta (d)- two positive real values there exists an n (natural number)s.t. |x - y| < e => | f^n (x) - f^n (y) | > d

so here it the point is that if e is small and d big, then you can eventually make iterates of x and y far apart.

Unfortunately this obviously holds for functions as simple as f(x) = 2x so sensitive dependence on initial conditions doesn't imply chaos. but is necessary.

so a "Strange Attractor" must be an attractor, and must be "strange" which is a adjective rather than a mathematical term, which generally means 'chaotic' which will require sensitive dependence on initial conditions.

Comment by Karl Waugh

2012-01-20T22:13:50Z

I see. My answer was to the similar question of "all even values being minima and all odd values maxima" rather than all minima being even. I still believe you could adjust the idea, considering the probability of each even point being either a minima or a 'through point'