Kis rendű projektív síkok metszésszámának számítógépes vizsgálata

Béres László, Illés Tibor

Research output: Contribution to journalArticle

Abstract

Cikkünkben Erdős Pál véges projektív síkok blokkoló halmazainak metszésszámával kapcso-latos sejtésével foglalkozunk. Megadjuk a probléma egy egészértékű lineáris programozási (ELP ) modelljét adott rendű projektív sík esetén. Figyelembe véve az egzakt módszerek műveletigényét és számítógépes lehetőségeinket, mohó módszer alkalmazása mellett döntöttünk. A probléma matem-atikai programozási megközelítése a véges projektív síkok elméletében alapvetően új. Mohó algoritmusunkkal előálh'tottuk a z E L P szuboptimális megoldását (jelöljük OíQ(q)-val) a 7 < q < 89 intervallumba eső prímrendekre , valamint a q = 8,9,1 6 prímhatványrendekre is. Mohó algoritmusunk egyben olyan eljárás, amellyel egy adott intervallumba (esetünkbe n [C*G(?]I а а{ч) < я) tartozó bármely a egészértékhez, a metszésszámú blokkoló halmaz konstruálható. Az otc(q) értéke számítógépes tapasztalataink szerint с log q, ahol 1 < с < 2.
H a q = 89 akkor az ELP modell 8011 bináris és egy korlátos egészérték ű változót, továbbá 8011 alsó és felső korláttal rendelkező egyenlőtlenséget tartalmaz. A dolgozat végén közöljük számítógépes eredményeinket, és azok összehasonlítását az elméleti eredményekből a blokkoló halmazok metszésszámára nyert korlátokkai.
Original languageOther
Pages (from-to)397-411
Number of pages15
JournalAlkalmazott Matematikai Lapok
Volume17
Issue number3-4
Publication statusPublished - 1993
Externally publishedYes

Keywords

  • véges projektiv sik
  • 0-1 programozás
  • blokkoló halmaz

Cite this