Finite and Infinite Sets (eBook)

Colloquia Mathematica Societatis Janos Bolyai, 37.

A. Hajnal, L. Lovasz, V. T. Sos (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
438 Seiten
Elsevier Science (Verlag)
978-1-4831-6122-8 (ISBN)

Infos

Colloquia Mathematica Societatis Jânos Bolyai, 37: Finite and Infinite Sets, Vol. I focuses on the principles, operations, and approaches involved in finite and infinite sets. The selection first elaborates on essential chains and squares, cellular automata in trees, almost disjoint families of countable sets, and application of Lovasz local lemma. Discussions focus on deleting operations, number of all and self-dual E-chains, transversality of E-chains and E-squares, and binary E-chains and E-squares. The text then elaborates on induced subgraphs, inverse extremal digraph problems, two Sperner-type conditions, and minimal decomposition of all graphs with equinumerous vertices and edges into mutually isomorphic subgraphs. Topics include general digraph extremal problem, matrix graphs and quadratic forms, augmentation of matrices, set of attained densities, proof of the continuity theorem, and inverse extremal multigraph problems. The text examines circular flows in graphs, two-colorings of simple arrangements, monochromatic paths in infinite colored graphs, and graphs associated with an integral domain and their applications. The selection is a dependable reference for researchers interested in finite and infinite sets.

---

Colloquia Mathematica Societatis Janos Bolyai, 37: Finite and Infinite Sets, Vol. I focuses on the principles, operations, and approaches involved in finite and infinite sets. The selection first elaborates on essential chains and squares, cellular automata in trees, almost disjoint families of countable sets, and application of Lovasz local lemma. Discussions focus on deleting operations, number of all and self-dual E-chains, transversality of E-chains and E-squares, and binary E-chains and E-squares. The text then elaborates on induced subgraphs, inverse extremal digraph problems, two Sperner-type conditions, and minimal decomposition of all graphs with equinumerous vertices and edges into mutually isomorphic subgraphs. Topics include general digraph extremal problem, matrix graphs and quadratic forms, augmentation of matrices, set of attained densities, proof of the continuity theorem, and inverse extremal multigraph problems. The text examines circular flows in graphs, two-colorings of simple arrangements, monochromatic paths in infinite colored graphs, and graphs associated with an integral domain and their applications. The selection is a dependable reference for researchers interested in finite and infinite sets.

Inhalt

Front Cover 1
Finite and Infinite Sets 2
Copyright Page 3
Table of Contents 5
PREFACE 4
SCIENTIFIC PROGRAM 8
LIST OF PARTICIPANTS 16
CHAPTER 1. ON THE ESSENTIAL CHAINS AND SQUARES 26
ABSTRACT 26
0. INTRODUCTION 26
1. THE NUMBER OF ALL AND SELF-DUAL E-cCHAINS 27
2. TRANSVERSALITY OF E-CHAINS AND E-SQUARES 30
3. BINARY E-CHAINS AND E-SQUARES 31
REFERENCES 34
CHAPTER 2. CELLULAR AUTOMATA IN TREES 36
THE DELETING OPERATIONS 38
REFERENCE 46
CHAPTER 3. ON THE DISTRIBUTION OF THE NUMBER OF INTERIOR POINTS IN SUBSETS OF THE n-DIMENSIONAL UNIT CUBE 48
REFERENCES 59
CHAPTER 4. ALMOST DISJOINT FAMILIES OF COUNTABLE SETS 60
§1. THE PROPERTY GH (t) 62
§2. RELATIVES TO GH (.) 73
§3. FAMILIES HAVING ADR 83
REFERENCES 87
CHAPTER 5. INDUCTIVE CLASSES OF CUBIC GRAPHS 90
ABSTRACT 90
PROOF OF THEOREM 94
REFERENCES 101
CHAPTER 6. AN APPLICATION OF LOVASZ LOCAL LEMMA: THERE EXISTS AN INFINITE 01-SEQUENCE CONTAINING NO NEAR IDENTICAL INTERVALS 104
REFERENCES 108
CHAPTER 7. INDUCED SUBGRAPHS 110
1. INTRODUCTION 110
2. INDUCED SUBGRAPHS AND PSEUDOSIMILAR VERTICES 111
3. SPECIAL GRAPH INVARIANTS AND EDGE COLOURINGS 114
REFERENCES 118
CHAPTER 8. INVERSE EXTREMAL DIGRAPH PROBLEMS 120
ABSTRACT 120
1. INTRODUCTION 121
2. THE GENERAL DIGRAPH EXTREMAL PROBLEM 122
3. MATRIX DIGRAPHS, DENSITY 123
4. MATRIX GRAPHS AND QUADRATIC FORMS. MATRIX COLOURINGS. ENUNCIATION OF THEOREM 1 132
5. UNIQUE A-COLOURINGS. PSEUDO-A-COLOURINGS 138
6. AUGMENTATION OF MATRICES 140
7. PROOF OF LEMMA 4 145
8. PROOF OF THEOREM 1 146
9. THE SET OF ATTAINED DENSITIES. A CONTINUITY THEOREM 151
10. PROOF OF THE CONTINUITY THEOREM 152
11. INVERSE EXTREMAL MULTIGRAPH PROBLEMS 154
REFERENCES 156
CHAPTER 9. ON TWO SPERNER-TYPE CONDITIONS 158
1. INTRODUCTION 158
2. MAXIMUM SIZE 159
3. CHARACTERIZATION OF MAXIMALLY SIZED SUBSETS FOR t = 3 160
4. LATTICE-ORDERING DEFINED ON THE SET S1 (P) 165
REFERENCES 169
CHAPTER 10. MINIMAL DECOMPOSITION OF ALL GRAPHS WITH EQUINUMEROUS VERTICES AND EDGES INTO MUTUALLY ISOMORPHIC SUBGRAPHS 172
I. INTRODUCTION 172
II. PRELIMINARIES 173
III. ESTIMATING U(n) 176
IV. CONCLUDING REMARKS 179
REFERENCES 180
CHAPTER 11. ON IRREGULARITIES OF DISTRIBUTION 182
INTRODUCTION 182
PRELIMINARIES 185
AN UPPER BOUND ON um 189
A LOWER BOUND ON um 204
AN EXTREMAL SEQUENCE 213
CONCLUDING REMARKS 220
REFERENCES 222
CHAPTER 12. SOME THEOREMS OF THE NORDHAUS-GADDUM CLASS 224
1. INTRODUCTION 224
2. AN UPPER BOUND 225
3. THE UPPER BOUND IS ATTAINED 227
4. POINT-PARTITION NUMBERS 228
REFERENCES 229
CHAPTER 13. A RESTRICTED VERSION OF HALES-JEWETT'S THEOREM 232
1. 232
2. 233
3. 234
4. 240
REFERENCES 246
CHAPTER 14. SIZE RAMSEY NUMBERS INVOLVING MATCHINGS 248
ABSTRACT 248
1. INTRODUCTION 248
2. EXACT RESULTS 250
3. BOUNDS 255
4. ASYMPTOTIC RESULTS 260
REFERENCES 264
CHAPTER 15. SELECTIVITY OF HYPERGRAPHS 266
1. INTRODUCTION 266
2. SIZE OF SELECTIVE k-GRAPHS 268
3. EXACT BOUND FOR THE CHROMATIC NUMBER OF A SELECTIVE HYPERGRAPH 273
4. A CONSTRUCTIVE PROOF OF THE EXISTENCE OF SPARSE SELECTIVE HYPERGRAPHS 277
5. CONCLUDING REMARKS 282
REFERENCES 284
CHAPTER 16. GENERALIZED POLYMATROIDS 286
ABSTRACT 286
1. INTRODUCTION 286
2. PRELIMINARIES 288
3. GENERALIZED POLYMATROIDS 289
REFERENCES 294
CHAPTER 17. MATROIDS FROM CROSSING FAMILIES 296
ABSTRACT 296
1. INTRODUCTION 297
2. PRELIMINARIES, NOTATION 298
3. A NEW MATROID CONSTRUCTION 298
4. ORIENTATIONS OF UNDIRECTED GRAPHS 303
REFERENCES 304
CHAPTER 18. FAMILIES OF FINITE SETS WITH MISSING INTERSECTIONS 306
ABSTRACT 306
1. PRELIMINARIES 306
3. STAR-SYSTEMS 309
4. THE PROOF OF THEOREM 1 311
5. THE PROOF OF THEOREM 2 315
REFERENCES 318
CHAPTER 19. EXTENDING FUNCTIONS FROM SUBSETS 320
ABSTRACT 320
1. INTRODUCTION. NOTATION 320
2. THE RESULTS 321
REFERENCES 333
CHAPTER 20. AN ERDÖS-KO-RADO TYPE THEOREM 334
1. INTRODUCTION AND RESULTS 334
2. THE PROOF METHOD 336
3. CANONICAL FORM OF F 339
4. AN UPPER BOUND FOR F 340
5. PROOF OF THEOREM 7 341
REFERENCES 343
CHAPTER 21. STRONG SYSTEMS OF REPRESENTATIVES 344
REFERENCE 348
CHAPTER 22. GRAPHS ASSOCIATED WITH AN INTEGRAL DOMAIN AND THEIR APPLICATIONS 350
1. INTRODUCTION 350
2. STATEMENT OF THEOREMS 1 AND 2 351
3. APPLICATIONS 354
REFERENCES 357
CHAPTER 23. MONOCHROMATIC PATHS IN INFINITE COLOURED GRAPHS 360
ABSTRACT 360
1. INTRODUCTION 360
2. PROOF OF THEOREM 1 362
3. PROOF OF THEOREM 2 364
4. PROOF OF THEOREM 3 368
REFERENCES 370
CHAPTER 24. TWO-COLORINGS OF SIMPLE ARRANGEMENTS 372
1. INTRODUCTION 372
2. MINIMUM NUMBER OF BLUE REGIONS 373
3. MAXIMUM NUMBER OF BLUE REGIONS 373
4. TRIANGLES IN THE PROJECTIVE PLANE 377
5. QUADRILATERALS IN THE PROJECTIVE PLANE 377
REFERENCES 379
CHAPTER 25. ON DUMPLING-EATING GIANTS 380
1. INTRODUCTION 380
2. THE INVESTIGATED MODEL 381
3. MAXIMAL AND MINIMAL SPEED-RATIO 382
4. AVERAGE SPEED-RATIO 388
5. FURTHER PROBLEMS 389
REFERENCES 391
CHAPTER 26. ON CIRCULAR FLOWS IN GRAPHS 392
ABSTRACT 392
I. INTRODUCTION 393
II. DIRECTED CIRCULAR FLOWS 394
III. UNDIRECTED CIRCULAR FLOWS 398
REFERENCES 403
CHAPTER 27. LONGEST CIRCUITS IN 3-CONNECTED GRAPHS 404
ABSTRACT 404
1. INTRODUCTION 404
2. PRELIMINARIES AND NOTATION 407
3. STRONGLY LINKED COMPONENTS 409
4. THE SEPARABLE COMPONENTS 411
5. HAMILTONIAN COMPONENTS 419
6. THE MAIN RESULTS 432
REFERENCES 439

Produkt-Details

• Erscheint lt. Verlag: 15.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4831-6122-6 / 1483161226
• ISBN-13: 978-1-4831-6122-8 / 9781483161228