I will keep a running log of phi-club happenings and future plans here. Please post comments about any things that I’m missing or any ideas for future agenda items!

ink_img001

Future

  • what do erdos renyi graphs with about \(1/n\) edges look like? in particular, what’s the probability that two random vertices are connected?

  • PAC learn Junta

  • finish 2-factor theorem

    • prove Hall’s theorem

  • FPT algorithm for “are there k edge-disjoint cycles”?

  • prove 2-choice hashing gets \(\log\log n\)

Dec 5:

  • started thinking about Beck Fiala (Bela-Fleck?) theorem
  • got a nice greedy algorithm that does great for \(t=2\).
  • got a greedy algorithm that does \(\log n\) in general
  • looked up the answer, its some linear-algebraic thing that we don’t really understand yet.

Nov 28:

  • proved \(\log \log n\) for the markov equilibrium state of the process when you add and delete balls
  • progress on HAM: [50,100] easy in max-degree 3

Nov 21:

Also sorry comments deleted because I had to change the date.

Today we talked about some stuff Alek read in the Parameterized Complexity book, specifically about “kernelization”.

Then we solved the following problem which is not actually related to FPT stuff, but was in the textbook because it was talking about Konig’s theorem / matching stuff:

You partition space into \(n\) equal-area school-districts and \(n\) equal-area military-districts. You want to build \(n\) pizza shops such that there is one pizza shop in every school-district and also in every military-district. Is it possible? Turns out the answer is yes. You can think of the problem as having a \(2n\)-vertex weighted-bipartite graph, with the vertices corresponding to the school-districts and military-districts. The weight is how much the districts overlap.

Then, you can ask the question, what is the minimum vertex cover for this graph? And, the answer is \(n\). Because you cover at most \(1\)-unit worth of military area per each selected school district.

But then by LP duality or something this means that there is a matching in this graph of size \(n\). And that matching corresponds to where you should put the pizza shops.

Nov 14:

  • chicken nuggets

  • quasipoly algorithm for something

  • which random graphs are bipartite?

    • \(p=\frac{\Theta(1)}{n}\) threshold
    • TODO: whats the constant dependence
    • turns out that \(p=\Theta(\frac{1}{n})\) is probably also planar threshold. we were mis-remembering what an induced minor is. seems rather important.

  • we thought about chromatic number of random graphs

  • no ideas for \(\chi>2\).

  • except, some bounds: e.g., if you have a \(K_4\) then your chromatic number is at least \(3\).

  • possible conjecture: maybe there’s just a point where you get a really high chromatic number instantly.

Nov 7:

  • Do PRGs exist? vs 1 bit adversaries?

  • we analyzed the case without a clock.

  • there are a very finite number of 2-state DFAs and also a very small number of functions on 2-state DFAs

  • if you don’t care about run-time buckets is a good idea

  • if you do care about run time then feeding like all 1s and then your random bits is maybe a good idea? it was a little bit subtle I don’t remember what ended up working

  • with a timer seems harder…

Nov 1:

  • analyzed chopsticks a bit
  • proved that you can do quadratic residosity stuff in some special cases

Oct 21:

  • thought about 2 factor theorem
  • maybe proved it for \(4\)-regular graphs.
  • Konig’s theorem: in a bipartite graph, maximum matching size = minimum vertex cover size

Oct 14:

  • bijection between 7-tuples of trees and trees
  • what other numbers work?

Oct 7:

  • union-find tried

Sept 30:

  • triangulation of a triangle, color vertices with 3 colors some color is banned on each of the edges. show that this is equivalent to Brower’s fixed point theorem which says that any function from ball to ball has a fixed point.

Aug 10:

  • 2-server on a circle

Aug 1:

  • rational approximations for numbers