Hajnal / Lovász / Sós Finite and Infinite Sets

Colloquia Mathematica Societatis János Bolyai, 37.
1. Auflage 2014
ISBN: 978-1-4831-6122-8
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 438 Seiten, Web PDF

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.

Autoren/Hrsg.

Hajnal, A.

Lovász, L.

Sós, V. T.

Inhaltsverzeichnis

1;Front Cover;1
2;Finite and Infinite Sets;2
3;Copyright Page;3
4;Table of Contents;5
5;PREFACE;4
6;SCIENTIFIC PROGRAM;8
7;LIST OF PARTICIPANTS;16
8;CHAPTER 1. ON THE ESSENTIAL CHAINS AND SQUARES;26
8.1;ABSTRACT;26
8.2;0. INTRODUCTION;26
8.3;1. THE NUMBER OF ALL AND SELF-DUAL E-cCHAINS;27
8.4;2. TRANSVERSALITY OF E-CHAINS AND E-SQUARES;30
8.5;3. BINARY E-CHAINS AND E-SQUARES;31
8.6;REFERENCES;34
9;CHAPTER 2. CELLULAR AUTOMATA IN TREES;36
9.1;THE DELETING OPERATIONS;38
9.2;REFERENCE;46
10;CHAPTER 3. ON THE DISTRIBUTION OF THE NUMBER OF INTERIOR POINTS IN SUBSETS OF THE n-DIMENSIONAL UNIT CUBE;48
10.1;REFERENCES;59
11;CHAPTER 4. ALMOST DISJOINT FAMILIES OF COUNTABLE SETS;60
11.1;§1. THE PROPERTY GH (t);62
11.2;§2. RELATIVES TO GH (.);73
11.3;§3. FAMILIES HAVING ADR;83
11.4;REFERENCES;87
11.5;CHAPTER 5. INDUCTIVE CLASSES OF CUBIC GRAPHS;90
11.6;ABSTRACT;90
11.7;PROOF OF THEOREM;94
11.8;REFERENCES;101
12;CHAPTER 6. AN APPLICATION OF LOVASZ LOCAL LEMMA: THERE EXISTS AN INFINITE 01-SEQUENCE CONTAINING NO NEAR IDENTICAL INTERVALS;104
12.1;REFERENCES;108
13;CHAPTER 7. INDUCED SUBGRAPHS;110
13.1;1. INTRODUCTION;110
13.2;2. INDUCED SUBGRAPHS AND PSEUDOSIMILAR VERTICES;111
13.3;3. SPECIAL GRAPH INVARIANTS AND EDGE COLOURINGS;114
13.4;REFERENCES;118
14;CHAPTER 8. INVERSE EXTREMAL DIGRAPH PROBLEMS;120
14.1;ABSTRACT;120
14.2;1. INTRODUCTION;121
14.3;2. THE GENERAL DIGRAPH EXTREMAL PROBLEM;122
14.4;3. MATRIX DIGRAPHS, DENSITY;123
14.5;4. MATRIX GRAPHS AND QUADRATIC FORMS. MATRIX COLOURINGS. ENUNCIATION OF THEOREM 1;132
14.6;5. UNIQUE A-COLOURINGS. PSEUDO-A-COLOURINGS;138
14.7;6. AUGMENTATION OF MATRICES;140
14.8;7. PROOF OF LEMMA 4;145
14.9;8. PROOF OF THEOREM 1;146
14.10;9. THE SET OF ATTAINED DENSITIES. A CONTINUITY THEOREM;151
14.11;10. PROOF OF THE CONTINUITY THEOREM;152
14.12;11. INVERSE EXTREMAL MULTIGRAPH PROBLEMS;154
14.13;REFERENCES;156
15;CHAPTER 9. ON TWO SPERNER-TYPE CONDITIONS;158
15.1;1. INTRODUCTION;158
15.2;2. MAXIMUM SIZE;159
15.3;3. CHARACTERIZATION OF MAXIMALLY SIZED SUBSETS FOR t = 3;160
15.4;4. LATTICE-ORDERING DEFINED ON THE SET S1 (P);165
15.5;REFERENCES;169
16;CHAPTER 10. MINIMAL DECOMPOSITION OF ALL GRAPHS WITH EQUINUMEROUS VERTICES AND EDGES INTO MUTUALLY ISOMORPHIC SUBGRAPHS;172
16.1;I. INTRODUCTION;172
16.2;II. PRELIMINARIES;173
16.3;III. ESTIMATING U(n);176
16.4;IV. CONCLUDING REMARKS;179
16.5;REFERENCES;180
17;CHAPTER 11. ON IRREGULARITIES OF DISTRIBUTION;182
17.1;INTRODUCTION;182
17.2;PRELIMINARIES;185
17.3;AN UPPER BOUND ON um;189
17.4;A LOWER BOUND ON um;204
17.5;AN EXTREMAL SEQUENCE;213
17.6;CONCLUDING REMARKS;220
17.7;REFERENCES;222
18;CHAPTER 12. SOME THEOREMS OF THE NORDHAUS-GADDUM CLASS;224
18.1;1. INTRODUCTION;224
18.2;2. AN UPPER BOUND;225
18.3;3. THE UPPER BOUND IS ATTAINED;227
18.4;4. POINT-PARTITION NUMBERS;228
18.5;REFERENCES;229
19;CHAPTER 13. A RESTRICTED VERSION OF HALES-JEWETT'S THEOREM;232
19.1;1.;232
19.2;2.;233
19.3;3.;234
19.4;4.;240
19.5;REFERENCES;246
20;CHAPTER 14. SIZE RAMSEY NUMBERS INVOLVING MATCHINGS;248
20.1;ABSTRACT;248
20.2;1. INTRODUCTION;248
20.3;2. EXACT RESULTS;250
20.4;3. BOUNDS;255
20.5;4. ASYMPTOTIC RESULTS;260
20.6;REFERENCES;264
21;CHAPTER 15. SELECTIVITY OF HYPERGRAPHS;266
21.1;1. INTRODUCTION;266
21.2;2. SIZE OF SELECTIVE k-GRAPHS;268
21.3;3. EXACT BOUND FOR THE CHROMATIC NUMBER OF A SELECTIVE HYPERGRAPH;273
21.4;4. A CONSTRUCTIVE PROOF OF THE EXISTENCE OF SPARSE SELECTIVE HYPERGRAPHS;277
21.5;5. CONCLUDING REMARKS;282
21.6;REFERENCES;284
22;CHAPTER 16. GENERALIZED POLYMATROIDS;286
22.1;ABSTRACT;286
22.2;1. INTRODUCTION;286
22.3;2. PRELIMINARIES;288
22.4;3. GENERALIZED POLYMATROIDS;289
22.5;REFERENCES;294
23;CHAPTER 17. MATROIDS FROM CROSSING FAMILIES;296
23.1;ABSTRACT;296
23.2;1. INTRODUCTION;297
23.3;2. PRELIMINARIES, NOTATION;298
23.4;3. A NEW MATROID CONSTRUCTION;298
23.5;4. ORIENTATIONS OF UNDIRECTED GRAPHS;303
23.6;REFERENCES;304
24;CHAPTER 18. FAMILIES OF FINITE SETS WITH MISSING INTERSECTIONS;306
24.1;ABSTRACT;306
24.2;1. PRELIMINARIES;306
24.3;3. STAR-SYSTEMS;309
24.4;4. THE PROOF OF THEOREM 1;311
24.5;5. THE PROOF OF THEOREM 2;315
24.6;REFERENCES;318
25;CHAPTER 19. EXTENDING FUNCTIONS FROM SUBSETS;320
25.1;ABSTRACT;320
25.2;1. INTRODUCTION. NOTATION;320
25.3;2. THE RESULTS;321
25.4;REFERENCES;333
26;CHAPTER 20. AN ERDÖS-KO-RADO TYPE THEOREM;334
26.1;1. INTRODUCTION AND RESULTS;334
26.2;2. THE PROOF METHOD;336
26.3;3. CANONICAL FORM OF F;339
26.4;4. AN UPPER BOUND FOR F;340
26.5;5. PROOF OF THEOREM 7;341
26.6;REFERENCES;343
27;CHAPTER 21. STRONG SYSTEMS OF REPRESENTATIVES;344
27.1;REFERENCE;348
28;CHAPTER 22. GRAPHS ASSOCIATED WITH AN INTEGRAL DOMAIN AND THEIR APPLICATIONS;350
28.1;1. INTRODUCTION;350
28.2;2. STATEMENT OF THEOREMS 1 AND 2;351
28.3;3. APPLICATIONS;354
28.4;REFERENCES;357
29;CHAPTER 23. MONOCHROMATIC PATHS IN INFINITE COLOURED GRAPHS;360
29.1;ABSTRACT;360
29.2;1. INTRODUCTION;360
29.3;2. PROOF OF THEOREM 1;362
29.4;3. PROOF OF THEOREM 2;364
29.5;4. PROOF OF THEOREM 3;368
29.6;REFERENCES;370
30;CHAPTER 24. TWO-COLORINGS OF SIMPLE ARRANGEMENTS;372
30.1;1. INTRODUCTION;372
30.2;2. MINIMUM NUMBER OF BLUE REGIONS;373
30.3;3. MAXIMUM NUMBER OF BLUE REGIONS;373
30.4;4. TRIANGLES IN THE PROJECTIVE PLANE;377
30.5;5. QUADRILATERALS IN THE PROJECTIVE PLANE;377
30.6;REFERENCES;379
31;CHAPTER 25. ON DUMPLING-EATING GIANTS;380
31.1;1. INTRODUCTION;380
31.2;2. THE INVESTIGATED MODEL;381
31.3;3. MAXIMAL AND MINIMAL SPEED-RATIO;382
31.4;4. AVERAGE SPEED-RATIO;388
31.5;5. FURTHER PROBLEMS;389
31.6;REFERENCES;391
32;CHAPTER 26. ON CIRCULAR FLOWS IN GRAPHS;392
32.1;ABSTRACT;392
32.2;I. INTRODUCTION;393
32.3;II. DIRECTED CIRCULAR FLOWS;394
32.4;III. UNDIRECTED CIRCULAR FLOWS;398
32.5;REFERENCES;403
33;CHAPTER 27. LONGEST CIRCUITS IN 3-CONNECTED GRAPHS;404
33.1;ABSTRACT;404
33.2;1. INTRODUCTION;404
33.3;2. PRELIMINARIES AND NOTATION;407
33.4;3. STRONGLY LINKED COMPONENTS;409
33.5;4. THE SEPARABLE COMPONENTS;411
33.6;5. HAMILTONIAN COMPONENTS;419
33.7;6. THE MAIN RESULTS;432
33.8;REFERENCES;439