• Title of article

    On computing boundary functional sums Original Research Article

  • Author/Authors

    A method for solving enumeration problems is suggested. We consider the enumeration problems which are reducible to estimation of the sums of type T(X، نويسنده , , f)=?Af(A) where f is so called boundary functional (BF) on X، نويسنده , , and the summation is over all subsets of X (or over some special subfamily of 2X). An evolution of the n-cube، نويسنده , , the percolation problem، نويسنده , , the problem of computation of the matchings number and the independent sets number، نويسنده , , the monotone Boolean functions number، نويسنده , , the binary codes number and so on are among such problems. We show how to obtain asymptotics for T(X، نويسنده , , f). In conclusion we give an example of application of the BF method to finding the number of independent sets in the bipartite graphs، نويسنده , , induced by neighbouring levels of the n-cube.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2000
  • Pages
    8
  • From page
    253
  • To page
    260
  • Abstract
    A.A. Sapozhenko
  • Keywords
    Expander , Boundary functional , Independent set
  • Journal title
    Discrete Mathematics
  • Serial Year
    2000
  • Journal title
    Discrete Mathematics
  • Record number

    950332

    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=10&DC=950332