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

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. Cover More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal Copyright page Table of Contents PREFACE A UNIFYING GENERALIZATION OF SPERNER'S THEOREM 1. SPERNER-TYPE THEOREMS 2. LYIVI INEQUALITIES 3. PROOF OF THE MAIN THEOREMS 4. CONSEQUENCES 5. THE MAXIMUM NUMBER OF COMPOSITIONS REFERENCES A QUICK PROOF OF SPRINDZHUK'S DECOMPOSITION THEOREM REFERENCES DISCREPANCY IN GRAPHS AND HYPERGRAPHS 1. INTRODUCTION 2. DISCREPANCY OF GRAPHS 3. HYPERGRAPH DISCREPANCY 4. SUBGRAPH DISCREPANCY REFERENCES BIPLANAR CROSSING NUMBERS I: A SURVEY OF RESULTS AND PROBLEMS 1. INTRODUCTION 2. GENERAL RESULTS 2.1. Variants of Euler's formula 2.2. Other lower bounds 2.3. Drawings, upper bounds 3. RESULTS AND PROBLEMS ON COMPLETE BIPARTITE GRAPHS 3.1. Lower bounds for complete bipartite Graphs 3.2. Exact results for complete bipartite graphs 3.3. Conjectured exact results for complete bipartite graphs 3.4. The best known drawings for other complete bipartite graphs 4. RESULTS AND PROBLEMS ON OTHER SPECIFIC FAMILIES GRAPHS 4.1. Complete graphs 4.2 . Hypercubes 4.3. Meshes 5. CONCLUSION REFERENCES AN EXERCISE ON THE AVERAGE NUMBER OF REAL ZEROS OF RANDOM REAL POLYNOMIALS 1.THE GENERAL SETTING 2. A SPECIAL CASE 3. A FIRST RES ULT 4. COMMENTS 5. RANDOM SEQUENCES AND DETERMINISTIC SEQUENCES 6. THE PAPERFOLDING CASE AND A GENERAL THEOREM 7. APOLOGY REFERENCES EDGE-CONNECTION OF GRAPHS, DIGRAPHS, AND HYPERGRAPHS 1. INTRODUCTION 1. Augmentation 2. Orientation 3. Cons tructive characterization 2. RELATIONS BETWEEN OLD RESULTS 2.1. Splitting and augmentation 2.2. Connectivity orientation and augmentation 2.3. Constructive characterization and splitting 3. SPLITTING AND DETACHMENT 3.1. Undirected splitting 3.1.1. Constructive characterizations. 3.1.2. Orientation. 3.1.3. Augmentation. 3.2. Directed splitting 3.3. Undirected detachment 3.4. Directed detachment 4. UNCROSSING-BASED RESULTS 4.1. Orientations and augmentations through submodular flows 4.2. Connectivity orientation and augmentation combined 4.3. Directed edge-connectivity augmentation 5. CONSTRUCTIVE CHARACTERIZATIONS 6. HYPERGRAPHS 6.1. Directed hypergraphs REFERENCES PERFECT POWERS IN PRODUCTS WITH CONSECUTIVE TERMS FROM ARITHMETIC PROGRESSIONS 1. INTRODUCTION II. PRODUCTS OF CONSECUTIVE INTEGERS III. PRODUCTS OF CONSECUTIVE TERMS IN ARITHMETIC PROGRESSION IV. AN APPLICATION OF THEOREMS 3 AND 4 V. THE METHOD OF PROOFS OF THEOREMS 1 TO 4 REFERENCES THE TOPOLOGICAL VERSION OF FODOR'S THEOREM 1. INTRODUCTION 2. THE THEOREM FOR LOCALLY COMPACT SPACES 3. A POSSIBLE GENERALIZATION 4 . STATIONARY SET DECOMPOSITION REFERENCES COLOR-CRITICAL GRAPHS AND HYPERGRAPHS WITH FEW EDGES: A SURVEY 1. INTRODUCTION 2.PRELIMINARIES 3. DIRAC-TYPE BOUNDS 4. GALLAI-TYPE BOUNDS 5. CRITICAL GRAPH S WITH NO LARGE CLIQUES 6. CRITICAL HYPERGRAPHS WITH FEW EDGES 7. ON CRITICAL SIMPLE HYPERGRAPHS 8. VARIATIONS: PANCHROMATIC AND STRONG COLORINGS 9. CONCLUDING REMARKS REFERENCES PSEUDO-RANDOM GRAPHS 1. INTRODUCTION 2. DEFINITIONS OF PSEUDO-RANDOM GRAPHS 2.1. Random graphs 2.2. Thomason's jumbled graphs 2.3. Equivalent definitions of weak pseudo-randomness 2.4. Eigenvalues and pseudo-random graphs 2.5. Strongly regular graphs 3. EXAMPLES 4. PROPERTIES OF PSEUDO-RANDOM GRAPHS 4.1. Connectivity and perfect matchings 4.2. Maximum cut 4.3. Independent sets and the chromatic number 4.4. Small subgraphs 4.5. Extremal properties 4.6. Factors and fractional factors 4.7. Hamiltonicity 4.8. Random subgraphs of pseudo-random graphs 4.9. Enumerative aspects 5. CONCLUSION REFERENCES BOUNDS AND EXTREMA FOR CLASSES OF GRAPHS AND FINITE STRUCTURES 1. INTRODUCTION 2. RELATIONAL STRUCTURES 3. BOUNDED DEGREES 4. DEGENERATED CLASSES OF GRAPHS 5. MINOR CLOSED CLASSES OF GRAPHS 6. BOUNDS, SUPREMA AND DUALITIES FOR FINITE STRUCTURES 7. SUMMARY AND CONCLU DING REMARKS REFERENCES RELAXING PLANARITY FOR TOPOLOGICAL GRAPHS 1. INTRODUCTION 2. ORDINARY AND TOPOLOGICAL MINORS 3. QUASI-PLANAR GRAPHS 4. GENERALIZED THRACKLES AND THEIR RELATIVES 5. LOCALLY PLANAR GRAPHS 6. STRENGTHENING THEOREM 3.6 7. STRENGTHENING THEOREM 3.7 REFERENCES NOTES ON CNS POLYNOMIALS AND INTEGRAL INTERPOLATION 1. INTRODUCTION 1.1. CNS polynomials 1.2. Integral interpolation 2. PROOF OF THEOREMS 1 AND 2 REFERENCES THE EVOLUTION OF AN IDEA - GALLAI'S ALGORITHM 1. INTRODUCTION 2 . 2-DIMENSIONAL ROUTING 2.1. Single Row Routing 2.2. Channel Routing 2.3. Switchbox Routing 3. 3-DIMENSIONAL ROUTING 3.1. The sn = 1 case 3.2. The Sn, Sw >2 case REFERENCES ON THE NUMBER OF ADDITIVE REPRESENTATIONS OF INTEGERS 1. INTRODUCTION 2. THE EARLY DAYS 3. VERA JOINS US (AND A CURE FOR AN INCURABLE DISEASE) 4. RECENT DEVELOPMENTS AND UNSOLVED PROBLEMS REFERENCES A LIFTING THEOREM ON FORCING LCS SPACES 1. INTRODUCTION 2. A METHOD TO FORCE THIN LCS SPACES WITH PRESCRIBED CARDINAL SEQUENCE 3. LIFTING THEOREM EXTREMAL FUNCTIONS FOR GRAPH MINORS 1. INTRODUCTION 1.1. Background 1.2. Recent developments 1.3. Contents of this article 2. INITIAL OBSERVATIONS 3. R.ANDOM GRAPHS 4. COMPLETE MINORS OF DENSE GRAPHS 4.1. The extremal function c(t) 4.2. Directed graphs 5. PSEUDO-RANDOMNESS AND SOS'S QUESTION 6. THE EXTREMAL PROBLEM FOR GENERAL H 6.1. General H minors 6.2. Estimating ((H) 7. LINKING 8. MINORS AND GIRTH 9. MINORS AND CONNECTIVITY REFERENCES PERIODICITY AND ALMOST-PERIODICITY 1. ENTREE 2. TILINGS 3. THE FINE AND WILF THEOREM 4. BI-SPECIAL WORDS 5. BALANCED WORDS 6. FRAENKEL WORDS 7. STIFF WORDS 8. THREE DISTANCES THEOREMS 9. LINEAR COMP LEXITY WORDS 10. FINE AND WILF WORDS FOR SEVERAL PERIODS 11. TILINGS 12. BALANCEDNESS 13. COMPLEXITY 14. FINE AND WILF WORDS 15. FROBENIUS ' LINEAR DIOPHANTINE PROBLEM 16. BV-WORDS REFERENCES 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