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

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

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 journal › Article

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 language	Other
Pages (from-to)	397-411
Number of pages	15
Journal	Alkalmazott Matematikai Lapok
Volume	17
Issue number	3-4
Publication status	Published - 1993
Externally published	Yes

Keywords

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

Cite this

@article{715d0e73a99649628474ae7da36494f7,

title = "Kis rend{\H u} 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{\H o}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{\H u} line{\'a}ris programoz{\'a}si (ELP ) modellj{\'e}t adott rend{\H u} projekt{\'i}v s{\'i}k eset{\'e}n. Figyelembe v{\'e}ve az egzakt m{\'o}dszerek m{\H u}veletig{\'e}ny{\'e}t {\'e}s sz{\'a}m{\'i}t{\'o}g{\'e}pes lehet{\H o}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{\H o}en {\'u}j. Moh{\'o} algoritmusunkkal el{\H o}{\'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{\H o} 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 {\H u} v{\'a}ltoz{\'o}t, tov{\'a}bb{\'a} 8011 als{\'o} {\'e}s fels{\H o} korl{\'a}ttal rendelkez{\H o} egyenl{\H o}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{\H o}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",

}

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

SN - 0133-3399

VL - 17

SP - 397

EP - 411

JO - Alkalmazott Matematikai Lapok

JF - Alkalmazott Matematikai Lapok

IS - 3-4

ER -

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

Abstract

Keywords

Other files and links

Cite this