Coloring geometric hypergraphs  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
108406
Type PD
Principal investigator Keszegh, Balázs
Title in Hungarian Geometria hipergráfok színezése
Title in English Coloring geometric hypergraphs
Keywords in Hungarian színezés, hipergráf, fedésszétszedés, dualitás, konfliktus-mentes színezés
Keywords in English coloring, hypergraph, cover decomposability, duality, conflict-free coloring
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Starting date 2013-09-01
Closing date 2016-08-31
Funding (in million HUF) 18.576
FTE (full time equivalent) 2.40
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A kombinatorikus geometria egy dinamikusan fejlődő kutatási terület, mely szorosan kapcsolódik gyakorlati alkalmazásokhoz. Kutatásom során geometriai hipergráfok színezéseit tervezem vizsgálni. Eredményei közvetlenül használhatóak pl. fedésszétszedési problémáknál vagy konfliktus-mentes színezések vizsgálatánál. Célom a saját és mások friss eredményeire támaszkodva megoldani eddig nehezen támadható problémákat. Az egyik fontos kérdés, hogy bár adott konvex alakzat eltoltjaival való fedésekről már nagyon sokat lehet tudni, homotetikus példányok fedéseit viszont még alig értjük. Lényegében az egyetlen pozitív eredmény háromszögekre vonatkozik (saját eredmény társszerzővel), de még háromszögekre is vannak nyitott kérdések. Tehát fő célom a homotetikus példányokkal való fedések kutatása.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
Adott S alakzat, keressünk olyan k-t, melyre tetszőleges P ponthalmaz kiszínezhető két színnel úgy, hogy S tetszőleges homotetikus példányát véve, ha az legalább k pontot tartalmaz P-ből, akkor tartalmaz mindkét színű pontot. Nemrég bebizonyítottuk, hogy ha S egy térnyolcad a térben vagy egy tetszőleges háromszög a síkban, akkor ilyen k létezik. Ha a kérdésben homotetikus helyett eltoltat veszünk, az megegyezik a klasszikus fedés-szétszedési kérdéssel, mely eset többet vizsgált és jobban megértett, bár a legfontosabb, Pach tetszőleges konvex alakzatok szétszedhetőségéről szóló sejtése máig nyitott. Homotetikust véve a legtöbb más alakzatra (pl. négyzet) nem tudjuk, létezik-e ilyen k. A kérdés általánosítása több színre, illetve a kérdés duális változata szintén fontosak.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Kutatásom központi témája közvetlenül összefügg egyrészt fedésszétszedések vizsgálatával, mely kérdés gyakorlati motivációja, hogy minél kevesebb megfigyelővel tudjunk ellenőrizni nagy területeket; másrészt konfliktus-mentes színezésekkel, amik az elméleti modelljei drótnélküli hálózatoknak és segítségükkel csökkenthető egy adott terület lefedéséhez szükséges antennák száma. A gyakorlati alkalmazásokon kívül elméleti szempontból is nagyon fontos témakör, mivel szoros kapcsolatban áll az epszilon-hálókkal és más általánosan használt kombinatorikus geometriai eszközökkel.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A kombinatorikus geometria egyre fontosabb kutatási terület, ahol a legtöbb problémának gyakorlati alkalmazása is van. Kutatásom során kombinatorikus hipergráfok színezéseit tervezem vizsgálni, melyeket pl. területek megfigyelésének optimalizálása és vezeték nélküli antennák számának minimalizálása motivál. Az utóbbi 1-2 évben számos fontos előrelépés történt a témában, melyek közül sokban én is (társ)szerző vagyok, már a doktori dolgozatom egy része is ezzel kapcsolatos eredményekből állt. A legújabb módszerek felhasználásával és újak kitalálásával célom, hogy jobban megértsük az ilyen színezések viselkedését. Egyénileg és korábbi társszerzőimmel (melyek nagy része szintén valamilyen OTKA-projektben szerepel) tervezek dolgozni.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
Combinatorial geometry is a dynamically developing area, with strong connections to practical applications. During my research I plan to investigate colorings of geometric hypergraphs. The results of this topic have direct consequences to cover-decomposability problems and conflict-free colorings. My aim is to build upon recent results of mine and other researchers to solve problems that were hard to approach so far. One important problem is that although coverings with the translates of a given shape are understood quite well, the same cannot be told about coverings with homothetic copies of a given shape. Basically the only positive result is about the homothetic copies of triangles (my result with a coauthor) and even here there are many unsolved problems. Thus my main aim is to research coverings with homothetic copies.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
Given a shape S we want to find a constant k such that any point set P can be colored with two colors such that if a homothetic copy of S contains at least k points from P then it contains points with both colors. Recently we proved that such a k exists for S being an octant in the space or any triangle in the plane. If we take translates instead of homothets then we get the classic cover-decomposability problem, which has bigger literature and is better understood, yet the most imporant problem, Pach's conjecture about the cover-decomposability of convex shapes is still open. For the homothets of many other shapes (e.g., a square) the existence of such a k is an open problem. Generalizations for more than two colors and dual variants are also imporant.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The main focus of my research is directly related to cover-decomposability questions, which are motivated by sensor cover problems, where we want to use the minimal number of sensors for the surveillance of an area. The other main connection is with conflict-free colorings which are motivated by wireless network problems, where we want to use the minimal number of antennas to guarantee connection to every person in an area. Besides practical applications the area is imporant for theoretical reasons as well, given its connections to epsilon-nets and other general tools of combinatorial geometry.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Combinatorial geometry is an emerging area, where most problems have real-life applications. During my research I plan to investigate colorings of geometric hypergraphs, which topic is motivated, e.g., by optimizing surveillance of areas and minimizing the number of antennas in wireless network systems. In the recent years many imporant advances were done in this area, in many of them I am also a (co)author, already a part of my PhD Thesis was about related results. My aim is to apply the latest methods and develop new methods to get a better understanding of such colorings. I plan to work alone and with my former coauthors (many of whom also take part in some OTKA-project).




 

Final report

  
Results in Hungarian
Kutatásom középpoontjában a geometriai hipergráfok színezése és fedés-szétszedési problémák álltak. Ezek szoros összefüggésben vannak gyakorlati alkalmazásokkal, pl. szenzor-fedési és frekvencia kiosztási problémákkal. Jelentős előrelépéseket sikerült elérnem a témában. Korábban bebizonyítottuk, hogy térnyolcadok fedései két fedésre szétszedhetőek. A kutatási periódusban ezen állítás konstansait javítottuk tovább és általánosítottuk több fedésre való szétszedésre is. Ezen eredményeknek köszönhetően háromszögek homotetikus példányainak fedésszétszedhetőségéről és ezen probléma duálisáról is jó ismereteket szereztünk. Kovács egy eredménye szerint más poligonok homotetikusai nem fedésszétszedhetőek. Ez különösen érdekessé tette a duális kérdés vizsgálatát háromszögtől különböző poligonok homotetikusai esetén. Sikerült bebizonyítanunk, hogy négyzet homotetikusaira a duális kérdésre pozitív a válasz, ez egyúttal az első példa, amikor a fedésszétszedési és a duális pontszínezési kérdésre különböző a válasz. Továbbá optimális állítást bizonyítottunk nemkorlátos alakzat eltoltjainak több fedéssé való szétszedhetőségéről. Valójában egy még erősebb állítást bizonyítottunk pszeudo-félsíkokról, melyek vizsgálatához egy teljesen absztrakt tárgyalási módot vezettünk be, mely más hasonló problémák megoldásánál is hasznos lehet. Ezen eredményeken kívül számos más eredményem is született a kombinatorika és a geometria kapcsolódó témaköreiben.
Results in English
The main body of my research is concentrated on geometric hypergraph colorings and cover-decomposability problems. These are connected to real-life applications, e.g., sensor covering and frequency assignment problems. I managed to make substantial progress in the area. Earlier we proved that octants are cover-decomposable to two coverings. During my grant we further improved the constants for this result and proved the generalization to cover-decomposition to any number of coverings. These results lead to a good understanding of the strongly related problem about cover-decomposing homothets of a triangle and the corresponding dual problem. A result of Kovács implies that homothets of a polygon are not cover-decomposable if the polygon is not a triangle. This made intriguing what is the case with the dual problem. Here we managed to prove that for squares the dual problem has a positive answer. This is the first example where the primal and dual problems have a different answer. We also proved optimal results about cover-decomposition of the translates of a given unbounded shape. We in fact proved a more general result that pseudo-halfplanes are cover-decomposable (to arbitrary many coverings). In our proof we introduced a purely abstract way to consider such problems, which may be beneficial in further research too. Besides these I had several further results in related areas in combinatorics and geometry.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=108406
Decision
Yes





 

List of publications

  
E Ackerman, B Keszegh, M Vizer: Coloring points with respect to squares, Proceedings of the 32nd International Symposium on Computational Geometry („közlésre elfogadva”), 2016
B. Keszegh, D. Pálvölgyi: An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes, LNCS 9224, Proceedings of WG 2015, 266-280., 2016
Balázs Keszegh, Nathan Lemons, Dömötör Pálvölgyi: Online and Quasi-online Colorings of Wedges and Intervals, ORDER 1: (1) 1-21, 2015
Balázs Keszegh, Dömötör Pálvölgyi: More on decomposing coverings by octants, J COMPUT GEOM 6: (1) 300-315, 2015
Ervin Győri, Balázs Keszegh: On the number of edge-disjoint triangles in K4-free graphs, COMBINATORICA &: &, 2016
E Ackerman, B Keszegh, M Vizer: On the size of planarly connected crossing graphs, Proceedings of the 24th International Symposium on Graph Drawing & Network Visualization („közlésre elfogadva”), 2016
R. Ben-Avraham, M. Henze, R. Jaume, B. Keszegh, O. E. Raz, M. Sharir, I. Tubis: Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms, Algorithmica („közlésre elfogadva”), 2016
D. Gerbner, B. Keszegh, D. Pálvölgyi, G. Rote, G. Wiener: Search for the end of a path in the d-dimensional grid and in other graphs, Ars Mathematica Contemporanea („közlésre elfogadva”), 2016
F. Cicalese, B. Keszegh, B. Lidicky, D. Pálvölgyi, T. Valla: On the Tree Search Problem with Non-uniform Costs, Theoretical Computer Science („közlésre elfogadva”), 2016
B Keszegh, B Patkos, X Zhu: Nonrepetitive colorings of lexicographic product of paths and other graphs, DISCRETE MATH THEOR 16: (2) 97-110, 2014
Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow: Counting houses of Pareto optimal matchings in the house allocation problem, DISCRETE MATH 339: (12) 2919-2932, 2016
B. Keszegh, D. Pálvölgyi: An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes, LNCS Proceedings of WG 2015, to appear, 2015
D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, G. Wiener and M. Vizer: Finding a majority ball with majority answers, ENDM Proceedings of Eurocomb 2015, to appear, 2015
D. Gerbner, B. Keszegh, D. Pálvölgyi, G. Rote, G. Wiener: Search for the end of a path in the d-dimensional grid and in other graphs, ARS MATHEMATICA CONTEMPORANEA, accepted, 2015
D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, G. Wiener and M. Vizer: Finding a majority ball with majority answers, Electronic Notes in Discrete Mathematics 49, 345-351., 2015
Dániel Gerbner, Balázs Keszegh, Cory Palmer, Dömötör Pálvölgyi: Topological orderings of weighted directed acyclic graphs, INFORM PROCESS LETT 116: (9) 564-568, 2016
Panagiotis Cheilaris, Keszegh Balázs, Pálvölgyi Dömötör: Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs, SIAM J DISCRETE MATH 27: (4) 1775-1787, 2013
Rinat Ben-Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis: Minimum Partial Matching and Hausdorff RMS-Distance Under Translation: Combinatorics and Algorithms, 22nd European Symposium on Algorithms (ESA 2014) Proceedings, 2014
F. Cicalese, B. Keszegh, B. Lidicky, D. Pálvölgyi, T. Valla: On the Tree Search Problem with Non-uniform Costs, LNCS Proceedings of WG 2015, to appear, 2015
B Keszegh: Covering Paths and Trees for Planar Grids, GEOMBINATORICS 24: (1) 1-5, 2014
B. Keszegh, D. Pálvölgyi: Convex Polygons are Self-Coverable, Discrete and Computational Geometry 51(4), 885-895., 2014
B. Keszegh: Covering Paths and Trees for Planar Grids, EuroCG 2014 booklet, 2014
A. Asinowski, B. Keszegh, T. Miltzow: Counting Houses of Pareto Optimal Matchings in the House Allocation Problem, Seventh International Conference on Fun with Algorithms (FUN 2014), Lecture Notes in Computer Science 8496, 301-312., 2014
Rinat Ben-Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis: Minimum Partial Matching and Hausdorff RMS-Distance Under Translation: Combinatorics and Algorithms, 22nd European Symposium on Algorithms (ESA 2014) Proceedings, 2014
Panagiotis Cheilaris, Keszegh Balázs, Pálvölgyi Dömötör: Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs, SIAM J DISCRETE MATH 27: (4) 1775-1787, 2013
B Keszegh, D Pálvölgyi: Octants are Cover Decomposable into Many Coverings, COMP GEOM-THEOR APPL 47: (5) 585-588, 2014



Back »