Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Cover of the book
Tytuł książki

Random matroids

Seria
Rozprawy Matematyczne tom/nr w serii: 367 wydano: 1997
Zawartość
Warianty tytułu
Abstrakty
EN
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
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
  • Institute of Mathematics, Technical University of Wrocław, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland, kordecki@im.pwr.wroc.pl
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

rozwiń roczniki

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ć.