## g_Z~i[

### Z~i[ uL^(2006N482007N319)

 2007N319()15:00-- cmwLpXȊw2K 36-205/207 R o΋Iiwwj ʓIOtɂɂ Ƃ́AOt̕ӂ𕪊т̍ŏ̂ƂłB {uł́AʓIOtɂɂčlB
 2007N31()17:00-- cmwLpXȊw2K 36-205/207 Antoine Deza (McMaster University, Canada) Colourful Simplicial Depth Inspired by Barany's colourful Caratheodory theorem, we introduce a colourful generalization of Liu's simplicial depth of a point $p$ in $R^d$ relative to a fixed set $S$ of sample points, i.e. the number of simplices generate by points in $S$ that contain $p$. We prove a parity property and conjecture that the minimum colourful simplicial depth of any core point in any $d$-dimensional configuration is $d2+1$ and that the maximum is $d^{d+1}+1$. We exhibit configurations attaining each of these depths, and apply our results to the problem of bounding monochrome (non-colourful) simplicial depth. Independently found recent quadratic lower bounds by Barany and Matousek and by Stephen and Thomas are also presented and algorithmic issues are highlighted.
 2007N219()15:00-- cmwLpXȊw2K 36-205/207 { ֍_ilwlԉȊwj K6-Minors in triangulations on surfaces 6ȏ̐nɂāASOtK_n}Ci[ƂĊ܂ރOt t͂ւƂ킩ĂĂB {uł́AK_6}Ci[ƂĊ܂ޕȖʂ̎Opt邱ƂڕWƂB ̌ƂāAˉeʁAg[X̎OpK_6}Ci[܂ނ߂ Kv\́A5_ȉ̊SOtɂlp܂܂ȂƂł邱Ƃ mĂB ɍ́AȊO̕Ȗʂ̎OpK_6}Ci[܂ނ߂̏A SulankeނOp̊SXgƂɋc_B
 2007N129()16:30-- cmwLpXȊw2K 36-205/207 Έ [kicmww@Hwȁj k-ordered graphs̈ʉ w肳ꂽ_SĒʂ悤cycleAw肳ꂽɒʂcycle݂悤ȏ ߔNĂB{uł́ÅTÖłk-ordered graphs̈ʉlA ̏ꍇɂ鎟Ɋւ\^B
 2007N122()16:30-- cmwLpXȊw2K 36-205/207 R o΋Iiwwj aƓƗƃn~gH݂̑ɂ PXWWNAFajtlowiczɂāAuaƓƗOt́A _Q̃pXTCNUOtƂĊ܂ށvƂĂB {uł́AaƓƗOtn~gH߂̏ɂċc_B
 2007N115()16:30-- cmwLpXȊw2K 36-205/207 |{ Fqicmwj ЉIID֌W Arrow ̕s\藝̊ȒPȏؖƁA el̑ID֌W single peaked ̂Ƃɂ͒l݂邱Ƃ̏ؖ^ B
 2006N1218()16:30-- cmwLpXȊw2K 36-205/207 icmww@Hwȁj Hamiltonicity of 3-connected claw-free graphs ܂܂ł claw-free Ot̃n~gɂāA 2-AA3-AA4-AAꂼ̏ꍇ ̌ȂĂB {uł͂̒ł3-Ȁꍇɂďœ_āA ̍ŐV̌ʂЉB
 2006N1211()16:30-- cmwLpXȊw2K 36-205/207 R o΋Iiwwj Relative Length of Longest Paths and Cycles ̌҂ɂāAŒŒH̒̕]Ɋւ錤sĂB ܂AŒƍŒH̒̊֌WɂĂ̌łB {uł́AɍŒƍŒH̒̍ɂāA̌ʂqׂB {́AÊ_jƌcmw̏֌Ƃ̋łB
 2006N124()16:30-- cmwLpXȊw2K 36-205/207 R jicmww@Hwȁj Aclaw-freeOtɂP_{\geq d+1}-factoȓ݂ɂ Aclaw-freeOtɂP_{\geq d+1}-factor݂邽߂ ŏ͊ɒmĂB {uł͂̊gƂĘAclaw-freeOtɂm-claw ̎w肵_ɂ݂̂Ɏ^邱Ƃɂ P_{\geq d+1}-factoȓ݂B
 2006N1127()16:30-- cmwLpXȊw2K 36-205/207 icmww@Hwȁj 5-AʃOt3-q݂̑ɂ ܂܂ł 3-A 4-AʃOẗqA ɘAqɊւĂ̌ȂĂB Ŗ{uł́A ̖ 5-AʃOtɂčlA uʐ 5-AʃOtɂ 3-q݂v Ƃ藝ؖB
 2006N1120()16:30-- cmwLpXȊw2K 36-205/207 ؑ iidCʐMww@dCʐMwȁj Ot1_폜Otqɂ {uł́AOt G 1_폜Ot k-qƂA G ̕ӘAxƂ̊֌Wl@B
 2006N1113()16:30-- cmwLpXȊw2K 36-205/207 R o΋Iiwwj Hamiltonian cycles passing through a matching un~gHvÅgłuw肳ꂽӂʂn~gHv 邽߂̔אڂQ_amĂB܂Aun~gHv ݂邽߂̂R_amĂB{uł́Auw肳ꂽӂʂ n~gHv݂邽߂̂R_aɂĊ̌ʂqׂB {́Acmw̏֌Ƃ̋łB
 2006N116()16:30-- cmwLpXȊw2K 36-205/207 ({ww) k-ended S؂݂̑ɂ Ot̑S؂kȉ̗tƂAk-ended S؂ƌĂԁB ܂A"Ot̔א2_Ŏar̂̂"Ƃ JԂē̂ÃOtr-ƌĂԁB {uł́An_̃Ot(n-1)-k-ended S؂ƂA ̃Otɂk-ended S؂݂邱ƂB ܂An_Otł(n-2)-SOtɂȂɂւ炸 ̃Otk-ended S؂ȂB {́ATU Bergakademie FreibergIngo SchiermeyerA {w̍֓ Ƃ̋łB
 2006N1030()16:30-- cmwLpXȊw2K 36-205/207 ({ww) Forbidden subgraphs and E(k,1) property on graphs OtɂāÃOt̔Cӂk+l{̓Ɨȕ e_1, e_2, c, e_{k+l}ɑ΂A"e_1, c, e_k܂݁A e_{k+1}, c, e_{k+l}܂܂Ȃ"悤ȊS}bOƂA ̃OtE(k,l)łƂB {uł́AOt̑Hɑ΂"Otm-AAH-freeȂE(k,1)ł" ƂlAH̃Ot琬ƂH=K_{1,r} (2rm-2k+1) ł邱ƂB܂AH̃Ot琬ƂÂ̈ X^[K_{1,r}ɂȂ邪Ar̒l(2rm-2k+1)ɌȂƂB "r̒l(2rm-2k+1)ɌȂ"ƂAE(0,0)ɂ l̖lۂƂ̍ق邱Ƃ킩B {́AVanderbilt UniversityMichael D. PlummerA TU Bergakademie FreibergIngo SchiermeyerA {w̍֓ Ƃ̋łB
 2006N1023()16:30-- cmwLpXȊw2K 36-205/207 Ingo Schiermeyer (TU Bergakademie Freiberg, Germany) k-colourability and forbidden subgraphs In this talk we will consider the k-colourability problem. We will show upper bounds for the chromatic number for several classes of graphs in terms of forbidden subgraphs. Especially we will show that all (K_3, P_6)-free graphs are 4-colourable. Moreover, if a (K_3, P_6)-free graph is 4-chromatic and contains no twins, then it contains the Mycielski-Grotzsch Graph as a subgraph and is a subgraph of the Clebsch graph.
 2006N1016()16:30-- cmwLpXȊw2K 36-205/207 Michael D. Plummer (Vanderbilt University, USA) On the matching extendability of graphs in surfaces A graph $G$ with at least $2n+2$ vertices is said to be $n$-extendable if every matching of size $n$ in $G$ extends to a perfect matching. It is shown that (1) if a graph is embedded on a surface of Euler characteristic $\chi$, and the number of vertices in $G$ is large enough, the graph is not 4-extendable; (2) given $g>0$, there are infinitely many graphs of orientable genus $g$ which are 3-extendable, and given $\overline g>2$, there are infinitely many graphs of non-orientable genus $\overline g$ which are 3-extendable; and (3) if $G$ is a 5-connected triangulation with an even number of vertices which has genus $g$ and sufficiently large representativity, then it is 2-extendable.
 2006N102()16:30-- cmwLpXȊw2K 36-205/207 R jicmww@Hwȁj ֎~OtƎw_ʂTCN݂̑ɂ QAOtɂĎw肳ꂽ_SĒʂ悤ȃTCN ݂邽߂̏\AũOt̑֎~vƂ ϓ_l@ĂB
 2006N719()16:30-- cmwLpXȊw2K 36-205/207 ({ww) Ot_ɂŐV̘b uSixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applicationsv ɂĔ\ꂽ̍ŐV̘bЉA ɂċc_B
 2006N713()16:00--17:30 cmwLpXȊw2K 36-207 { [imwȊwj ̕ƃfUC iÉwł̃Z~i[̃C^[lbgpj
 2006N710()16:30-- cmwLpXȊw2K 36-205/207 { ֍_ (lwlԉȊw) Ȗʂ̋Op̐Fɂ Œ肳ꂽȖʂɖߍ߂Ot̐FA ܂ApƂĖߍ߂Ot̐F̏ÉA Ȗʂ̎퐔݂̂Ɉˑ֐ɂ}邱ƂmĂB AȖʏ̋OpiׂĂ̒_􎟐̎Opj̐FɂẮA ʁAˉeʂ̏ꍇA܂AȊO̔Cӂ̋Ȗʏrepresentativity \ꍇ̂݊S肳ĂB {uł́ANC̒ق̋Op̐F̏E͂傤6ł邱ƂؖB ɁA6-FIOp̓tɂނāA̍l@^B
 2006N73()16:30-- cmwLpXȊw2K 36-205/207 c F (cmwHw) transpositionɂ\[g 0,1,2̂RȂɃ\[g邱ƂlB s鑀transpositionƂ΂镔Ɋւ邠όɌꍇA ̕Kvȑ񐔂ɂčl@B
 2006N626()17:00--18:00 cmwLpXȊw2K 36-205/207 David Avis (McGill University, Canada) A Few Million More Tight Bell Inequalities Bell's 1964 theorem has been described as "one of the profound scientific discoveries of the (20th) century". His inequality, and generalizations of it, are at the heart of quantum computation and information processing. Related inequalities have been well studied in areas such as probability theory, metric embeddings, number theory and discrete optimization in connection with cut and correlation polyhedra. I will explain this connection, and using it describe a method of generating a large number of new, distinct, tight Bell inequalities and a convex body that contains the quantum correlation set. If time permits, I will also discuss briefly how such inequalities can be used for nonlocal games. (Joint work with H. Imai, T. Ito and Y. Sasaki.) iÉwփC^[lbgps܂Bj
 2006N619()16:30-- cmwLpXȊw2K 36-205/207 R o΋Iiwwj w肳ꂽ_ʂH̒ɂ uŏdkAOt́ACӂk_ʂ钷2dȏ̕H݂v ƂmĂB kAOt͔Cӂk_ʂH݂邪A Cӂ(k+1)_ʂH݂邩͂킩ȂB ŁAuŏdkAOt́AH(k+1)_ʂ钷2d ȏ̕H݂vƂ\zɂċc_B
 2006N615()16:00--17:00 cmwLpXȊw2K 36-207 Thomas Britz (University of New South Wales, Australia) Matroids, codes, and designs u iÉwł̃Z~i[̃C^[lbgpj
 2006N612()16:30-- cmwLpXȊw2K 36-205/207 i{wwj Ot̒_AxAX^[t[Aŏ2-factoȓ݂ɂ {uł́A5/22̍uœꂽʂɉA ^ꂽ2̐ n \ge 3 ,k \ge 2 ɑ΂A uOtK_{1,n}-t[Ak-_AłƂ2-factoȓ݂ۏ؂v ߂̍ŏɊւőPȏ^藝ЉB {́AUniversity of OtagoRobert E. L. AldredA ȑw̍]ÔAcmw̑cOA{w̍֓ Ƃ̋łB
 2006N65()16:30-- cmwLpXȊw2K 36-205/207 Ê_ j Pan-factorial Property in Regular Graph [ɂACӂ̕ӂɑ΂̕ӂ܂1-factorʐ̘Ar-Otɂ́ACӂ̕ӂ܂k-factorƊ܂܂Ȃk-factor(0
 2006N529()16:30-- cmwLpXȊw2K 36-205/207 ] m (lww@w) K_6 Minors in triangulations on the torus ܂ł̌ŁA ˉeʏ̎Op G K_6}Ci[ƂĎ߂̕Kv\́A GK_4-lp𕔕OtƂĊ܂܂ȂƂł邱ƂmĂB {uł́Ag[X̎Op G K_6}Ci[ƂĎKv\́A GK_5-lp𕔕OtƂĊ܂܂ȂƂ藝ؖB ̏ؖɂ́AOp̊SXgpB 񓾂ꂽ藝̉pƂāÂQ̋ȖʂOpOtɑ΂āA Hadwiger's Conjecture n=6 ̏ꍇ藧ƂeՂɊmFłB
 2006N522()16:30-- cmwLpXȊw2K 36-205/207 i{wwj Ot̕ӘAxAX^[t[Aŏ2-factoȓ݂ɂ {uł́A^ꂽ2̐ n \ge 4 ,k \ge 2 ɑ΂A uOtK_{1,n}-t[Ak-ӘAłƂ2-factoȓ݂ۏ؂v ߂̍ŏɊւőPȏ^藝ЉB {́AUniversity of OtagoRobert E. L. AldredA ȑw̍]ÔAcmw̑cOA{w̍֓Ƃ łB
 2006N515()16:30-- cmwLpXȊw2K 36-205/207 i{wwj X^[t[OtɂAӘAx2-factoȓ݂ɂ {uł́A OtK_{1,n}-t[ł鎞A2-factoȓ݂ۏ؂邽߂ ӘAxɊւőPȏ^藝ЉB{́AUniversity of Ot agoRobert E. L. AldredA{w̍֓Ƃ̋łB
 2006N58()16:30-- cmwLpXȊw2K 36-205/207 icmww@Hwȁj Ot̘AxƓƗɊւ鎟ɂ uw肵_SĒʂHv݂邽߂̏\ɂẮA uAx3_avɊւĂ͂łɒmĂB ŁA{uł͂̉Ƃčlꂽ uAxƓƗ4_avɊւɂċc_B
 2006N51()16:30-- cmwLpXȊw2K 36-205/207 c OicmwHwj Toughness of K_{a,t}-minor-free graphs It is well known that every 3-connected K_{3,3}-free graph is planar, and hence is (1/2)-tough. As a generalization of this fact, we prove the following theorem: Let t\ge a\ge 3 be integers. Then, there exists a positive constant f(a,t) such that every a-connected K_{a,t}-minor-free graph is f(a,t)-tough. This is a joint work with G. Chen, K. Kawarabayashi and B. Mohar.
 2006N424()16:30-- cmwLpXȊw2K 36-205/207 icmww@Hwȁj w_ƎwӂʂӎxzHɂ  Bondy ́uӎxzH݂̑ۏ؂鎟av Ɋւ錋ʂB gA uw_ƎwӂSĒʂ悤ȕӎxzH ݂̑ۏ؂鎟av Ɋւċc_B
 2006N417()16:30-- cmwLpXȊw2K 36-205/207 R jicmww@Hwȁj ֎~OtƎw_ʂTCN݂̑ɂ QAOtclawP_6UOtƂĊ܂܂ȂȂ΁A ̃OtɃn~gTCN݂ƂƂ͊ɒmĂB {uł͂̒藝ɊgĂƂlB
 2006N410()16:30--17:30 cmwLpXȊw2K 36-205/207 Bojan Mohar (Simon Fraser University, Canada) Coloring Graphs on Surfaces Map and graph coloring problems have been motivated by the famous Four-Color Problem. Even today, three decades after the Four-Color Problem has been solved, new fundamental theorems about colorings of graphs embedded in surfaces are discovered. Some results about usual colorings, list colorings and acyclic colorings will be presented with intention to show how combinatorial, topological and probabilistic methods interplay in this area of graph theory. (A copy of OHP sheets is available.)
 2006N48(y)11:00--12:00 cmwLpX142K 14-203(Z~i[[3) Bojan Mohar (Simon Fraser University, Canada) Hadwiger's Conjecture Hadwiger has conjectured in 1943 that every graph whose chromatic number is k contains a k-clique as a minor. He formulated this problem as an attempt to generalize the Four Color Problem without using topological notions. Hadwiger's Conjecture remains a mystery. It has been solved for values of k up to 6 and is open for k\ge 7. By many, this conjecture is considered as one of the central open problems in graph theory. The talk, which will be intended for general audience, will show some of the ideas behind this conjecture, reveal the history, and uncover some recent developments related to the Hadwiger Conjecture. (A copy of OHP sheets is available.)