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

László, Béres ; Tibor, Illés. / Kis rendű projektív síkok metszésszámának számítógépes vizsgálata. In: Alkalmazott Matematikai Lapok. 1993 ; Vol. 17, No. 3-4. pp. 397-411.
@article{715d0e73a99649628474ae7da36494f7,
title = "Kis rendű projekt{\'i}v s{\'i}kok metsz{\'e}ssz{\'a}m{\'a}nak sz{\'a}m{\'i}t{\'o}g{\'e}pes vizsg{\'a}lata",
abstract = "Cikk{\"u}nkben Erdős P{\'a}l v{\'e}ges projekt{\'i}v s{\'i}kok blokkol{\'o} halmazainak metsz{\'e}ssz{\'a}m{\'a}val kapcso-latos sejt{\'e}s{\'e}vel foglalkozunk. Megadjuk a probl{\'e}ma egy eg{\'e}sz{\'e}rt{\'e}kű line{\'a}ris programoz{\'a}si (ELP ) modellj{\'e}t adott rendű projekt{\'i}v s{\'i}k eset{\'e}n. Figyelembe v{\'e}ve az egzakt m{\'o}dszerek műveletig{\'e}ny{\'e}t {\'e}s sz{\'a}m{\'i}t{\'o}g{\'e}pes lehetős{\'e}geinket, moh{\'o} m{\'o}dszer alkalmaz{\'a}sa mellett d{\"o}nt{\"o}tt{\"u}nk. A probl{\'e}ma matem-atikai programoz{\'a}si megk{\"o}zel{\'i}t{\'e}se a v{\'e}ges projekt{\'i}v s{\'i}kok elm{\'e}let{\'e}ben alapvetően {\'u}j. Moh{\'o} algoritmusunkkal elő{\'a}lh'tottuk a z E L P szuboptim{\'a}lis megold{\'a}s{\'a}t (jel{\"o}lj{\"u}k O{\'i}Q(q)-val) a 7 < q < 89 intervallumba eső pr{\'i}mrendekre , valamint a q = 8,9,1 6 pr{\'i}mhatv{\'a}nyrendekre is. Moh{\'o} algoritmusunk egyben olyan elj{\'a}r{\'a}s, amellyel egy adott intervallumba (eset{\"u}nkbe n [C*G(?]I а а{ч) < я) tartoz{\'o} b{\'a}rmely a eg{\'e}sz{\'e}rt{\'e}khez, a metsz{\'e}ssz{\'a}m{\'u} blokkol{\'o} halmaz konstru{\'a}lhat{\'o}. Az otc(q) {\'e}rt{\'e}ke sz{\'a}m{\'i}t{\'o}g{\'e}pes tapasztalataink szerint с log q, ahol 1 < с < 2.H a q = 89 akkor az ELP modell 8011 bin{\'a}ris {\'e}s egy korl{\'a}tos eg{\'e}sz{\'e}rt{\'e}k ű v{\'a}ltoz{\'o}t, tov{\'a}bb{\'a} 8011 als{\'o} {\'e}s felső korl{\'a}ttal rendelkező egyenlőtlens{\'e}get tartalmaz. A dolgozat v{\'e}g{\'e}n k{\"o}z{\"o}lj{\"u}k sz{\'a}m{\'i}t{\'o}g{\'e}pes eredm{\'e}nyeinket, {\'e}s azok {\"o}sszehasonl{\'i}t{\'a}s{\'a}t az elm{\'e}leti eredm{\'e}nyekből a blokkol{\'o} halmazok metsz{\'e}ssz{\'a}m{\'a}ra nyert korl{\'a}tokkai.",
keywords = "v{\'e}ges projektiv sik, 0-1 programoz{\'a}s, blokkol{\'o} halmaz",
author = "B{\'e}res L{\'a}szl{\'o} and Ill{\'e}s Tibor",
year = "1993",
language = "Other",
volume = "17",
pages = "397--411",
journal = "Alkalmazott Matematikai Lapok",
issn = "0133-3399",
number = "3-4",

}

Kis rendű projektív síkok metszésszámának számítógépes vizsgálata. / László, Béres; Tibor, Illés.

In: Alkalmazott Matematikai Lapok, Vol. 17, No. 3-4, 1993, p. 397-411.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - László, Béres

AU - Tibor, Illés

PY - 1993

Y1 - 1993

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

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

KW - véges projektiv sik

KW - 0-1 programozás

KW - blokkoló halmaz

UR - http://real-j.mtak.hu/view/journal/Alkalmazott_matematikai_lapok.html

M3 - Article

VL - 17

SP - 397

EP - 411

JO - Alkalmazott Matematikai Lapok

JF - Alkalmazott Matematikai Lapok

SN - 0133-3399

IS - 3-4

ER -