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 Projekt célja főként diszkrét geometriai kérdések megválaszolása. A fő kérdéskör konvex testek fedései, azon belül a központi probléma a Gohberg--Markus--Boltyanski--Hadwiger-féle fedési sejtés (másképpen: megvilágítási sejtés). Néhány kapcsolódó problémát is vizsgálok majd, például Fejes Tóth László egy kérdését, mely egy testnek adott homotetikus példányai által történő lefedhetőségének egy elégséges feltételét adná, valamint V. Soltan egy sejtését, amely hasonló helyzetben szükséges feltételt szolgáltathat.
A megvilágítási sejtés mint egy konvex testek határnak szerkezetéről szóló probléma is megfogalmazható. Hasonló természetű kérdés redukált testek megértése. Ez az állandó szélességű testek osztályához hasonló (és azt tartalmazó) osztálya konvex testeknek.
Elhelyezéseket (pakolásokat) is vizsgálok majd, például Bezdek Károly és Pach János egy sejtését, amely egy konvex testet érintő nem-átfedő pozitív homotetikus példányainak maximális számáról szól.
További, a magasdimenziós konvexitás-elmélet és a diszkrét geometria határán lévő kérdéseket vizsgálok még: a Banach-Mazur-távolság egy nem-szimmetrikus testekre történő kiterjesztésének maximum-helyeit, valamint konvex testek szimmetrikus vetületeinek dimenzióját.
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. A fő kérdés a megvilágítási sejtés, amely szerint tetszőleges n-dimenziós konvex test lefedhető belsejének 2^n darab eltoltjával. A kutatás célja a sejtés és kapcsolódó kérdések vizsgálata.
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! A megvilágítási sejtés a diszkrét geometria egy sokak által kutatott, több mint félévszázados megoldatlan kérdése. Sok eredmény ismert, de az eredeti feladat teljes általánosságban történő megoldásához (azaz, amikor minden konvex testet, nemcsak bizonyos családokat, és minden dimenzióban tekintünk), úgy tűnik, nem vagyunk közelebb, mint 50 éve voltunk.
A redukált testek osztálya természetes módon megjelenik bizonyos izoperimetrikus problémák vizsgálatakor, mivel bizonyos mennyiségek nyilvánvaló módon ebben a családban veszik fel szélsőértéküket.
Konvex testek szimmetrikus metszetének vizsgálata egy, az aszimptotikus konvexitás elméletében gyakran visszatérő gondolat egy megjelenése: különböző eredményeket először szimmetrikus testekre tudunk bizonyítani, majd megkíséreljük a kiterjesztést a nem-szimmetrikus esetre. A vizsgálódás kiindulópontja az a "negatív" tény, amely szerint általában ez a kiterjesztés nem triviális. Egy "pozitív" eredmény valamilyen módon mégis segítené az effajta kiterjesztéseket.
A vizsgált kérdések a konvex testek alapvető tulajdonságaival kapcsolatos ismereteink hiányosságára mutatnak rá, különös tekintettel a határuk szerkezetének megértésére, asszimmetriájuk mértékére, és annak mértékére, hogy mennyire különbözőek lehetnek.
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 projekt célja magasdimenziós konvex testekkel kapcsolatos nyitott kérdések vizsgálata. Ezek a matematikai objektumok absztraktnak és távolinak tűnhetnek, valójában igen széles az alkalmazási területük: optimalizációs kérdések vizsgálatától a képfeldolgozáson át statisztikai adatok értelmezéséig. A kutatás fő iránya fedési és pakolási kérdések vizsgálata. A pakolási kérdéskör egy egyszerű példája a következő feladvány: Hány egyforintost lehet átfedés nélkül egy 5cm átmérőjű körben elhelyezni? Ezen ártatlan (talán gyerekesnek tűnő) kérdés egy magasabb dimenziós kiterjesztésének vizsgálata például olyan kódolási eljárások kifejlesztésében segít, amelyek kommunikációs eszközök számára lehetővé teszik üzenetek hatékony és pontos küldését és fogadását zaj jelenlétében -- korántsem olyan ártatlan feladat.
Ha a fenti feladványt megfordítjuk, egy fedési kérdéshez jutunk: fedjük le a körlapot egyforintosokkal (most persze lehet az érmék közt átfedés). A megvilágítási sejtés (projektünk fő kérdése) ezen probléma egy messzemenő általánosítása: a feladat konvex testek hatékony fedését megtalálni önmaguk kicsinyített példányaival. A probléma történetének egy érdekessége, hogy kb. 50 éve két különböző kutatócsoport is megfogalmazta, különböző formában, és csak később derült ki, hogy a két kérdés valójában azonos. A válasz máig is várat magára.
Summary
Summary of the research and its aims for experts Describe the major aims of the research for experts. The project aims to settle some open problems, mainly coming from Discrete Geometry. The dominant theme is coverings of convex bodies and, among them, the central problem is the Gohberg--Markus--Boltyanski--Hadwiger Covering Conjecture (or Illumination Conjecture). A number of related covering problems will be considered, eg. a question of L. Fejes T\'oth on the total volume of a sequence of positive homothetic copies of a convex body that are sufficient to yield a translative covering of the body, and a conjecture of V. Soltan about a necessary condition on the sum of the coefficients in such a sequence to yield a translative cover.
The Illumination Conjecture can be stated as a question on the structure of the boundary of convex bodies. A problem similar in nature is understanding reduced bodies, a family of convex sets similar to (and containing) the family of sets of constant width.
I will also work on packings, for example on the conjecture formulated by K. Bezdek and J. Pach regarding the maximum number of non-overlapping positive homothetic copies of a convex body that touch it.
I will investigate questions that lie on the boundary of high dimensional convexity and discrete geometry: finding maximizers of (a version of) the Banach--Mazur distance between non--symmetric convex bodies, and estimating the dimension of symmetric projections of convex bodies.
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. The central problem is the Illumination Conjecture, which states that any n-dimensional convex body can be covered by 2^n translates of its interior. The main purpose of the project is the study this conjecture and related problems.
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 Illumination Conjecture is a problem in Discrete Geometry that is over half a century old, and has been considered by many researchers. Many results have been published, but we do not seem to be any closer to the solution of the general problem (that is, when all convex bodies, not just subfamilies, and all dimensions are considered) than we were 50 years ago.
Reduced bodies appear naturally in isoperimetric problems as minimizers of certain quantities are easily seen to belong to this family.
The problem on symmetric projections of convex bodies is part of a recurring theme in Asymptotic Convexity: often, results are proven for symmetric bodies and later extended to the non-symmetric case. The starting point of the question is the "negative" fact that, in general, this extension is not trivial. A "positive" result would provide a tool that could be used for this type of extension.
All the questions considered highlight gaps in our knowledge of fundamental properties convex sets, regarding their boundary structure, their measure of asymmetry, or the measure of how different they may be.
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. The project aims to answer a number of open problems regarding high dimensional convex bodies. These mathematical objects may seem very abstract and remote, but are applied in a variety of situations, from optimization to image processing to understanding statistical data. The main theme is covering and packing problems. A prototype packing problem is the following: How many non-overlapping pennies can you put in a circle of an inch of a diameter? The study of this rather innocent (arguably, childish) question, when generalized in higher dimensions yields coding algorithms that enable communication devices to send messages back and forth accurately and efficiently in the presence of noise --- not so innocent anymore.
If you reverse the puzzle above, and want to cover the circle with (overlapping) pennies you get a covering problem. The Illumination Conjecture is a generalization of this question: the goal is to cover any given convex body by smaller copies of itself. A curious part of the story of the problem is that it was posed about 50 years ago in two distinct ways independently by two groups of researchers. Later on, it turned out that the two questions were in fact the same. The answer, however is yet to be found.
Final report
Results in Hungarian
Több diszkrét- és konvex geometriai problémát vizsgáltunk. Először fedési
kérdéseket tekintettünk, köztük a Levi, Gohberg, Markus, Hadwiger és
Boltyanskii által megfogalmazott megvilágítási sejtést. Új módszerekkel alsó-
illetve felső becsléseket találtunk arra, hogy egy adott konvex test hány
eltoltjával fedhető le egy másik konvex test az n-dimenziós euklideszi térben.
Ezután beláttuk Bárány, Katchalski és Pach egy sejtését, amely egy kvantitatív
Helly-típusú kérdés.
Vizsgáltunk még gömbpoliédereket, azaz olyan konvex testeket az n-dimenziós
euklideszi térben, amelyek megkaphatók véges sok egységgömb metszeteként. Több
klasszikus konvexitásbeli, speciálisan a konvex poliéderek elméletében
szereplő állítás 'görbe' megfelelőjét megtaláltuk. Megnéztük továbbá, hogy
hogyan terjeszthetők ki ezek a kérdések általános véges dimenziós normált
terekre.
Véges halmazok szeparálhatóságával is foglalkoztunk. Ezen kombinatorikai
kérdéskör tekinthető a népszerű barkochba-játék különböző off-line
variánsainak, azaz amikor a kérdéseket előre meg kell adni, a válaszok ismerete
nélkül.
Results in English
The project involved the study of various topics in discrete and convex
geometry. First, we considered covering problems, in particular the
Illumination conjecture by Levi, Gohberg, Markus, Hadwiger and Boltyanskii. We
developed new methods both for obtaining lower bounds and for obtaining upper
bounds on the number of translates of a convex body needed to cover another
convex body in the Euclidean n-dimensional space.
Then, we proved a conjecture of Bárány, Katchalski and Pach on a quantitative
Helly type problem.
We also investigated ball polyhedra, that is, convex sets obtained as the
intersection of finitely many unit balls in Euclidean n-space. We found 'round'
analogues of classical results in convexity, and in particular, in the theory
of convex polytopes. Moreover, we studied the corresponding questions in finite
dimensional normed spaces in general.
We also studied combinatorial problems on separating a finite set, that is,
various off-line variants of the popular game '20 questions' (or, 'Barkochba
game', as known in Hungary).
Márton Naszódi, János Pach, Konrad Swanepoel: Sphere-of-influence graphs in normed spaces, Discrete Geometry and Symmetry, a Springer contributed volume (accepted for publication), 2017
Naszódi Márton: Flavors of Translative Coverings, New Trends in Intuitive Geometry, Bolyai Society, Budapest (accepted for publication), 2017
