Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Zapraszamy na https://bibliotekanauki.pl
Zawartość
Pełne teksty:
Warianty tytułu
Abstrakty
CONTENTS
1. Introduction.............................................................................5
2. Matroids..................................................................................6
2.1. Notations and basic properties...........................................6
2.2. Gaussian coefficients.......................................................10
2.3. Projective geometries.......................................................11
2.4. Special classes................................................................14
3. Probabilistic tools..................................................................15
3.1. Poisson convergence.......................................................15
3.2 Normal convergence.........................................................17
3.3. Markov processes on finite lattices..................................18
4. Random matroids - general approach..................................19
4.1. Definitions........................................................................19
4.2. Rank.................................................................................21
4.3. Duality..............................................................................23
5. Random projective geometries - combinatorial results..........26
5.1. Distribution of rank...........................................................26
5.2. Fullsubspaces - expectation and variance.......................30
5.3. Submatroids of a given type............................................33
6. Random projective geometries - limit theorems....................33
6.1. Rank of random subspaces.............................................33
6.2. Small submatroids...........................................................38
6.3. Full subspaces................................................................43
6.4. Related results................................................................46
7. Problems and conclusions....................................................49
Appendix: tables.......................................................................49
1. Gaussian coefficients.........................................................49
2. Probabilities $P^{(r)}$.........................................................51
3. Parameters of X..................................................................53
Bibliography..............................................................................54
1. Introduction.............................................................................5
2. Matroids..................................................................................6
2.1. Notations and basic properties...........................................6
2.2. Gaussian coefficients.......................................................10
2.3. Projective geometries.......................................................11
2.4. Special classes................................................................14
3. Probabilistic tools..................................................................15
3.1. Poisson convergence.......................................................15
3.2 Normal convergence.........................................................17
3.3. Markov processes on finite lattices..................................18
4. Random matroids - general approach..................................19
4.1. Definitions........................................................................19
4.2. Rank.................................................................................21
4.3. Duality..............................................................................23
5. Random projective geometries - combinatorial results..........26
5.1. Distribution of rank...........................................................26
5.2. Fullsubspaces - expectation and variance.......................30
5.3. Submatroids of a given type............................................33
6. Random projective geometries - limit theorems....................33
6.1. Rank of random subspaces.............................................33
6.2. Small submatroids...........................................................38
6.3. Full subspaces................................................................43
6.4. Related results................................................................46
7. Problems and conclusions....................................................49
Appendix: tables.......................................................................49
1. Gaussian coefficients.........................................................49
2. Probabilities $P^{(r)}$.........................................................51
3. Parameters of X..................................................................53
Bibliography..............................................................................54
Słowa kluczowe
Tematy
Kategoryzacja MSC:
Miejsce publikacji
Warszawa
Copyright
Seria
Rozprawy Matematyczne
tom/nr w serii:
367
Liczba stron
56
Liczba rozdzia³ów
Opis fizyczny
Dissertationes Mathematicae, Tom CCCLXVII
Daty
wydano
1997
otrzymano
1995-03-27
poprawiono
1997-02-10
Twórcy
autor
- Institute of Mathematics, Technical University of Wrocław, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland
Bibliografia
- [1] N. Alon, A. Frieze, and D. J. A. Welsh, Polynomial time randomized approximation scheme for Tutte-Gröthendieck invariants: the dense case, Random Structures Algorithms 6 (1995), 459-478.
- [2] G. E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976.
- [3] A. D. Barbour, L. Holst, and S. Janson, Poisson approximation, Clarendon Press, Oxford, 1992.
- [4] A. D. Barbour, S. Janson, M. Karoński, and A. Ruciński, Small cliques in random graphs, Random Structures Algorithms 1 (1990), 403-434.
- [5] R. E. Barlow and F. Proshan, Statistical Theory of Reliability and Life Testing, Holt, Rinehart and Winston, New York, 1975.
- [6] B. Bollobás, Threshold functions for small subgraphs, Math. Proc. Cambridge Philos. Soc. 90 (1981), 197-206.
- [7] B. Bollobás, Random Graphs, Academic Press, London, 1985.
- [8] P. A. Catlin, J. W. Grossman, A. M. Hobbs, and H.-J. Lai, Fractional arboricity, strength, principal partitions in graphs and matroids, Combinatorics & optimization, res. report corr. 89-13, 1989.
- [9] W. H. Cunnigham, Optimal attack and reinforcement of a network, J. Assoc. Comput. Mach. 32 (1985), 549-561.
- [10] P. Erdős and A. Reńyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61.
- [11] M. Filipkowska, Matroid generating procedures in C, Master's thesis, Technical University, Wrocław, 1993.
- [12] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, 1983.
- [13] R. L. Graham, M. Grötschel, and L. Lovász (eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995.
- [14] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1971.
- [15] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Clarendon Press, Oxford, 1979.
- [16] S. Janson, Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs, Ann. Probab. 16 (1988), 305-312.
- [17] S. Janson, Poisson approximation for large deviation, Random Structures Algorithms 1 (1990), 221-229.
- [18] S. Janson, T. Łuczak, and A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraphs in a random graph, in: Random Graphs, Proc., Poznań 1987, Wiley, 73-87.
- [19] J. G. Kalbfleisch, Complete subgraphs of random hypergraphs and bipartite graphs, in: Proc. 3rd S-E Conf. on Combinatorics, Graph Theory and Computing, Florida Atlantic Univ., Boca Raton, 1972, 297-304.
- [20] S. Karlin, A First Course in Stochastic Processes, Academic Press, 1969.
- [21] M. Karoński, Balanced Subgraphs of Large Random Graphs, Adam Mickiewicz University Press, Poznań, 1984.
- [22] M. Karoński, Random matroids, in: Handbook of Combinatorics, L. Lovász, R. L. Graham, M. Grötschel (eds.), Elsevier, Amsterdam, 1995.
- [23] D. G. Kelly and J. G. Oxley, Asymptotic properties of random subsets of projective spaces, Math. Proc. Cambridge Philos. Soc. 91 (1982), 119-130.
- [24] D. G. Kelly and J. G. Oxley, Threshold functions for some properties of random subsets of projective spaces, Quart. J. Math. Oxford 33 (1982), 463-469.
- [25] D. G. Kelly and J. G. Oxley, On random representable matroids, Stud. Appl. Math. 71 (1984), 181-205.
- [26] A. K. Kelmans, Some problems of the analysis of reliability of nets, Automat. Remote Control 26 (1965).
- [27] D. Knuth, Random matroids, Discrete Math. 12 (1975), 341-358.
- [28] W. Kordecki, Strictly balanced submatroids in random subsets of projective geometries, Colloq. Math. 55 (1988), 371-375.
- [29] W. Kordecki, Random subgraphs of the n-cycle and the n-wheel, Discrete Math. 93 (1991), 35-53.
- [30] W. Kordecki, On the rank of a random submatroid of projective geometry, in: Random Graphs, Proc. Poznań 1989, Vol. 2, Wiley, 151-163.
- [31] W. Kordecki, Maximal full subspaces in random projective spaces - thresholds and Poisson approximation, Random Structures Algorithms 6 (1995), 297-305.
- [32] W. Kordecki, Small submatroids in random matroids, Combin. Probab. Comput. 5 (1996), 1-10.
- [33] W. Kordecki and T. Łuczak, On random subsets of projective spaces, Colloq. Math. 57 (1991), 353-356.
- [34] W. Lipski and W. Marek, Combinatorial Analysis, PWN, Warszawa, 1986 (in Polish).
- [35] M. V. Lomonosov, Bernoulli scheme with closure, Problems Inform. Transmission 10 (1974), 73-81.
- [36] V. G. Mikhaĭlov, On a Janson's theorem, Teor. Veroyatn. i Primenen. 36 (1991), 168-170 (in Russian).
- [37] H. Narayanan and N. Vartak, On molecular and atomic matroids, in: Combinatorics and Graph Theory, S. B. Rao (ed.), Lecture Notes in Math. 885, Springer, New York, 1981, 358-364.
- [38] J. G. Oxley, Threshold distribution function for some random representable matroids, Math. Proc. Cambridge Philos. Soc. 95 (1984), 335-346.
- [39] J. G. Oxley, Matroid Theory, Oxford Univ. Press, Oxford, 1992.
- [40] J. G. Oxley and D. J. A. Welsh, The Tutte polynomial and percolation, in: Graph Theory and Related Topics, Academic Press, New York, 1979, 329-339.
- [41] A. Ruciński, Random graphs of binomial type with sparsely-edged initial graphs, Acta Math. Hungar. 47 (1986), 81-87.
- [42] A. Ruciński, Small subgraphs of random graphs - a survey, in: Random Graphs, Proc. Poznań 1987, Wiley, 283-303.
- [43] A. Ruciński, Proving normality in combinatorics, in: Random Graphs, Proc. Poznań 1989, Vol. 2, Wiley, 215-231.
- [44] V. E. Stepanov, Combinatorial algebra and random graph, Theory Probab. Appl. 14 (1969), 373-399.
- [45] B. Voigt, On the evolution of finite affine and projective spaces, Math. Oper. Res. 49 (1986), 313-327.
- [46] D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976.
- [47] D. J. A. Welsh, Complexity: Knots, Colourings and Counting, London Math. Soc. Lecture Note Ser. 186, Cambridge Univ. Press, 1993.
- [48] D. J. A. Welsh, Randomized approximation schemes for Tutte-Gröthendieck invariants, in: Discrete Probability and Algorithms, D. Aldous, P. Diaconis, J. Spencer, and J. M. Steele (eds.), IMA Vol. Math. Appl. 72, Springer, New York, 1995, 133-148.
- [49] N. White (ed.), Theory of Matroids, Encyclopedia Math. Appl., Cambridge Univ. Press, Cambridge, 1986.
- [50] N. White (ed.), Matroid Applications, Encyclopedia Math. Appl. 40, Cambridge Univ. Press, Cambridge, 1992.
- [51] N. White (ed.), Combinatorial Geometries, Encyclopedia Math. Appl. 29, Cambridge Univ. Press, Cambridge, 1993.
Języki publikacji
| EN |
Uwagi
1991 Mathematics Subject Classification: Primary 05B35; Secondary 60C05.
Identyfikator YADDA
bwmeta1.element.zamlynska-6dd62306-e0c3-4688-a60e-f43a418e2c94
Identyfikatory
ISSN
0012-3862
Kolekcja
DML-PL
Zawartość książki
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.