SwePub
Sök i LIBRIS databas

  Utökad sökning

L773:0012 365X OR L773:1872 681X
 

Sökning: L773:0012 365X OR L773:1872 681X > (1995-1999) > On the number of ne...

On the number of nearly perfect matchings in almost regular uniform hypergraphs

Asratian, Armen (författare)
Luleå tekniska universitet
Kuzjurin, N. N. (författare)
Institute of System Programming, Russian Academy of Sciences
 (creator_code:org_t)
Elsevier, 1999
1999
Engelska.
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 207:1, s. 1-8
  • Tidskriftsartikel (refereegranskat)
Abstract Ämnesord
Stäng  
  • Strengthening the result of R dl and Frankl (Europ. J. Combin 6 (1985) 317-326), Pippenger proved the theorem stating the existence of a nearly perfect matching in almost regular uniform hypergraph satisfying some conditions (see J. Combin. Theory A 51 (1989) 24-42). Grable announced in J. Combin. Designs 4 (4) (1996) 255-273 that such hypergraphs have exponentially many nearly perfect matchings. This generalizes the result and the proof in Combinatorica 11 (3) (1991) 207-218 which is based on the R dl Nibble algorithm (European J. Combin. 5 (1985) 69-78). In this paper, we present a simple proof of Grable's extension of Pippenger's theorem. Our proof is based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching. We use the Lovasz Local Lemma to obtain the desired lower bound of this probability.

Ämnesord

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)
NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)

Nyckelord

Matematik
Mathematics

Publikations- och innehållstyp

ref (ämneskategori)
art (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
Asratian, Armen
Kuzjurin, N. N.
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Matematik
och Matematisk analy ...
Artiklar i publikationen
Discrete Mathema ...
Av lärosätet
Luleå tekniska universitet

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy