More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal (Bolyai Society Mathematical Studies Book 15)

This volume honours the eminent mathematicians Vera Sos and Andras Hajnal. The book includes survey articles reviewing classical theorems, as well as new, state-of-the-art results. Also presented are cutting edge expository research papers with new theorems and proofs in the area of the classical Hungarian subjects, like extremal combinatorics, colorings, combinatorial number theory, etc. The open problems and the latest results in the papers are sure to inspire further research. Cover......Page 1 More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal......Page 4 Copyright page......Page 5 Table of Contents......Page 6 PREFACE......Page 8 1. SPERNER-TYPE THEOREMS......Page 10 2. LYIVI INEQUALITIES......Page 14 3. PROOF OF THE MAIN THEOREMS......Page 16 4. CONSEQUENCES......Page 19 5. THE MAXIMUM NUMBER OF COMPOSITIONS......Page 21 REFERENCES......Page 24 A QUICK PROOF OF SPRINDZHUK'S DECOMPOSITION THEOREM......Page 26 REFERENCES......Page 32 1. INTRODUCTION......Page 34 2. DISCREPANCY OF GRAPHS......Page 36 3. HYPERGRAPH DISCREPANCY......Page 43 4. SUBGRAPH DISCREPANCY......Page 52 REFERENCES......Page 57 1. INTRODUCTION......Page 58 2.1. Variants of Euler's formula......Page 60 2.2. Other lower bounds......Page 61 2.3. Drawings, upper bounds......Page 62 3. RESULTS AND PROBLEMS ON COMPLETE BIPARTITE GRAPHS......Page 63 3.2. Exact results for complete bipartite graphs......Page 64 3.3. Conjectured exact results for complete bipartite graphs......Page 68 3.4. The best known drawings for other complete bipartite graphs......Page 71 4.1. Complete graphs......Page 73 4.2 . Hypercubes......Page 74 4.3. Meshes......Page 75 REFERENCES......Page 76 AN EXERCISE ON THE AVERAGE NUMBER OF REAL ZEROS OF RANDOM REAL POLYNOMIALS......Page 80 1.THE GENERAL SETTING......Page 81 2. A SPECIAL CASE......Page 82 3. A FIRST RES ULT......Page 84 4. COMMENTS......Page 85 5. RANDOM SEQUENCES AND DETERMINISTIC SEQUENCES......Page 87 6. THE PAPERFOLDING CASE AND A GENERAL THEOREM......Page 89 REFERENCES......Page 92 1. INTRODUCTION......Page 94 3. Cons tructive characterization......Page 95 2. RELATIONS BETWEEN OLD RESULTS......Page 99 2.1. Splitting and augmentation......Page 101 2.2. Connectivity orientation and augmentation......Page 103 2.3. Constructive characterization and splitting......Page 106 3. SPLITTING AND DETACHMENT......Page 107 3.1.1. Constructive characterizations.......Page 108 3.1.2. Orientation.......Page 110 3.1.3. Augmentation.......Page 112 3.2. Directed splitting......Page 113 3.3. Undirected detachment......Page 114 3.4. Directed detachment......Page 118 4. UNCROSSING-BASED RESULTS......Page 119 4.1. Orientations and augmentations through submodular flows......Page 121 4.2. Connectivity orientation and augmentation combined......Page 125 4.3. Directed edge-connectivity augmentation......Page 130 5. CONSTRUCTIVE CHARACTERIZATIONS......Page 131 6. HYPERGRAPHS......Page 134 6.1. Directed hypergraphs......Page 137 REFERENCES......Page 138 1. INTRODUCTION......Page 144 II. PRODUCTS OF CONSECUTIVE INTEGERS......Page 145 III. PRODUCTS OF CONSECUTIVE TERMS IN ARITHMETIC PROGRESSION......Page 148 IV. AN APPLICATION OF THEOREMS 3 AND 4......Page 150 V. THE METHOD OF PROOFS OF THEOREMS 1 TO 4......Page 151 REFERENCES......Page 154 1. INTRODUCTION......Page 158 2. THE THEOREM FOR LOCALLY COMPACT SPACES......Page 159 3. A POSSIBLE GENERALIZATION......Page 166 4 . STATIONARY SET DECOMPOSITION......Page 171 REFERENCES......Page 175 1. INTRODUCTION......Page 176 2.PRELIMINARIES......Page 177 3. DIRAC-TYPE BOUNDS......Page 179 4. GALLAI-TYPE BOUNDS......Page 183 5. CRITICAL GRAPH S WITH NO LARGE CLIQUES......Page 185 6. CRITICAL HYPERGRAPHS WITH FEW EDGES......Page 186 7. ON CRITICAL SIMPLE HYPERGRAPHS......Page 189 8. VARIATIONS: PANCHROMATIC AND STRONG COLORINGS......Page 192 REFERENCES......Page 195 1. INTRODUCTION......Page 200 2.1. Random graphs......Page 202 2.2. Thomason's jumbled graphs......Page 205 2.3. Equivalent definitions of weak pseudo-randomness......Page 207 2.4. Eigenvalues and pseudo-random graphs......Page 212 2.5. Strongly regular graphs......Page 218 3. EXAMPLES......Page 220 4.1. Connectivity and perfect matchings......Page 228 4.2. Maximum cut......Page 231 4.3. Independent sets and the chromatic number......Page 233 4.4. Small subgraphs......Page 237 4.5. Extremal properties......Page 242 4.6. Factors and fractional factors......Page 244 4.7. Hamiltonicity......Page 247 4.8. Random subgraphs of pseudo-random graphs......Page 250 4.9. Enumerative aspects......Page 254 REFERENCES......Page 258 1. INTRODUCTION......Page 264 2. RELATIONAL STRUCTURES......Page 267 3. BOUNDED DEGREES......Page 269 4. DEGENERATED CLASSES OF GRAPHS......Page 272 5. MINOR CLOSED CLASSES OF GRAPHS......Page 274 6. BOUNDS, SUPREMA AND DUALITIES FOR FINITE STRUCTURES......Page 278 7. SUMMARY AND CONCLU DING REMARKS......Page 282 REFERENCES......Page 283 1. INTRODUCTION......Page 286 2. ORDINARY AND TOPOLOGICAL MINORS......Page 287 3. QUASI-PLANAR GRAPHS......Page 288 4. GENERALIZED THRACKLES AND THEIR RELATIVES......Page 291 5. LOCALLY PLANAR GRAPHS......Page 293 6. STRENGTHENING THEOREM 3.6......Page 294 7. STRENGTHENING THEOREM 3.7......Page 295 REFERENCES......Page 299 1.1. CNS polynomials......Page 302 1.2. Integral interpolation......Page 305 2. PROOF OF THEOREMS 1 AND 2......Page 310 REFERENCES......Page 315 1. INTRODUCTION......Page 318 2.1. Single Row Routing......Page 319 2.2. Channel Routing......Page 321 2.3. Switchbox Routing......Page 322 3. 3-DIMENSIONAL ROUTING......Page 324 3.1. The sn = 1 case......Page 325 3.2. The Sn, Sw >2 case......Page 326 REFERENCES......Page 328 1. INTRODUCTION......Page 330 2. THE EARLY DAYS......Page 331 3. VERA JOINS US (AND A CURE FOR AN INCURABLE DISEASE)......Page 333 4. RECENT DEVELOPMENTS AND UNSOLVED PROBLEMS......Page 337 REFERENCES......Page 339 1. INTRODUCTION......Page 342 2. A METHOD TO FORCE THIN LCS SPACES WITH PRESCRIBED CARDINAL SEQUENCE......Page 344 3. LIFTING THEOREM......Page 347 1. INTRODUCTION......Page 360 1.1. Background......Page 361 1.2. Recent developments......Page 362 1.3. Contents of this article......Page 363 2. INITIAL OBSERVATIONS......Page 364 3. R.ANDOM GRAPHS......Page 365 4. COMPLETE MINORS OF DENSE GRAPHS......Page 366 5. PSEUDO-RANDOMNESS AND SOS'S QUESTION......Page 368 6. THE EXTREMAL PROBLEM FOR GENERAL H......Page 371 6.1. General H minors......Page 372 6.2. Estimating '"'((H)......Page 373 7. LINKING......Page 375 8. MINORS AND GIRTH......Page 376 9. MINORS AND CONNECTIVITY......Page 378 REFERENCES......Page 379 1. ENTREE......Page 382 2. TILINGS......Page 383 3. THE FINE AND WILF THEOREM......Page 384 4. BI-SPECIAL WORDS......Page 385 5. BALANCED WORDS......Page 386 6. FRAENKEL WORDS......Page 388 7. STIFF WORDS......Page 389 8. THREE DISTANCES THEOREMS......Page 390 9. LINEAR COMP LEXITY WORDS......Page 391 10. FINE AND WILF WORDS FOR SEVERAL PERIODS......Page 393 12. BALANCEDNESS......Page 396 13. COMPLEXITY......Page 397 14. FINE AND WILF WORDS......Page 398 15. FROBENIUS ' LINEAR DIOPHANTINE PROBLEM......Page 399 16. BV-WORDS......Page 400 REFERENCES......Page 403 Discrete Mathematics, Including (combinatorial) Number Theory And Set Theory Has Always Been A Stronghold Of Hungarian Mathematics. The Present Volume Honouring Vera Sos And Andras Hajnal Contains Survey Articles (with Classical Theorems And State-of-the-art Results) And Cutting Edge Expository Research Papers With New Theorems And Proofs In The Area Of The Classical Hungarian Subjects, Like Extremal Combinatorics, Colorings, Combinatorial Number Theory, Etc. The Open Problems And The Latest Results In The Papers Inspire Further Research. The Volume Is Recommended To Experienced Specialists As Well As To Young Researchers And Students. A Unifying Generalization Of Sperner's Theorem / M. Beck, X. Wang, T. Zaslavsky -- A Quick Proof Of Sprindzhuk's Decomposition Theorem / Y.f. Bilu, D. Masser -- Discrepancy In Graphs And Hypergraphs / B. Bollobas, A.d. Scott -- Biplanar Crossing Numbers I: A Survey Of Results And Problems / E. Czabarka, O. Sykora, L.a. Szekely, I. Vrt'o -- An Exercise On The Average Number Of Real Zeros Of Random Real Polynomials / C. Doche, M. Mendes France -- Edge-connection Of Graphs, Digraphs, And Hypergraphs / A. Frank -- Perfect Powers In Products With Consecutive Terms From Arithmetic Progressions / K. Györy -- The Topological Version Of Fodor's Theorem / I. Juhasz, A. Szymanski -- Color-critical Graphs And Hypergraphs With Few Edges: A Survey / A. Kostochka -- Pseudo-random Graphs / M. Krivelevich, B. Sudakov -- Bounds And Extrema For Classes Of Graphs And Finite Structures / J. Nesetril -- Relaxing Planarity For Topological Graphs / J. Pach, R. Radoicic, G. Toth -- Notes On Cns Polynominals And Integral Interpolation / A. Pethö -- The Evolution Of An Idea -- Gallai's Algorithm / A. Recski, D. Szeszler -- On The Number Of Additive Representations Of Integers / A. Sarközy -- A Lifting Theorem On Forcing Lcs Spaces / L. Soukup -- Extremal Functions For Graph Minors / A. Thomason -- Periodicity And Almost-periodicity / A Tijdeman. Ervin Győri, Gyula O.h. Katona, László Lovász (eds.). Includes Bibliographical References.