More sets, graphs, and numbers : a salute to Vera Sós and András Hajnal

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 Cover 1 More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal 4 Copyright page 5 Table of Contents 6 PREFACE 8 A UNIFYING GENERALIZATION OF SPERNER'S THEOREM 10 1. SPERNER-TYPE THEOREMS 10 2. LYIVI INEQUALITIES 14 3. PROOF OF THE MAIN THEOREMS 16 4. CONSEQUENCES 19 5. THE MAXIMUM NUMBER OF COMPOSITIONS 21 REFERENCES 24 A QUICK PROOF OF SPRINDZHUK'S DECOMPOSITION THEOREM 26 REFERENCES 32 DISCREPANCY IN GRAPHS AND HYPERGRAPHS 34 1. INTRODUCTION 34 2. DISCREPANCY OF GRAPHS 36 3. HYPERGRAPH DISCREPANCY 43 4. SUBGRAPH DISCREPANCY 52 REFERENCES 57 BIPLANAR CROSSING NUMBERS I: A SURVEY OF RESULTS AND PROBLEMS 58 1. INTRODUCTION 58 2. GENERAL RESULTS 60 2.1. Variants of Euler's formula 60 2.2. Other lower bounds 61 2.3. Drawings, upper bounds 62 3. RESULTS AND PROBLEMS ON COMPLETE BIPARTITE GRAPHS 63 3.1. Lower bounds for complete bipartite Graphs 64 3.2. Exact results for complete bipartite graphs 64 3.3. Conjectured exact results for complete bipartite graphs 68 3.4. The best known drawings for other complete bipartite graphs 71 4. RESULTS AND PROBLEMS ON OTHER SPECIFIC FAMILIES GRAPHS 73 4.1. Complete graphs 73 4.2 . Hypercubes 74 4.3. Meshes 75 5. CONCLUSION 76 REFERENCES 76 AN EXERCISE ON THE AVERAGE NUMBER OF REAL ZEROS OF RANDOM REAL POLYNOMIALS 80 1.THE GENERAL SETTING 81 2. A SPECIAL CASE 82 3. A FIRST RES ULT 84 4. COMMENTS 85 5. RANDOM SEQUENCES AND DETERMINISTIC SEQUENCES 87 6. THE PAPERFOLDING CASE AND A GENERAL THEOREM 89 7. APOLOGY 92 REFERENCES 92 EDGE-CONNECTION OF GRAPHS, DIGRAPHS, AND HYPERGRAPHS 94 1. INTRODUCTION 94 1. Augmentation 95 2. Orientation 95 3. Cons tructive characterization 95 2. RELATIONS BETWEEN OLD RESULTS 99 2.1. Splitting and augmentation 101 2.2. Connectivity orientation and augmentation 103 2.3. Constructive characterization and splitting 106 3. SPLITTING AND DETACHMENT 107 3.1. Undirected splitting 108 3.1.1. Constructive characterizations. 108 3.1.2. Orientation. 110 3.1.3. Augmentation. 112 3.2. Directed splitting 113 3.3. Undirected detachment 114 3.4. Directed detachment 118 4. UNCROSSING-BASED RESULTS 119 4.1. Orientations and augmentations through submodular flows 121 4.2. Connectivity orientation and augmentation combined 125 4.3. Directed edge-connectivity augmentation 130 5. CONSTRUCTIVE CHARACTERIZATIONS 131 6. HYPERGRAPHS 134 6.1. Directed hypergraphs 137 REFERENCES 138 PERFECT POWERS IN PRODUCTS WITH CONSECUTIVE TERMS FROM ARITHMETIC PROGRESSIONS 144 1. INTRODUCTION 144 II. PRODUCTS OF CONSECUTIVE INTEGERS 145 III. PRODUCTS OF CONSECUTIVE TERMS IN ARITHMETIC PROGRESSION 148 IV. AN APPLICATION OF THEOREMS 3 AND 4 150 V. THE METHOD OF PROOFS OF THEOREMS 1 TO 4 151 REFERENCES 154 THE TOPOLOGICAL VERSION OF FODOR'S THEOREM 158 1. INTRODUCTION 158 2. THE THEOREM FOR LOCALLY COMPACT SPACES 159 3. A POSSIBLE GENERALIZATION 166 4 . STATIONARY SET DECOMPOSITION 171 REFERENCES 175 COLOR-CRITICAL GRAPHS AND HYPERGRAPHS WITH FEW EDGES: A SURVEY 176 1. INTRODUCTION 176 2.PRELIMINARIES 177 3. DIRAC-TYPE BOUNDS 179 4. GALLAI-TYPE BOUNDS 183 5. CRITICAL GRAPH S WITH NO LARGE CLIQUES 185 6. CRITICAL HYPERGRAPHS WITH FEW EDGES 186 7. ON CRITICAL SIMPLE HYPERGRAPHS 189 8. VARIATIONS: PANCHROMATIC AND STRONG COLORINGS 192 9. CONCLUDING REMARKS 195 REFERENCES 195 PSEUDO-RANDOM GRAPHS 200 1. INTRODUCTION 200 2. DEFINITIONS OF PSEUDO-RANDOM GRAPHS 202 2.1. Random graphs 202 2.2. Thomason's jumbled graphs 205 2.3. Equivalent definitions of weak pseudo-randomness 207 2.4. Eigenvalues and pseudo-random graphs 212 2.5. Strongly regular graphs 218 3. EXAMPLES 220 4. PROPERTIES OF PSEUDO-RANDOM GRAPHS 228 4.1. Connectivity and perfect matchings 228 4.2. Maximum cut 231 4.3. Independent sets and the chromatic number 233 4.4. Small subgraphs 237 4.5. Extremal properties 242 4.6. Factors and fractional factors 244 4.7. Hamiltonicity 247 4.8. Random subgraphs of pseudo-random graphs 250 4.9. Enumerative aspects 254 5. CONCLUSION 258 REFERENCES 258 BOUNDS AND EXTREMA FOR CLASSES OF GRAPHS AND FINITE STRUCTURES 264 1. INTRODUCTION 264 2. RELATIONAL STRUCTURES 267 3. BOUNDED DEGREES 269 4. DEGENERATED CLASSES OF GRAPHS 272 5. MINOR CLOSED CLASSES OF GRAPHS 274 6. BOUNDS, SUPREMA AND DUALITIES FOR FINITE STRUCTURES 278 7. SUMMARY AND CONCLU DING REMARKS 282 REFERENCES 283 RELAXING PLANARITY FOR TOPOLOGICAL GRAPHS 286 1. INTRODUCTION 286 2. ORDINARY AND TOPOLOGICAL MINORS 287 3. QUASI-PLANAR GRAPHS 288 4. GENERALIZED THRACKLES AND THEIR RELATIVES 291 5. LOCALLY PLANAR GRAPHS 293 6. STRENGTHENING THEOREM 3.6 294 7. STRENGTHENING THEOREM 3.7 295 REFERENCES 299 NOTES ON CNS POLYNOMIALS AND INTEGRAL INTERPOLATION 302 1. INTRODUCTION 302 1.1. CNS polynomials 302 1.2. Integral interpolation 305 2. PROOF OF THEOREMS 1 AND 2 310 REFERENCES 315 THE EVOLUTION OF AN IDEA - GALLAI'S ALGORITHM 318 1. INTRODUCTION 318 2 . 2-DIMENSIONAL ROUTING 319 2.1. Single Row Routing 319 2.2. Channel Routing 321 2.3. Switchbox Routing 322 3. 3-DIMENSIONAL ROUTING 324 3.1. The sn = 1 case 325 3.2. The Sn, Sw >2 case 326 REFERENCES 328 ON THE NUMBER OF ADDITIVE REPRESENTATIONS OF INTEGERS 330 1. INTRODUCTION 330 2. THE EARLY DAYS 331 3. VERA JOINS US (AND A CURE FOR AN INCURABLE DISEASE) 333 4. RECENT DEVELOPMENTS AND UNSOLVED PROBLEMS 337 REFERENCES 339 A LIFTING THEOREM ON FORCING LCS SPACES 342 1. INTRODUCTION 342 2. A METHOD TO FORCE THIN LCS SPACES WITH PRESCRIBED CARDINAL SEQUENCE 344 3. LIFTING THEOREM 347 EXTREMAL FUNCTIONS FOR GRAPH MINORS 360 1. INTRODUCTION 360 1.1. Background 361 1.2. Recent developments 362 1.3. Contents of this article 363 2. INITIAL OBSERVATIONS 364 3. R.ANDOM GRAPHS 365 4. COMPLETE MINORS OF DENSE GRAPHS 366 4.1. The extremal function c(t) 368 4.2. Directed graphs 368 5. PSEUDO-RANDOMNESS AND SOS'S QUESTION 368 6. THE EXTREMAL PROBLEM FOR GENERAL H 371 6.1. General H minors 372 6.2. Estimating '"'((H) 373 7. LINKING 375 8. MINORS AND GIRTH 376 9. MINORS AND CONNECTIVITY 378 REFERENCES 379 PERIODICITY AND ALMOST-PERIODICITY 382 1. ENTREE 382 2. TILINGS 383 3. THE FINE AND WILF THEOREM 384 4. BI-SPECIAL WORDS 385 5. BALANCED WORDS 386 6. FRAENKEL WORDS 388 7. STIFF WORDS 389 8. THREE DISTANCES THEOREMS 390 9. LINEAR COMP LEXITY WORDS 391 10. FINE AND WILF WORDS FOR SEVERAL PERIODS 393 11. TILINGS 396 12. BALANCEDNESS 396 13. COMPLEXITY 397 14. FINE AND WILF WORDS 398 15. FROBENIUS ' LINEAR DIOPHANTINE PROBLEM 399 16. BV-WORDS 400 REFERENCES 403 9783540323778 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.