User peter - MathOverflow

Answer by Peter for Non-constructive proofs vs. efficient algorithms

2013-01-22T12:46:54Z

As a personal view - there are lots of different meanings to 'constructive'. At one end, there is the distinction between objects which can be proven to exist in ZFC but not ZF (with finer distinctions if you like logic). At the other, one has the Erdos-idea of constructive, which isn't really formally defined but should certainly imply a polynomial time algorithm which further doesn't apply brute force checking in its running. In particular this excludes for example taking a Szemeredi partition of a graph and then brute-force testing the associated (bounded size) cluster graph for some property, even though this is a valid polynomial algorithm. And then there are all the shades in between - one definition of 'constructive' is 'I know it when I see it'.

Usually the meaning of 'constructive' is just 'useful for my further proof' - so an object constructed via the axiom of choice will probably not come with any extra properties one can use to prove further facts, while an object which comes from some number-theoretical construction, even one which isn't polynomial-time constructible, usually comes with a host of extra facts one can use. And an object which has a nice cubic time algorithm to construct, but where the cubic algorithm uses brute force on a Szemeredi partition somewhere, is probably not easy to work with. A probabilistic construction is somewhere intermediate - if it's really an easy construction (take a random graph and with high probability it works) then you can read off a bunch of extra properties, but more complex constructions (nibble method, or local lemma, et cetera) don't necessarily keep properties and one has to check that the proof goes through with the extra conditions.

Answer by Peter for Large Intersecting Subsets of a Set

2012-10-25T09:07:10Z

Just to have something for all sufficiently large n, one can also take, for any small enough $\varepsilon>0$, the set $U$ to have $(2+5\varepsilon)n$ points, and then let $S'_i$ be independent random subsets of $U$ each obtained by choosing the points independently with probability $1/2-\varepsilon$. An application of Chernoff's inequality says that the size of any given $S'_i$ is concentrated close to expectation, and in particular greater than $n$. And the expected intersection of any two sets is $(1/4-\varepsilon+\varepsilon^2)(2+5\varepsilon)n$ which is smaller than $n/2$, and also by Chernoff we have good concentration. The failure probability of each of these applications of Chernoff is something like $2^{-\varepsilon^2 n}$. In particular we can certainly take a union bound over all $n+n^2$ applications (in fact we could have exponentially many $S_i$). Alternatively we can take $\varepsilon$ to be something like $\sqrt{\log n/n}$ and get $n$ sets.

So let $S_i$ be a subset of $S'_i$ of size $n$ for each $i$ and the construction is done.

Answer by Peter for Example of: K-regular graph with girth K, for a given K

2010-12-18T03:16:13Z

The easiest way to do this is as said the probabilistic method. However, for those who prefer non-random constructions, here is a greedy method.

Choose some large $n$ (you can calculate what is needed easily enough).

Start with the empty $n$-vertex graph. Add edges greedily between vertices subject to two conditions. First, the vertices you join should always have distance at least $K$ in the current graph (if not connected, then assume distance is infinite). Second, both vertices should have degree at most $K-1$.

When this procedure is forced to terminate for lack of such pairs, you have a graph with maximum degree $K$ and girth at least $K$. Now take any vertex $v$ of degree less than $K$. Look at all the vertices at distance less than $K$ from $v$ (including $v$). This set must include all the vertices of degree less than $K$, or you would not have terminated. But the set has at most $1+K+K(K-1)+K(K-1)^2+..+K(K-1)^{K-1}=C$ vertices, since the maximum degree is $K$. Similarly, the set of vertices at distance at most $2K$ from $v$ is bounded, and we can presume there are at least $KC^2$ vertices at distance more than $2K$ from $v$. Now joining greedily vertices of degree less than $K$ to these far-away vertices greedily without creating short cycles must succeed (each edge added blocks at most $C$ vertices, and there are certainly not more than $CK$ edges required).

To make this have girth exactly $K$, start with a $K$-cycle. To make it regular is a little harder: one option is to run the first procedure (starting with a $K$-cycle which we insist on preserving forever, to fix the girth) with a much higher distance requirement to join two edges (say $3K$), then after termination, identify a low-degree vertex $u$ and adding an edge to some far-away $v$ (as before) then removing some edge $vw$. Now $w$ cannot have been (before edge removal) a low degree vertex (it is too far away from the first low degree vertex) and furthermore it cannot be within distance $K$ of any remaining low degree vertex, so you can join it to a remaining low degree vertex. Rinse, repeat, assuming $n$ satisfies the parity condition for a $K$-regular graph to exist (and is large enough) you will succeed.

Answer by Peter for The probability for a sequence to have small partial sums

2010-03-03T02:51:31Z

As a lazy heuristic, one can consider the following construction.

Consider the following operation $F$ on sequences. Given a sequence $S$, we identify in $S$ the first place $q$ where the partial sum leaves $\pm t$. We identify the last place $r$ preceding $q$ in which it remains within $\pm t/2$. Then we let $F(S)$ be the sequence obtained from $S$ by swapping the signs of all elements from the $r$th place. Of course, if we apply $F$ sufficiently many times to any sequence we will obtain a sequence whose partial sums are bounded in $\pm t$. The question is how many times must we apply $F$ to a typical sequence?

We expect that for a random $S$ the value of $q-r$ is about ${t^2}/4$. Furthermore, by definition, if $q$ is the place at which the partial sums of $F$ first leave $\pm t$, and $q'$ is the first place at which the partial sums of $F(S)$ leave $\pm t$, then the last place $r'$ preceding $q'$ in which the partial sums of $F(S)$ remain within $\pm t/2$ satisfies $r'\geq q$. It follows that we expect to apply $F$ about $4n/t^2$ times to a randomly generated sequence $S$ in order to obtain a sequence whose partial sums are bounded within $\pm t$. It follows that we should expect that the probability that a random sequence has partial sums bounded by $\pm t$ is about $2^{-4n/t^2}$.

It should not be so hard to turn this into a good argument that the probability is $2^{-c_tn}$ for some $c_t$ growing roughly like $t^{-2}$ (perhaps with some log factors..).

Comment by Peter

2013-01-22T13:15:17Z

That said, one solution is to publish everything and either not list the weaker papers in your CV or (better) list them in their own section(s) with a two sentence reason for why you published but why they are not supposed to be your 'best work'.

Comment by Peter

2013-01-22T13:14:11Z

Each will be a short paper, they will not link together to make any very coherent story, and you will pick up maybe ten a year. If you publish the lot, then you may well find that you apply to places and you get rejected because 'all their work is in the Rocky Mountain Journal'. Even though the five results you really care about are in top journals - they get overlooked, or at least averaged with the flood of weak papers, where a CV listing only five results in top journals would probably get serious consideration.

Comment by Peter

2013-01-22T13:08:40Z

Actually extra papers can be detrimental, at least if you're not careful. Suppose you're working in a field where you can relatively easily find bits of new evidence towards some major conjecture which is what you actually want to prove. Furthermore these bits of evidence and ideas are not just support, you (with justification) really believe that they are building a path towards some eventual proof of the conjecture (this is not too far from Andrew King's position, actually). So do you try to publish all these results you can get?