Topics in Discrete Mathematics

by Klazar, Martin; Kratochvil, Jan; Loebl, Martin; Matousek, Jiri; Thomas, Robin

• ISBN13: 9783540336983
• ISBN10: 3540336982
• Format: Hardcover
• Copyright: 2006-09-11
• Publisher: Springer Nature

Summary

The book offers the readers a collection of high quality papers in selected topics of Discrete Mathematics, to celebrate the 60th birthday ofProfessor Jarik Nešetril. Leading experts have contributed survey and research papers in the areas of Algebraic Combinatorics, Combinatorial Number Theory, Game theory, Ramsey Theory, Graphs and Hypergraphs,Homomorphisms, Graph Colorings and Graph Embeddings.

Table of Contents

Part I Algebra, Geometry, Numbers
Countable Almost Rigid Heyting Algebras
Michael E. Adams, Aleš Pultr	3	(10)
Piecewise-Bohr Sets of Integers and Combinatorial Number Theory
Vitaly Bergelson, Hillel Furstenberg, Benjamin Weiss	13	(26)
A Generalization of Conway Number Games to Multiple Players
Christopher Cunningham, Igor Kriz	39	(26)
Two Isoperimetric Problems for Euclidean Simplices
Miroslav Fiedler	65	(6)
On Finitely Generated Varieties of Distributive Double p-algebras and their Subquasivarieties
Václav Koubek, Jiri Sichler	71	(22)
The F-triangle of the Generalised Cluster Complex
Christian Krattenthaler	93	(36)
Part II Ramsey Theory
Monochromatic Equilateral Right Triangles on the Integer Grid
Ron Graham, József Solymosi	129	(4)
One-sided Coverings of Colored Complete Bipartite Graphs
András Gyárfás, Miklós Ruszinkó, Gábor N. Sárközy, Endre Szemerédi	133	(12)
Nonconstant Monochromatic Solutions to Systems of Linear Equations
Neil Hindman, Imre Leader	145	(10)
On the Induced Ramsey Number IR(P3,H)
Alexandr Kostochka, Naeem Sheikh	155	(14)
On Explicit Ramsey Graphs and Estimates of the Number of Sums and Products
Pavel Pudlák	169	(10)
Part III Graphs and Hypergraphs
Hereditary Properties of Ordered Graphs
József Balogh, Béla Bollobás, Robert Morris	179	(36)
A Proof and Generalizations of the Erdos–Ko–Rado Theorem Using the Method of Linearly Independent Polynomials
Zoltán Füredi, Kyung-Won Hwang, Paul M. Weichsel	215	(10)
Unions of Perfect Matchings in Cubic Graphs
Tomás Kaiser, Daniel Král', Serguei Norine	225	(6)
Random Graphs from Planar and Other Addable Classes
Colin McDiarmid, Angelika Steger, Dominic J.A. Welsh	231	(16)
Extremal Hypergraph Problems and the Regularity Method
Brendan Nagle, Vojtech Rödl, Mathias Schacht	247	(34)
Part IV Homomorphisms
Homomorphisms in Graph Property Testing
Noga Alon, Asaf Shapira	281	(34)
Counting Graph Homomorphisms
Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi	315	(58)
Efficient Algorithms for Parameterized H-colorings
Josep Diaz, Maria Serna, Dimitrios M. Thilikos	373	(34)
From Graph Colouring to Constraint Satisfaction: There and Back Again
Pavol Hell	407	(28)
Part V Graph Colorings
Thresholds for Path Colorings of Planar Graphs
Glenn G. Chappell, John Gimbel, Chris Hartman	435	(20)
Chromatic Numbers and Homomorphisms of Large Girth Hypergraphs
Dwight Duffas, Vojtech Rödl, Bill Sands, Norbert Sauer	455	(18)
Acyclic 4-Choosability of Planar Graphs Without Cycles of Specific Lengths
Mickaël Montassier, André Raspaud, Weifan Wang	473	(20)
On the Algorithmic Aspects of Hedetniemi's Conjecture
Claude Tardif	493	(4)
Recent Developments in Circular Colouring of Graphs
Xuding Zhu	497	(56)
Part VI Graph Embeddings
Regular Embeddings of Multigraphs
Hubert de Fraysseix, Patrice Ossona de Mendez	553	(12)
Quadrangulations and 5-critical Graphs on the Projective Plane
Bojan Mohar	565	(16)
Crossing Number of Toroidal Graphs
János Pach, Géza Tóth	581	(10)
Regular Maps on a Given Surface: A Survey
Jozef Širán	591	(22)
Part VII
On Six Problems Posed by Jarik Nesetril
Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, Uli Wagner	613