Vanity of Vanities, all is Vanity

In the defense of plagiarism:

_ But now, reflecting further, there begins to creep into his breast a touch of fellow-feeling for his imitators. For it seems to him now that there are but a handful of stories in the world; and if the young are to be forbidden to prey upon the old then they must sit for ever in silence. _

from J.M. Coetzee somewhat strange noble prize lecture(long). If I got his point, then it applies also to research not only to writing stories.

And here is another quote by him:

_ You call those men crazy. To me they do not seem crazy at all. On the contrary, they seem all too canny, all too clear-headed. And with world-historical ambitions too. They want to turn the ship of history around, or failing that to sink her. _

from this very nice story (also long). I however deplore you not to read this story because of this quote, since it is unrelated to the main body of the story.

And here is another quote (short).

New comment on your post #388 “Gray boxes in latex”
Author : Sariel Har-Peled
Comment:
BTW, you might have to play with the values of the gray, to get results that you woudl see in the printout. I currenty use:

\fcolorbox[rgb]{0,0,0}{0.75,0.80,0.85}{

BTW, you might have to play with the values of the gray, to get results that you woudl see in the printout. I currenty use:

\fcolorbox[rgb]{0,0,0}{0.75,0.80,0.85}{

BTW, you might have to play with the values of the gray, to get results that you woudl see in the printout. I currenty use:

\fcolorbox[rgb]{0,0,0}{0.75,0.80,0.85}{

Here is a cute observation about combinatorial discrepancy which seems to be (maybe) new, but is too minor to be worth writing down. Consider a set system **(X,R)** where **X** is a set of **n** elements, and **R** is a family of **m** subsets of **X**. We would like to color the element of X by black (i.e., -1) and white (+1), such that the number of white and black points is as equal as possible in each set of **R**. Formally, the _discrepancy_ of a coloring **f:X -> {-1,+1}**, is the maximum value of **|f(U)| = | \sumu \in U f(u)** over all sets **U in R**. The discrepancy of **(X,R)** is the discrepancy realized by the coloring with the minimum discrepancy.

A classical result shows that if we randomly color the elements of **X** then, with high probability, the discrepancy of this system is **sqrt( 2n ln( 4m ) )** (just use the Chernoff inequality). A first improvement in the constant, can be achieved by partitioning the points into pairs (i.e., a matching), and coloring each pair **(p,q)** by either **(-1,1)** or **(1,-1)**, where this is decided independently for each pair. If a pair is contained inside a set **U \in R** then its contribution to the discrepancy of **U** is zero. As such, only pairs that crosses **U** contribute to its discrepancy (an edge/pair crosses a set, if one of its endpoints is in the set, and the other one is in the complement). Since the number of crossing pairs can be at most **n/2** for a set **U**, it follows that, with high probability, **(X,R)** discrepancy is **sqrt( n ln( 4m ) )** (there is in fact another way to get the same bound – think about it). This is of course all old water under the s!
enile bridge.

Here is the new (?) observation: Let us take a (perfect) random matching of the elements of **X**. It is easy to show that in expectation, each set of **R** would cross **< = n/4** edges of this matching. In fact, by a messy but unsurprising concentration argument, we have that each set of ****R** crosses **n/4 + o(n)** edges of the matching, with high probability. Plugging this into the standard argument, we have that the discrepancy of this set system is **sqrt( (n/2 + o(n)) ln( 4m ) )**. An improvement of 2 over the obvious bound. I knew you would be excited.

For more details about discrepancy, see here.

New comment on your post #388 “Gray boxes in latex”
Author : Vinh Phu
Comment:
Thanks a lot. It is very useful

Thanks a lot. It is very useful !

Thanks a lot. It is very useful !