Kombinatorický seminář DMI022



26.2.2003 M. Sotáková: Hra BLED.

5.3.2003 M. Sotáková: Hra BLED - dokončení. J. Černý: Geometric graphs with no self-intersecting path of length 3 (Pach, Pinchasi, Tardos, Tóth).

12.3.2002 J. Černý: dokončení z minula (konstruce geom. grafu s n vrcholy a c.n.log n hranami, který nemá žádnou sebeprotínající cestu délky 3). Kreslení vnějškově rovinných grafů v lineárně velkých 3d mřížkách. V. Jelínek: Topological graphs with no large grids (Pach, Pinchasi, Sharir, Tóth). 

19.3. V. Jelínek: dokončení.

26.3. M. Tancer: Relaxing planarity for topological graph (Pach, Radoicic, Tóth).


2.4. M. Zerola: Finding sets of points without empty convex 6-gons (M. Overmars). 

9.4. Problémy s problémky. J. Fiala: orientovaný průměr grafu. M. Klazar: počty stromů a počty 3-nekřížících se párování. P. Valtr: Conwayovy thrackly a odhady počtů hran v geometrických grafech.

16.4. T. Valla: On a list-coloring problem (S. Gravier, F. Maffray and B. Mohar).

23.4. T. Valla: dokončení.

30.4. J. Kára: úvod do Edelsbrunnerova Sjednocení koulí a jejich duálního tvaru.


příští program: pokračování...

+ Věnujte prosím vzpomínku Vlastimilu Jandovi, účastníkovi kombinatorických seminářů, který 28. března zemřel.+


Přidělené články. M. Pergel: Weak epsilon-nets for points uniformly distributed on a circle (B. Chazelle). D. štěrba: The two points theorem of Mazurkiewicz (P. Komjáth and J.H. Schmerl).  J. Kára: The union of Balls and its dual shape (H. Edelsbrunner). V. Jelínek: The Turán density of triple systems is not principal (J. Balogh). I. švejdarová: A short list color proof of Grötzsch's theorem (C. Thomassen). M. Sotáková: Description trees and Tutte formulas (R. Cori and G. Schaeffer). P. Bella: A new 3-color criterion for planar graphs (K. Diks, L. Kowalik, M. Kurowski). M. Sulovský: Girth of sparse graphs (B. Bollobás and E. Szemerédi).




Nabídka článkůk referování. J. Fiala nabízí články

A new 3-color criterion for planar graphs (K. Diks, L. Kowalik, M. Kurowski) (zadáno)

The union of Balls and its dual shape (H. Edelsbrunner) (zadáno)

Girth of sparse graphs (B. Bollobás and E. Szemerédi) 7 stran. (V článku se zkoumá horní hranice pro obvod grafu na n vrcholech s n+k hranami). (zadáno)

A Ramsey-type problem and the Turán numbers (N. Alon, P. Erdös, D. S. Gunderson, M. Molloy) 10 stran. (V článku se zkoumá varianta Ramseyova problému, kdy chceme nalézt dostatečně velké n, aby v každém hranovém k-obarvení úplného grafu na n vrcholech byl úplný podgraf na m vrcholech obarven nejvýše k-1 barvami.)

Acyclic list 7-coloring of planar graphs (O. V. Borodin, D. G. Fon-Der Flaass, A. V. Kostochka, A. Raspaud, E. Sopena) 8 stran. (Acyklické barvení grafu je takové obarvení vrcholů, že libovolné dvě barevné třídy indukují v grafu les, t.j. podgraf bez cyklů. V článku je ukázáno, že pokud má rovinný graf předepsáno 7 barev u každého vrcholu, lze z nich vybrat acyklické obarvení. Metoda používá tzv. "discharging" - česky bychom řekli "vybíjení náboje" - a rozbor případů).

M. Klazar k referování nabízí následující články. Jsou vytištěné u mě nebo si je lze stáhnout (či prohlédnout) pomocí Science Direct (odkaz je ve formě loga na stránce knihovny MFF).

J. Balogh: The Turán Density of Triple Systems Is Not Principal - Journal of Combinatorial Theory, Series A 100, 176-180 (2002). (zadáno)
Turánova hustota množiny grafů F je limita zlomků (n jde do nekonečna) lim ex(n, F) / (n(n-1)/2), kde ex(n, F) je maximální počet hran v jednoduchém grafu na n vrcholech neobsahujícím jako podgraf žádný graf z F. Erdös-Stone-Simonovitsova věta říká, že tato hustota se rovná 1-1/(p+1), kde p je nejmenší chromatické číslo grafu z F. Speciálně je T. hustota množiny grafů F rovna nejmenší T. hustotě grafu z F. V této poznámce se ukazuje, že to neplatí pro 3-regulární hypergrafy (systémy trojic). Sestrojí se systém trojic F, který má T. hustotu menší než každý jeho člen.

S. Gravier, F. Maffray and B. Mohar: On a list-coloring problem - Discrete Mathematics, Article In Press (6 stran). (zadáno)
Zkoumá se funkce f(G), která je pro graf G definovaná jako nejmenší číslo k takové, že join G a nezávislé množiny s k vrcholy není |V(G)|-vybíravý. Join dvou grafů G a H vznikne tak, že se G a H vezmou na dvou disjunktních množinách, které se pak spojí všemi možnými hranami. Graf G je p-vybíravý, pokud pro každé přiřazení p-prvkových množin barev k vrcholům G existuje funkce, která z každé množiny vybírá barvu tak, že vrcholy spojené hranou mají vždy různou barvu. Vybíravost G je nejmenší p, že G je p-vybíravý (je to zobecnění barevnosti a chromatického čísla). .

P. F. Blanchard: On Regressive Ramsey Numbers - Journal of Combinatorial Theory, Series A 100, 189-195 (2002).
Pro číslo n z N (přirozená čísla) položíme [n] = {1, 2, ..., n} a pro libovolnou množinu X symbol [X]^k označuje množinu k-prvkových podmnožin X. Funkce f z [X]^k do N, kde X je podmnožina N, je regresivní pokud pro každou A z [X]^k je f(A) menší než každý prvek A. Regresivní Ramseyovo číslo Reg^n(k) se definuje jako nejmenší přir. číslo m takové, že pro každou regresivní fukci f z [m]^n do N existuje podmnožina H množiny [m] taková, že má alespoň k prvků a f zúžená na [H]^n závisí jen na nejmenším prvku n-bodovky v argumentu (tj. když A a B jsou z [H]^n a min(A) = min(B), potom f(A) = f(B)). V této poznámce se ukazuje, že Reg^2(5) = 15, Reg^3(5) = 8, Reg^4(6) = 15, Reg^5(7) > 35 a 194 < Reg^2(6) < 5.2^{42} + 2^{39} - 1.

P. Komjáth and J.H. Schmerl: The Two Points Theorem of Mazurkiewicz - Journal of Combinatorial Theory, Series A 99, 371-376 (2002). (zadáno) V r. 1914 S. Mazurkiewicz dokázal, že existuje podmnožina roviny, která protíná každou přímku v právě dvou bodech. Autoři Mazurkiewiczovu větu zobecňují pro každý vektorový prostor nad nekonečným tělesem. Speciálně platí pro každý Eukleidovský prostor R^d.


duben 2003