Spring School of Combinatorics 2013 – List of papers

The template for extended abstracts can be found here.

The talks are in English, and should take no more than 90 minutes (if you want to have a significantly shorter talk, it is not a problem, but let us know beforehand so that we can schedule it). For your talk, you can use a whiteboard with markers and/or slides (we have a projector).

Series

Incidence Theorems and Their Applications

• Source: A survey by Zeev Dvir (only part two – Counting Incidences over the Reals)
• Contact person: Zuzka Safernova (one slot free)
• Description: This series is a one with geometric flavour. It deals with geometric objects and the number of incidences (intersections) that can exists between them. The stage are either the reals or finite fields, and an oft-used technique is the so-called polynomial method. The central source for this series surveys both classical and recent results.

Extremal Set Theory

• Source: Extremal Combinatorics by Stasys Jukna (chapters 9 and 10), paper
• Contact person: Martin Bohm (one slots free)
• Description: This series aims on a traditional branch of combinatorics which asks questions of the type "If F is a collection of sets having some property P, what is the maximal (minimal) size of such system?". The series will start with introduction and presentation of some classical results, using the book by Jukna, followed by new results.

Entropy Compression Method

• Source: Posts about Moser's proof by Tao and Fortnow, selected papers
• Contract person: Martin Kupec (series already full)
• Description: Entropy-Compression method is a recent technique usable in design of probabilistic algorithms. Originally, it was obtained by Moser and used for a consctructive proof of the Lovasz Local Lemma. This series aims to introduce new results using this method.

Additive Combinatorics

• Source: Lecture notes by Andrew Granville, selected papers
• Contact person: Vojta Tuma (series already full)
• Description: Additive Combinatorics is a mathematical discipline that employs techniques from many others, e.g. combinatorics, number theory, fourier analysis, etc. The questions revolve about subsets of integers or other algebraic structures employed with addition, and their properties expressible in terms of linear equations. The series will start with an exposition of classical material, followed by new results.

Individual papers

(With comments in Czechs, but both the papers and the talks are in English)

• Matthias Kriesell – Packing Steiner trees on four terminals free!
  Článek zkoumá, kdy v grafu existuje k disjunktních stromů (ne nutně koster), z nichž každý obsahuje danou čtyřprvkovou množinu. Pěkné, ne moc těžké.



• Gábor Simonyi, Gábor Tardos – On Directed Local Chromatic Number, Shift Graphs, and Borsuk-Like Graphs free!
  Lokální barevnost měří obvyklá obarvení grafu nezvyklým způsobem: místo počtu použitých barev chceme minimalizovat počet hran mezi sousedy"nejhoršího"vrcholu. Poněkud těžší, je třeba přečíst s nadhledem a nenechat se zahltit detaily.


• Don Coppersmith, Shmuel Winograd – Matrix Multiplication via Arithmetic Progressions free!
  Starší ale stále pěkné. Na to, že jde matice nxn násobit rychleji než v kubickém čase přišel už dávno pan Strassen, ale v tomhle článku se poprvé vyskytuje nová metoda: jak použít na násobení matic hustou množinu přirozených čísel, která neobsahuje tříprvkovou aritmetickou posloupnost. Pořádně vysvětlit princip (možná napřed pro uvedení do děje připomenout ten Strassenův algoritmus), a s citem podat detaily, kolik zvládnete.


• Firke, Kosek, Nash, Williford – Extremal graphs without 4-cycles taken!
  Článek v prestižním časopise od studentů, patrně někteří z nich američtí Bc! Kolik hran může mít graf bez čtyřcyklu? V prvácké diskrétce se ukazuje, že je to zhruba n^{3/2}, a pomocí projektivních rovin se zkonstruují grafy, kdy je nalezený odhad přesný, pokud je n tvaru q^2 + q + 1 pro q mocninu prvočísla. Tady se ukáže přesný odhad pro n=q^2+q, kde q je sudé (čili pro"více hodnot"). Přímočaré počítání (Jensenova nerovnost) a jednoduchá konstrukce.


• Gunnar Brinkmann, Simon Crevals, John Frye – An independent set approach to ... GPS III taken!
  Pro novou generaci GPS se připravují plány pro dráhy satelitů, přičemž je požadováno, aby mohly komunikovat i satelity mezi sebou – což nejde, když jsou moc daleko, celkem přímočaře to vede na zkoumání grafů malého průměru. Článek je silně aplikovaný (v podstatě popis toho, jak řešili NP-úplný problém), ale zato je to od lidí, kteří to opravdu dělají (dva z autorů přímo pracují pro přislušnou firmu).


• Matt DeVos, Jessica McDonald, Diego Scheide – Average Degree in Graph Powers free!
  Mocninou grafu se tady rozumí"vzdálenostní mocnina"tj. množinu vrcholů necháme, a hranou spojíme blízké vrcholy. Zkoumá se, jaký je průměrný stupeń v takém grafu. Pěkné grafové postupy, žádné hrůzy :-)


• Ernest Croot III – On a coloring conjecture about unit fractions free!
  Obarvíme přirozená čísla 2, 3, ..., b^r (b je velká konstanta) pomocí r barev, a chceme najít jendobarevnou množinu S takovou, že součet převrácených hodnot se přesně rovná 1. To řeší dávnou otázku Erdose a Grahama. Článek je celkem drsný (aspoň pro kombinatorika) – prvočíselná věta, komplexní čísla, odhady, ... Ale nepoužívá to žádnou"příliš moderní"teorii čísel, takže s trochou snahy, citu a nadšení pro teorii čísel by to mělo jít říct.


• Nathan Linial, Michael Saks, David Statter – The non-crossing graph taken!
  Jednoduše definovaný graf: vrcholy jsou všechny množiny na n prvcích, hranou jsou spojené množiny, co jsou disjunktní, nebo jedna obsažená v té druhé. V článku se zkoumá barevnost, největší klika, a další vlastnosti tohoto grafu. Není nutné říct všechno, naopak je možné rozvést některé důkazy, které jsou jenom naznačené jako snadné cvičení.


• Disjoint 3-cycles in tournaments: a proof of the Bermond-Thomassen conjecture for tournaments – Jorgen Bang-Jensen, Stephane Bessy, Stephan Thomasse free!
  Hledání disjunktních trojúhelníků v or. grafech s velkým výstupním stupněm. Moc pěkné, trochu těžší.


• Pebbling Graphs of Fixed Diameter – Luke Postle taken!
  Jednoduchá hříčka na grafech "oblázkování" spočívá v přesouvání oblázků z libovolného původního rozmístění systémem podobným přeskakování v dámě. Cílem je na jednom vrcholu umístit co nejvíce oblázků. Pěkné a krátké.


• A simpler proof for the two disjoint odd cycles theorem – Ken-ichi Kawarabayashi, Kenta Ozeki taken!
  Grafy bez liché kružnice jsou snadné na popsání – jsou to přesně bipartitní grafy. Jak vypadají grafy bez dvou disjunktních lichých kružnic? V článku se dokazuje věta (známá už dříve ale se složitějším důkazem), která tyto grafy popisuje, nejzajímavější třída takových grafů jsou asi grafy nakreslitelné na projektivní rovinu, že každá stěna má všechny stěny sudé.


• Impartial coloring games (G. Beaulieu, K. Burke, E. Duchene) free!
  Poměrně obsáhlý článek zabývající se několika variantami barevnosti grafů pojaté jako hra dvou hráčů. Pro prezentaci je možné vybrat pouze některé varianty barvení.


• The game of 3-Euclid (D. Collins, T. Lengyel) free!
  Problém je odvozen od euklidova algoritmu pro hledání největšího společného dělitele. V tomto článku se hledéní NSD tří kladných celých čísel bere jako hra dvou hráčů. Každý hráč provede nějaký krok euklidova algoritmu a konec je při nalezení NSD. Článek je krátký, trochu hravý a trochu počítací.