Here is a blog discussion of a dimension argument for this theorem.http://gilkalai.wordpress.com/2009/05/21/extremal-combinatorics-vi-the-frankl-wilson-theorem/ . The linear algebra proof of Erdos-deBruijn theorem (a great grand father of Frankl-Wilson theorem)is described among other things in this post: http://gilkalai.wordpress.com/2008/05/01/extremal-combinatorics-i/
At the moment, example 1 contains a reference to , although these are not defined until later in the article. Maybe someone with a better feeling for the material can correct this.
I'm unsure of whether this belongs in the article proper, or in a separate article, or just restricted to the comments, but of course one can also use a just-do-it method to construct a set with undesirable properties, as in a proof by contradiction. (The example I'm thinking of right now is in the usual proof of Hilbert's basis theorem, but the general trick is a common one – it's essentially used in Euclid's proof of infinitely many primes.) So the question is, where does this variation on the trick go in the Tricki?
Also a good example for uses of duality is the case: consider a sublevel set for the norm, and Minkowski-sum with a smooth and suitably symmetric convex region; its size doesn't matter! The result is an approximating symmetric convex region, dual to a norm.
Could this article perhaps have a more informative title? If you don't already know what LU factorization is, then the title gives you no clue where this tool might be helpful!
In computer science:
Algorithms are like definitions.
Invariants (used to prove algorithms correct) are properties of the algorithms.
The invariants describe the higher-level ideas in the lower-level algorithm.
Invariants are closer to the "understanding" in the algorithm than the algorithm itself.
As a set of instructions for computing something, the algorithm is superior (a computer can use it to do the computation). But for "understanding the algorithm", the invariant is key.
There could be a link somewhere among the later examples to Use topology to study your group, although I haven't thought very carefully about where it would sit best.
An example of neglecting higher order terms in a computation to simplify it is given in Tips on Physics. Page 77 of this book lists a computation by Feynman of the deflection angle of a fast moving charged particle in a central field generated by a fixed electrical charge. The calculation is short, simple and beautiful and gives the right answer up to a constant factor. His approximation ignores the interactions of the particles when they are far away, relativity and the horizontal interaction when the particles are near. He explains why it is a good idea to ignore these things. A precise computation requires at least the study of a Hamilton-Jacobi equation.
As is, it seems as if this example doesn't quite fit this page because it is not exactly an example of the method described here. But it is clearly related to the subject of this page.
Here are some further thoughts/sentences on ignoring higher order terms:
We are often confronted with problems, which may have very complicated models. When this is the case, don't go first to the most complicated model but to a simpler one that approximates the real model at least when certain parameters are close to some limit values. Do your computations first for this simple model. The solution of the simpler model can be helpful in several ways: 1) It can be an approximation to the initial model. One can then get some idea how the original solution behaves by looking at the behavior of this approximate solution. This is useful, because it gives us an idea about what we should look for in a real solution 2) Sometimes, we get super lucky and the approximate solution tells us the exact nature of the functional dependence of the real solution to some of the important parameters of the system. This seems to be the case, for example, for the deflection angle problem.
Any ideas on how and whether to incorporate these thoughts and the deflection angle example into this article or into tricki in general?
These also seem to be related to other subjects in tricki, including convergence and approximation. Perhaps, we can think about how to organize/link articles on these subjects.
I think there is an important distinction between the idea of that article and the idea of this. It's the distinction between proving a result for a few simple cases and deducing the rest, and proving it in a few special cases in order to get ideas about how to prove the general result. I think putting a link might blur this distinction in an unhelpful way.
I just noticed that there is a topic in 'What kind of problem are you trying to solve' titled 'Prove the result for some cases and deduce it for the rest'. It would be nice if we could link that topic to this article in some way.
I just want to say that this is a beautiful and very helpful article; I am learning a great deal reading it. Thank you. While at expressing feelings, thanks to everyone for writing these amazing articles. What a great resource tricki is becoming.
Thanks for the comment. I like the notation and frequently use it because it consisely states everything related to the operation (we are taking a derivative with respect to a variable.) The one you suggest () is also good I think. As for . This is common notation in many books, including Fleming and Rishel. I don't prefer it because I think it is confusing to use the same symbol to mean two entirely different things on the same page. In this case, if we use the notation, will mean the derivative of the function with respect to time and also the name of a free variable.
is a is a free variable representing a function satisfying the Euler-Lagrange equation. It probably is not a good choice of notation because as you point out upon reading it one thinks it must be related to the in its context. I changed it to . This I think causes an abuse of notation, but hopefully not a confusing one.
There was an inconclusive forum discussion about this issue (under the topic of "Linking to front pages"). If I understand the current situation correctly, at the moment if you add a parent to an article, you have to manually edit that parent article and add the link.
Download the animation from http://ditka.fmf.uni-lj.si/~andrej/curves/gowers-better.gif and insert it here. It is an animated GIF, so all that is needed is insertion of an image.
Divide and Conquer is currently a child of Estimating Integrals. However it seems that it should be a general principle that applies to many different situations. Thus it could be for example a child of Techniques for obtaining estimates which it is in a sense (it's a grandchild). However, if someone goes to the techniques for obtaining estimates and their problem has nothing to do with integrals, he/she might never end up seeing this article as its way is via Estimating Integrals. I understand that this is potentially a general problem for many different articles. They belong to many different places. Is it possible to have a more parallel structure here? That is, instead of a folder structure have a label structure (a bit like how gmail uses labels instead of folders so different things can of course belong to the same label). Of course this might already be the case without me knowing it. But in this case I guess the article divide and conquer that I'm using as an example should be linked from Techniques for obtaining estimates as well. I have another question. If I edit the article and add an extra 'parent', can a link automatically be created in the parent article? Otherwise how can one track the child from this new parent?
I suppose I was worried that some pedant might say that making everything zero kills all other terms. But I've decided not to be worried by that after all and leave the aspect of the idea to the article itself.
Actually I was thinking that I should also talk about quotients of boundary maps and that kind of thing. It could probably be done at the same sort of informal level, and might be useful for people who wanted to relate the above account to what they might have seen in an algebraic topology course.
Here is a blog discussion of a dimension argument for this theorem.http://gilkalai.wordpress.com/2009/05/21/extremal-combinatorics-vi-the-frankl-wilson-theorem/ . The linear algebra proof of Erdos-deBruijn theorem (a great grand father of Frankl-Wilson theorem)is described among other things in this post: http://gilkalai.wordpress.com/2008/05/01/extremal-combinatorics-i/
Thanks – I didn't quite make enough modifications to the earlier version of the article, but have fixed it now.
At the moment, example 1 contains a reference to , although these are not defined until later in the article. Maybe someone with a better feeling for the material can correct this.
No, I need all the to differ from all the , so that we are free to colour the red and the blue. I called them to emphasize this.
In Example 2,'.....such that no r_i is equal to any b_j.' Do you mean to say '.... such that no r_i is equal to any b_i.'?
I'm unsure of whether this belongs in the article proper, or in a separate article, or just restricted to the comments, but of course one can also use a just-do-it method to construct a set with undesirable properties, as in a proof by contradiction. (The example I'm thinking of right now is in the usual proof of Hilbert's basis theorem, but the general trick is a common one – it's essentially used in Euclid's proof of infinitely many primes.) So the question is, where does this variation on the trick go in the Tricki?
Also a good example for uses of duality is the case: consider a sublevel set for the norm, and Minkowski-sum with a smooth and suitably symmetric convex region; its size doesn't matter! The result is an approximating symmetric convex region, dual to a norm.
Could this article perhaps have a more informative title? If you don't already know what LU factorization is, then the title gives you no clue where this tool might be helpful!
In computer science:
Algorithms are like definitions.
Invariants (used to prove algorithms correct) are properties of the algorithms.
The invariants describe the higher-level ideas in the lower-level algorithm.
Invariants are closer to the "understanding" in the algorithm than the algorithm itself.
As a set of instructions for computing something, the algorithm is superior (a computer can use it to do the computation). But for "understanding the algorithm", the invariant is key.
Thank you. I will try to follow your thoughts here as I contribute to tricki articles.
A suggestion: a new article in the `help' section on `how to write tricki articles'
There could be a link somewhere among the later examples to Use topology to study your group, although I haven't thought very carefully about where it would sit best.
Do you really want to use here for multiplication? Seems a little odd to me. Why not ?
An example of neglecting higher order terms in a computation to simplify it is given in Tips on Physics. Page 77 of this book lists a computation by Feynman of the deflection angle of a fast moving charged particle in a central field generated by a fixed electrical charge. The calculation is short, simple and beautiful and gives the right answer up to a constant factor. His approximation ignores the interactions of the particles when they are far away, relativity and the horizontal interaction when the particles are near. He explains why it is a good idea to ignore these things. A precise computation requires at least the study of a Hamilton-Jacobi equation.
As is, it seems as if this example doesn't quite fit this page because it is not exactly an example of the method described here. But it is clearly related to the subject of this page.
Here are some further thoughts/sentences on ignoring higher order terms:
We are often confronted with problems, which may have very complicated models. When this is the case, don't go first to the most complicated model but to a simpler one that approximates the real model at least when certain parameters are close to some limit values. Do your computations first for this simple model. The solution of the simpler model can be helpful in several ways: 1) It can be an approximation to the initial model. One can then get some idea how the original solution behaves by looking at the behavior of this approximate solution. This is useful, because it gives us an idea about what we should look for in a real solution 2) Sometimes, we get super lucky and the approximate solution tells us the exact nature of the functional dependence of the real solution to some of the important parameters of the system. This seems to be the case, for example, for the deflection angle problem.
Any ideas on how and whether to incorporate these thoughts and the deflection angle example into this article or into tricki in general?
These also seem to be related to other subjects in tricki, including convergence and approximation. Perhaps, we can think about how to organize/link articles on these subjects.
I think there is an important distinction between the idea of that article and the idea of this. It's the distinction between proving a result for a few simple cases and deducing the rest, and proving it in a few special cases in order to get ideas about how to prove the general result. I think putting a link might blur this distinction in an unhelpful way.
I just noticed that there is a topic in 'What kind of problem are you trying to solve' titled 'Prove the result for some cases and deduce it for the rest'. It would be nice if we could link that topic to this article in some way.
I just want to say that this is a beautiful and very helpful article; I am learning a great deal reading it. Thank you. While at expressing feelings, thanks to everyone for writing these amazing articles. What a great resource tricki is becoming.
Thanks for the comment. I like the notation and frequently use it because it consisely states everything related to the operation (we are taking a derivative with respect to a variable.) The one you suggest () is also good I think. As for . This is common notation in many books, including Fleming and Rishel. I don't prefer it because I think it is confusing to use the same symbol to mean two entirely different things on the same page. In this case, if we use the notation, will mean the derivative of the function with respect to time and also the name of a free variable.
is a is a free variable representing a function satisfying the Euler-Lagrange equation. It probably is not a good choice of notation because as you point out upon reading it one thinks it must be related to the in its context. I changed it to . This I think causes an abuse of notation, but hopefully not a confusing one.
There was an inconclusive forum discussion about this issue (under the topic of "Linking to front pages"). If I understand the current situation correctly, at the moment if you add a parent to an article, you have to manually edit that parent article and add the link.
Download the animation from http://ditka.fmf.uni-lj.si/~andrej/curves/gowers-better.gif and insert it here. It is an animated GIF, so all that is needed is insertion of an image.
Thanks a lot for this clear and precise page on Dyadic decompositions. With it, I have cleared all my doubts on the subject.
greetings
Miguel
Divide and Conquer is currently a child of Estimating Integrals. However it seems that it should be a general principle that applies to many different situations. Thus it could be for example a child of Techniques for obtaining estimates which it is in a sense (it's a grandchild). However, if someone goes to the techniques for obtaining estimates and their problem has nothing to do with integrals, he/she might never end up seeing this article as its way is via Estimating Integrals. I understand that this is potentially a general problem for many different articles. They belong to many different places. Is it possible to have a more parallel structure here? That is, instead of a folder structure have a label structure (a bit like how gmail uses labels instead of folders so different things can of course belong to the same label). Of course this might already be the case without me knowing it. But in this case I guess the article divide and conquer that I'm using as an example should be linked from Techniques for obtaining estimates as well. I have another question. If I edit the article and add an extra 'parent', can a link automatically be created in the parent article? Otherwise how can one track the child from this new parent?
I suppose I was worried that some pedant might say that making everything zero kills all other terms. But I've decided not to be worried by that after all and leave the aspect of the idea to the article itself.
This title seems kind of long, even for Tricki.
How about "To find the value of a coefficient, do something that kills all other terms"
I do think that it could be useful. Perhaps it would belong under a new section heading, so as not to clutter up what you've already written.
Actually I was thinking that I should also talk about quotients of boundary maps and that kind of thing. It could probably be done at the same sort of informal level, and might be useful for people who wanted to relate the above account to what they might have seen in an algebraic topology course.