Category: Computer Science

Category of Networks PPT

It's interesting to find this presentation because last week as I was traveling and thinking about random things, I suddenly realized that perhaps graphs & networks are the underlying math for ways of describing our universe! We have social networks, biological systems, genealogy(family trees), entropy, lots of math objects (even knots!), brain, CFT, Feynman diagrams, … Continue reading Category of Networks PPT

Creative Ways of Communicating Research

I'm part of LYNX under the Stanford Undergraduate Research Journal this year. Here's a useful piece we received as new writers: Awesome Examples Writing Quanta Magazine (here) Nautilus (here) Asian Scientist Magazine (here) Philosophy Now (here) Podcast / Radio / Audio Radiolab (here) Cold Spring Harbor Labs Oral History Collection (here) Philosophy Bites (here) Social Science … Continue reading Creative Ways of Communicating Research

Bolloba’s First Theorem

From Don Knuth‘s Theory Lunch Talk at Stanford on Oct 6. I found a blog post talking about the exact same thing, so won’t repeat. The idea behind the proof of this rather combinatorial theorem is interesting. The main idea is to construct a nice mapping between a permutation of (1,2, …., n) and a pair of (finite) sets: (A, B) based on the elements inside the sets.

You can try to figure out and prove when the equality holds by yourself as an exercise.

When is this Theorem useful? For example, in making representative families <– so that we have better memory performance. Think about it!411ei42toel-_sx328_bo1204203200_

Too lazy D:< Plzzzz let me know if you made a nice drawing for the proof of the theorem (Shouldn’t be too hard) so that I can include your image here rather than this textbook cover.

 

Uniformly at Random

The following theorem of Bollobas is an important result from extremal set theory.  It has apparently been rediscovered several times by others.  It implies certain classical results, such as Sperner’s Theorem, and has some interesting extensions.

Theorem (Bollobas).  Let $latex A_1, ldots, A_m$ and $latex B_1, ldots, B_m$ be sequences of $latex a$-element and $latex b$-element sets respectively.  Suppose that $latex A_i cap B_i = emptyset$ and $latex A_i cap B_j neq emptyset$ whenever $latex i neq j$.  Then $latex m leq {a+b choose a}$.

Proof.  Let $latex X$ be the union of all the $latex A_i$’s and $latex B_i$’s.  Consider an arbitrary permutation $latex pi$ of $latex X$.  We claim that there is at most one pair $latex (A_i, B_i)$ such that all of the elements of $latex A_i$ precede those of $latex B_i$ in the ordering $latex pi$.  Suppose to the contrary that there are two…

View original post 301 more words