Posts Tagged ‘pseudorandom’

What’s a “locally determined graph property?”

January 1, 2010

This has nothing to do with the rest of the post, but I’ll put it here so you read it before you get bored. I’d like to thank my readers (all seven of you) for supporting this blog in the first six months or so of its existence, and hope that you’ll stick around (and be joined by hundreds of new readers…) to hear my sporadic ramblings and wild ravings in the next year. Here’s to a happy and successful 2010!

Over at MathOverflow, Gjergji Zaimi asks (in a criminally under-voted-for question): How can we obtain global information from local data in graph theory?  This is something that perhaps everyone working in or around graph theory has asked themselves, in some form, at some point — I know I have. So it’s not surprising that Gjergji’s question has received many different answers with many different interesting things to say.

I originally wanted to write a post trying to “answer” Gjergji’s question as best I could, but quickly realized the futility of that goal — it’s such a broad and deep question that I doubt if anyone could answer it concisely, and I know I couldn’t! So instead I’ll just talk about an $\epsilon$ of the question — what does it even mean, “local data?”

GILA 4: The pseudorandom case

September 19, 2009

So in the last post, we defined the discrete Fourier transform and gave some of its basic properties. At the end, we claimed that it gives us a simple notion of pseudorandomness that allows us to make rigorous the intuition that “pseudorandom subsets of $\mathbb{Z}/N\mathbb{Z}$ should have many arithmetic progressions.” Today we’re going to justify this notion of pseudorandomness, and work through this — the easy case — of the proof of Roth’s theorem for $\mathbb{Z}/N\mathbb{Z}$. At the end, we’ll sketch how to modify the method for the regular, finitary version of the theorem.