Preskoči na vsebino Preskoči na navigacijo

Inštitut za matematiko, fiziko in mehaniko

Language:
RSS:
Navigacija

A mathematician is a device for turning coffee into theorems.

Paul Erdös
Nahajate se tu: Domov Raziskave in projekti Raziskovalni projekti J1-8130 - Prekrižna števila in njihova uporaba
Akcije dokumenta

J1-8130 - Prekrižna števila in njihova uporaba

Temeljni znanstveno-raziskovalni projekt.

Vodja projekta: prof. dr. Bojan Mohar

Naslov projekta: Prekrižna števila in njihova uporaba

Šifra projekta: J1-8130

Veda: Naravoslovno matematične vede

Trajanje projekta: 01. 05. 2017 - 30. 04. 2020.

Cenovna kategorija: C

Letni obseg projekta: 1,59 FTE

Sodelujoči organizaciji:

1554 - Univerza v Ljubljani, Fakulteta za matematiko in fiziko

2547 - Univerza v Mariboru, Fakulteta za naravoslovje in matematiko

Projekt sofinancira: Javna agencija Republike Slovenije za raziskovalno dejavnost.

Vsebinski opis projekta:

Predstavitev problema: Risba grafa v nekem topološkem prostoru je definirana z injektivno preslikavo vozlišč grafa v točke tega prostora ter preslikavo povezav grafa v odprte gladke (pogosto odsekoma linearne) krivulje med točkami, ki predstavljajo krajišča teh povezav. Križišče je definirano kot točka, v kateri se sekata predstavitvi dveh povezav (tipično prepovemo sekanje več povezav). Prekrižno število grafa v izbranem prostoru je definirano kot najmanjše število križišč v kaki risbi grafa v tem prostoru.  Primeri uporabe prekrižnih števil prihajajo s področja elektrotehnike, kjer vozlišča predstavljajo elementi vezij (npr. tranzistorji), žice med njimi pa so povezave grafa.

Problem prekrižnega števila grafov je Turan formuliral v sredini dvajsetega stoletja, a že takratni začetni problemi kljub desetletjem napora raziskovalcev (Zarankiewiczeva domneva o prekrižnem številu polnih dvodelnih grafov, Harary-Hillova domneva o prekrižnem številu polnih grafov) z izjemo malih grafov ostajajo odprti problemi. V zvezi s Harary-Hillovo domnevo je z uporabo semidefinitnega programiranja naredila pomemben korak naprej skupina pod vodstvom R. B. Richterja, tako da so znana prekrižna števila polnih grafov s 13 ali manj vozlišči. Pri Zarankiewiczevem problemu je po dvajsetih letih od zadnjih Woodalovih rezultatov prinesla ista skupina, a ne s konkretnimi rezultati, marveč z dokazom, da če poznamo dovolj začetnih vrednosti prekrižnih števil K(m,n) za male m, potem Zarankiewiczeva domneva velja za vse. Še dve desetletji starejši pa so edini znani – Kleitmanovi – rezultati za velike dvodelne grafe, o prekrižnih številih K(m,n) za poseben primer, ko je m manjši ali enak 6.

Navedeno pokaže, da so raziskovalci že v samem začetku študija prekrižnih števil potrebovali zahtevno, poglobljeno razumevanje risb grafov. Okrog tega se je v zadnjih desetletjih razvila bogata matematična teorija. V našem projektu naslavljamo tri stebre te teorije, ki jih bomo izpostavili v nadaljevanju.

Prvi steber prinaša razumevanje strukturnih konceptov, povezanih s prekrižnimi števili grafov, kot so prekrižno-kritični grafi in operacije, ki omogočajo induktivno gradnjo grafov ter vzporedno določanje prekrižnih števil. Med slednje sodi šiv grafa (zip product), ki ga je uvedel Bokal leta 2007 in je omogočil nekaj prebojev pri določanju prekrižnega števila večparametričnih družin grafov, kot so kartezični produkti grafov in dreves. Razumevanje prekrižno kritičnih grafov pa je vodilo od začetnih preprostih konstrukcij Širana in Kochola do rezultatov o njihovih povprečnih stopnjah (pri tem so v obdobju 1990-2016 sodelovali Richter, Thomassen, Salazar, Pinontoan, Bokal, Hlineny) pa do zavrnitve domneve o omejeni stopnji k-prekrižno kritičnih grafov (Dvorak, Mohar, 2009). Ukvarjanje s tovrstnimi izzivi je vodilo do teorije grafovskih tlakovcev, ki se je izkazala kot temeljno konstrukcijsko orodje pri problemih prekrižno kritičnih grafov. Obenem po Hlinenijevem rezultatu o omejeni potni širini kritičnih grafov, pridemo do domneve (Bokal, 2010), da so vsi k-prekrižno kritični grafi zgrajeni iz tlakovanih pasovnih grafov, povezanih z majhnimi prerezi. Domnevo potrjujejo indici v smeri strukturnega izreka o velikih k-prekrižno kritičnih grafih, s katerimi se ukvarjajo Dvorak, Hlineny, Mohar, obenem pa je v celoti potrjena za 2-prekrižno kritične grafe z njihovo karakterizacijo, ki je bila objavljena v 2016 (Bokal, Richter, Salazar, Oporowski).

Drugi steber poglablja razumevanje algoritmičnih izzivov. Problem prekrižnega števila grafov je NP-težek že za kubične grafe (Hlineny), težka vprašanja pa se porajajo že ob dodatku ene same povezave v ravninsko risbo grafa (Cabello, Mohar in Chimani, Hlineny, Salazar). Računaje prekrižnega števila je zelo težek problem in najboljši aproksimacijski algoritmi za prekrižno število poljubnih grafov obetajo zelo malo (Chuzhoy). Obstajajo algoritmi, ki v polinomskem času določijo, ali je prekrižno število omejeno s fiksno konstanto (Grohe in Kawarabayashi, Reed).

Tretji steber pa gradi na razumevanju širine konceptov prekrižnega števila in njegovih aplikacij. Prej omenjeni rezultati se nanašajo na klasično prekrižno število, ki pa ga je zaradi različnih lastnosti različnih risb pri predstavljanju informacij mogoče definirati na vrsto različnih načinov. V tem kratkem pregledu izpostavimo le npr. minorsko prekrižno število, ki so ga leta 2005 uvedli Bokal, Fijavž, Mohar, in ki se izkaže za najbolj naraven model VLSI vezij: minorske operacije modelirajo točke vezja z enakim električnim potencialom, risbe grafovskih minorjev pa so model vezij, kjer se lahko poleg elementov vezja sekajo tudi prevodne povezave. Poskus taksonomije je zastavil Schaeffer v dinamičnem preglednem članku, kjer zgoščeno opredeli več kot 100 variant prekrižnega števila in sorodnih konceptov ter navede ključne rezultate. Pomemben vir za nadgrajevanje tega razumevanja je bibliografija prekrižnih števil, ki jo redno objavlja Vrto, informacije za pregled nad širino področja pa si raziskovalci izmenjujejo tudi na vsakoletni delavnici Crossing Numbers Worksohp, za katere organizacijo skrbi programski odbor v sestavi Bokal, Chimani, Hlineny in Salazar.

Sestava projektne skupine: povezava na SICRIS

Bibliografske reference: povezava na SICRIS