Building bridges between mathematics and computer science ; ["Lovász Meetings" ; two conferences in August 2008 in Hungary, both celebrating Lovász's 60th birthday

Title Page......Page 4 Copyright Page......Page 5 Table of Contents......Page 6 Preface......Page 8 Curriculum Vitae of László Lovász......Page 11 Books:......Page 14 Research papers:......Page 15 Expository papers:......Page 27 1. Introduction......Page 29 2. The Steinitz lemma......Page 30 3. The story of the Steinitz lemma......Page 32 4. Signed sum......Page 34 5. Signing vector sequences......Page 36 6. Partitioning a sequence......Page 39 7. A transference theorem......Page 41 References......Page 42 1. Row-Column Games.......Page 44 2. Exact results.......Page 47 3. The Core-Density and the Surplus.......Page 50 4. Remarks.......Page 53 5. Regular graphs – local randomness.......Page 55 6. Can we use the Lovász Local Lemma in games?......Page 56 7. When the Lovász Local Lemma successfully predicts the truth: examples in Tic-Tac-Toe like games.......Page 58 8. How sharp is Theorem 1?......Page 65 1.......Page 67 2.......Page 70 3. Inevitable surplus is trivial.......Page 73 4. Discrepancy and variance.......Page 76 1. What is the difficulty in general?......Page 80 2. An alternative approach.......Page 81 3. Global balancing.......Page 85 4. An average argument.......Page 89 4. Proof of Theorem 2: the Upper Bound......Page 92 References......Page 99 1. Introduction......Page 100 2. Deformable Polygon Representation......Page 103 3. Construction and its Proof......Page 107 4. Mincuts and Near-Mincuts......Page 122 5. Tree Hierarchy......Page 124 6. Size of the Family......Page 129 References......Page 131 1. Introduction......Page 133 2.1. Basic cases......Page 136 2.2. Extensions......Page 140 3.1. Simultaneous coverings......Page 147 3.2. Applications to bipartite graphs and digraphs......Page 154 3.3. Algorithmic aspects......Page 156 References......Page 158 1. Introduction......Page 161 2.1. Basics......Page 164 2.2. The braid arrangement......Page 166 2.3. Cell complexes and zonotopes......Page 168 2.4. The permutohedron and the k-equal arrangements......Page 169 3.1. Basics......Page 172 3.2. Cell complexes......Page 175 3.3. Complexified R-arrangements......Page 176 4. Random Walks......Page 178 4.1. Walks on semigroups......Page 179 4.2. Walks on R-arrangements......Page 181 4.3. Walks on C-arrangements......Page 182 4.4. Walks on libraries......Page 184 4.5. Walks on greedoids......Page 189 5. Appendix......Page 193 5.1. A generalized Zaslavsky formula......Page 194 5.2. Lattice of intervals......Page 195 5.3. Interval greedoids......Page 196 References......Page 198 1. Introduction......Page 200 2. Old and New Results in the Plane......Page 201 3. Solution of Kakeya’s Problem in the Plane......Page 204 4. Applications to Dual Blocking Sets......Page 209 5. Old and New Results in Higher Dimensions......Page 211 References......Page 213 1. Introduction......Page 214 1.1. Measure triples......Page 215 1.2. SR-systems......Page 216 1.2.1. Using SR-systems to define ε-regularity.......Page 217 2. The main result......Page 219 3.1. Equitable partitions......Page 220 3.2. Regularity lemmas for k-graphs......Page 221 3.3. Regularity lemmas for the cube [0, 1]k......Page 222 3.4. Regularity lemmas for functions and matrices......Page 223 3.4.1. A regularity lemma for matrices.......Page 224 4. Proofs......Page 225 4.1. Proof of Theorem 13......Page 226 4.2. Proof of Lemma 14......Page 231 4.3. Proof of Theorem 23......Page 232 References......Page 234 1. Introduction......Page 236 1.1. Previous work......Page 238 1.2. Results......Page 241 2. Algorithm......Page 245 2.1. Parallel pancakes......Page 246 3.1. Matrix properties......Page 247 3.2. The Fisher criterion and isotropy......Page 249 3.3.1. Single Component.......Page 252 3.3.2. Mixture moments.......Page 255 3.4. Sample convergence......Page 259 4. Finding a Vector near the Fisher Subspace......Page 262 4.1. Mean shift......Page 264 4.2. Spectral method......Page 265 5. Recursion......Page 270 References......Page 275 1. Introduction......Page 277 1.1. Motivation and related work......Page 280 2. Distinguished Cycles Shorter than log n......Page 282 3. Distinguished Cycles Longer than log n......Page 288 3.1. A digression......Page 289 3.2. Back to the main proof......Page 291 3.3. A negative example......Page 295 3.4. Extensions......Page 296 4. Nontrivial Cycles of Length O(log n)......Page 298 References......Page 301 1. Introduction......Page 302 2. The Case k = l + 1......Page 305 3. The General Case......Page 307 5. Finding a Large Subset......Page 309 6. An Application to Restricted Sums......Page 311 References......Page 313 1. Introduction......Page 314 2. Proof of the Square-form Theorem......Page 317 2.1. Decoupling......Page 319 3. Proof of Theorems 2 and 3......Page 321 References......Page 323 Introduction......Page 325 Instance......Page 328 What is Known......Page 329 Extensions......Page 330 Motivation......Page 331 What is Known......Page 332 Extensions......Page 334 Task......Page 335 Extensions......Page 336 Motivation......Page 337 Task......Page 338 Extensions......Page 339 Motivation......Page 340 Task......Page 341 Importance......Page 342 Instance......Page 343 Extensions......Page 345 Motivation......Page 346 What is Known......Page 348 Importance......Page 349 What is Known......Page 350 Motivation......Page 351 Challenge......Page 352 Extensions......Page 353 Instance......Page 354 Extensions......Page 355 References......Page 356 4. Regular Partitions of Sparse Graphs......Page 361 1.1. Dense graphs......Page 362 1.2. Sparse graphs......Page 363 2. Measuring Sparsity......Page 365 2.1. Shallow minors and grads......Page 366 2.2. Shallow topological minors and top-grads......Page 368 2.3. Hajós or Hadwiger?......Page 369 2.4. Stability with respect to lexicographic product......Page 371 3.1.1. Limits.......Page 372 3.2. When is a class sparse or dense?......Page 373 3.3. Within the nowhere dense world......Page 375 3.4. Classes with bounded expansion......Page 377 3.5. Proper minor closed classes......Page 379 3.6. The full picture......Page 380 4.2. Tree-depth......Page 382 4.3. Generalized coloring numbers......Page 385 4.4. Low tree-width coloring......Page 387 4.5. Low tree-depth coloring and p-centered colorings......Page 388 4.6. Algorithmic considerations......Page 390 4.6.1. Computing a Transitive Fraternal Augmentation.......Page 391 5. Algorithmic Applications......Page 392 5.1. Subgraph isomorphism problem......Page 393 5.3. Existential first-order properties......Page 394 5.4. Dominating sets......Page 395 5.5. Induced matchings......Page 397 5.6. Vertex separators......Page 398 6.1. Restricted dualities......Page 399 6.2. Homomorphism preservation......Page 402 6.3. Richness of first order......Page 406 7.1. Polynomial dependence......Page 408 7.2.1. Classes of nowhere dense graphs.......Page 409 7.2.2. Bounded expansion classes.......Page 410 References......Page 411 1. Introduction and a Brief History......Page 419 2. n-extendability in General......Page 421 3. Matching Extension in Embedded Graphs......Page 425 4. Restricted Matching Extension: the E(m, n) Properties......Page 428 5. Variations on a Theme......Page 433 6. Bricks and Braces: a Brief Outline......Page 434 7. Pfaffian Graphs......Page 437 References......Page 440 1. Introduction......Page 447 2. Top......Page 453 2.1. The Structure of Top. An Informal Presentation......Page 457 3. Adjacent n Simplicies......Page 461 4. Which k 1 Faces are Interior to Top?......Page 462 5. Lattice Translates of Interior Simplicies......Page 464 6. Intervals in Top [g]......Page 465 7.1. Boundary Intervals in Top [g]......Page 470 8. The Behavior of Top under Continuous Changes in a0......Page 471 9. What is Next?......Page 475 References......Page 477 1. Introduction......Page 479 2. The Characterization......Page 480 3. Some Framework......Page 481 4. Derivatives......Page 483 5. Proof of Theorem 1......Page 484 6. Derivation of Szegedy’s Theorem......Page 488 7. Uniqueness of b......Page 489 References......Page 490 1. Introduction......Page 491 2. The Sum-Product Problem......Page 492 2.1. The Sum-Product graph......Page 493 2.2. The spectral bound......Page 494 3. 3-term Arithmetic Progressions......Page 495 4. Sidon functions......Page 497 5. Incidence Bounds on Pseudolines......Page 501 References......Page 504 2. Common Elements......Page 506 3. Lovász......Page 508 4. Janson......Page 511 References......Page 514 1. Introduction......Page 516 2. Freiman’s Structural Theorem......Page 520 3. Structure of Zero-Sum-Free Sets......Page 521 3.2. The structure of relatively large zero-sum-free sets......Page 522 4. Incomplete Sets......Page 523 4.1. The structure of relatively large incomplete sets......Page 524 4.2. The structure of incomplete sequences......Page 525 5. Incomplete Sets in a General Abelian Group......Page 526 6. Structures in SA......Page 528 6.1. Folkman conjectures on infinite arithmetic progressions......Page 529 6.2. Erdős conjecture on square-sum-free sets......Page 530 7. Inverse Littlewood–Offord Theorems and Random Matrices......Page 531 References......Page 533 "Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is Laszlo Lovasz, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovasz's 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers."--Jacket