"Personaalne uurimistoetus" projekt PUT620
PUT620 "Biklikid - kombinatoorika, optimiseerimine ja kommunikatsioon (1.01.2015−31.12.2018)", Dirk Oliver Jim Theis, Tartu Ülikool, Loodus- ja täppisteaduste valdkond, Arvutiteaduse instituut.
PUT620
Biklikid - kombinatoorika, optimiseerimine ja kommunikatsioon
Bicliques -- Combinatorics, Optimization, and Communication
1.01.2015
31.12.2018
Teadus- ja arendusprojekt
Personaalne uurimistoetus
Otsinguprojekt
ValdkondAlamvaldkondCERCS erialaFrascati Manual’i erialaProtsent
4. Loodusteadused ja tehnika4.4. MatemaatikaP110 Matemaatiline loogika, hulgateooria, kombinatoorika1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)50,0
4. Loodusteadused ja tehnika4.4. MatemaatikaP160 Statistika, operatsioonanalüüs, programmeerimine, finants- ja kindlustusmatemaatika 1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)25,0
4. Loodusteadused ja tehnika4.6. ArvutiteadusedP175 Informaatika, süsteemiteooria1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)25,0
PerioodSumma
01.01.2015−31.12.201563 600,00 EUR
01.01.2016−31.12.201663 600,00 EUR
01.01.2017−31.12.201763 600,00 EUR
190 800,00 EUR

Biklikid kahealuselistes graafides on kolme kombinatoorse matemaatika ja teoreetilise arvutiteaduse valdkonna ühisosas. Kommunikatsioonikeerukus: Lovász'i ja Saks'i log-astaku hüpotees on samaväärne küsimustega biklikikatete või kahealuseliste graafide biklikkide suuruste kohta. Kombinatoorne optimiseerimine: need mõisted on väga tähtsad hiljutistes tulemustes mõnede kombinatoorse optimiseerimise ülesannete lineaarse planeerimise formulatsioonis vajaminevate tõkete ja muutujate arvu kohta, näiteks rändkaupmehe ülesandes. Kombinatoorika: alles eelmisel aastal näidati, et P. Frankl'i kuulus ühendi suhtes kinnise hulga hüpotees on samaväärne küsimusega sisalduvuse mõttes maksimaalsete biklikkide kohta kahealuselises graafis. Me tahame rakendada ekstremaalse ja tõenäosusliku kombinatoorika lähenemist ja meetodeid biklikkide ja biklikikatete uurimiseks. Et uuritavad objektid on neil juhtudel muutunud üllatavalt sarnaseks, siis me loodame kõigi kolme probleemi uurimisel anda tugeva panuse.
Bicliques in bipartite graphs are at the intersection of three areas of combinatorial mathematics and theoretical computer science. Communication Complexity: The Log-Rank Conjecture by Lovász and Saks (1988) is equivalent to questions about biclique coverings of or sizes of bicliques in bipartite graphs. Combinatorial Optimization: These concepts are at the core of recent results on bounds on the number of constraints and variables a Linear Programming formulation for a given combinatorial optimization problem, e.g., the Traveling Salesman Problem, must have. Combinatorics: Only last year, Péter Frankl’s famous Union-Closed Sets Conjecture was shown to be equivalent to a question about inclusion-wise maximal bicliques in bipartite graphs. We want to apply approaches and tools of extremal and probabilistic combinatorics to the study of bicliques and biclique coverings. Since the objects of interest become stunningly similar, we hope to make significant contributions to all three problems.