Combinatorial and convex geometry  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
111827
Type K
Principal investigator Tóth, Géza
Title in Hungarian Kombinatorikus es konvex geometria
Title in English Combinatorial and convex geometry
Keywords in Hungarian konvex halmazok, graf lerajzolasok
Keywords in English convex sets, graph drawings
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
Participants Bárány, Imre
Starting date 2015-02-01
Closing date 2019-01-31
Funding (in million HUF) 7.650
FTE (full time equivalent) 3.05
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 kérdéseket, amelyeket tanulmányozni szeretnénk, hat csoportba osztottuk be.
Mivel a kérdések viszonylag függetlenek, mindegyikkel foglalkozni kívánunk a
pályázat teljes időtartama alatt.

1. Topologikus gráfok, nem bővíthető egyszerű és k-egyszerű topologikus
gráfok.
2. Egy síkbeli halmaz eltoltjaival való sokszoros fedés felbonthatósága több
fedésre.
3. Az Erdős-Szekeres tétel és hasonló tételek általánosítása egyenesekre.
4. Véletlen politópok és rácspolitópok konvex testekben.
5. Helly típusú eredmények.
6. Vegyes: Különböző reprezentánsok geometriai feltételekkel, gráfok különböző
metszési számainak viszonya, a színes szimplexek uniójának topologiája.

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.
Sok fontos kérdés van ezeken a területeken, minden ponthoz megemlítünk egyet.

1. Nem bővíthető egyszerű illetve k-egyszerű topologikus gráfok leírása.
2. Fedés-felbontható halmazok minél pontosabb meghatározása.
3. Radon, Tverberg, Caratheodory és hasonló tételek általánosítása
egyenesekre.
4. Melyik d dimenziós konvex testekre lesz maximális illetve minimális
a beleírt véletlen politóp térfogatának (vagy csúcsszámának)
k-adik momentuma?
5. Mennyi a d dimenziós tengelyparhuzamos téglák frakcionális Helly száma?
6. Igaz-e, hogy minden gráf metszési száma legfeljebb konstansszorosa a
pár-metszési számának?

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!
Ez alapkutatás, az elméleti jelentőségén túl fontos alkalmazásai vannak a
geográfiai információs rendszerek, szenzor hálózatok, nyomtatott áramkörök
területén és sok más területen.

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.
Geometriai alakzatok (pl. pontok, egyenesek, görbék, sokszögek) elrendezéseit
vizsgáljuk a síkon, illetve magasabb dimenzióban. Tanulmányozzuk a különböző
kombinatorikai tulajdonságaikat, mint pl a metszéseiknek, metszéspontjaiknak
a struktúrája illetve száma, a részhalmazaiknak, rész-elrendezéseiknek a
lehetséges típusai, illetve ezeknek a tipikus vagy átlagos viselkedése.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
We propose to investigate six group of questions. The work on them is spread
out evenly on the whole period, since these questions are rather independent.
We state the seven problems briefly:

1. Topological graphs, saturated simple and k-simple topological graphs.
2. Decomposing multiple coverings by translates of a fixed set in the plane.
3. Generalization of the Erdos-Szekeres theorem and its relatives to lines.
4. Random polytopes and lattice polytopes in convex bodies.
5. Helly type results.
6. Miscellaneous: Distinct representatives with geometric conditions,
relationships between different crossing numbers, topology of the union of
colorful simplices

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.
There are many important questions in these fields, we mention one for each
item.

1. Description of non-extendable simple or k-simple topological graphs.
2. Characterization of some further classes of cover-decomposable sets.
3. Generalization of the Radon, Tverberg, Caratheodory, and related theorems
to lines.
4. For which d dimensional convex body K is the k-th moment of the volume
(or of the number of vertices) of the random polytope on n vertices inscribed
in K (chosen uniformly and independently from K) is maximal and minimal?
5. What is the fractional Helly number of aligned boxes in d dimensions?
6. Is it true, that the crossing number of every graph is at most a constant
multiple of its pair-crossing number?

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.
This is basic research, besides its theoretical interest, it
has applications in geographical information systems, sensor networks,
VLSI design, and many other fields.

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.
We investigate arrangements of geometric objects (e. g. points, lines,
curves, polygons) in the plane or in the space. We study some of their
combinatorial properties, like structure or number of their
intersections, possible types of subsets, subarrangements, their typical or
average behavior.




 

Final report

  
Results in Hungarian
Rovid jelentes, NKIFH, K-111827, A legtobb eredmeny temaja a Tverberg tetel altalanositasa, veletlen politopok, es metszesi szamok. De sok mas eredmeny is szuletett, osszesen 32 publikacioban. A hasznalt eszkozok nagyon sokfelek, elsosorban kombinatorikai, geometriai es topologiai. Itt csak nehany peldat tudunk felsorolni: Barany kulonbozo iranyokba altalanositotta a Tverberg tetelt. Az egyik ilyen altalanositas, matroidokra, kozos munka Kalaival es Maeshulammal [12]. A fo nehezseg a kapott szimplicialis komplexus osszefuggosege. Algebrai topologiara volt szukseg. Egy masik altalanositasban, Soberonnal kozosen, felteteleket adnak arra, hogy a Tverberg particionak megfelelo affin kombinacioban eloirt szamu negativ egyutthato legyen. Legyen G egy n csucsu es e>4n elu graf. A Metszesi Lemma szerint G minden lerajzolasaban legalabb c{e^3\over n^2} metszes van. Nyilvan ez az eredmeny nem allhat fenn multigrafokra. Pach es Toth belattak, hogy bizonyos egyszeru es termeszetes feltetelek mellett megis altalanosithato a Metszesi Lemma [27]. Tovabb altalanositotta az eredmenyt Kaufmann, Pach, Toth es Ueckert [31], kulonbozo feltelelek mellett kulonbozo korlatokat kaptak.
Results in English
Short report on NKIFH K-111827 Most results are about generalizations and relatives of Tverberg's theorem, random polytopes, and crossing numbers. But there are many other results, in 32 publications. There are various methods used, mostly geometric, combinatorial and topological. Some examples: I. Barany was working on various extensions of Tverberg's classical theorem. One such extension to matroids was proved in a joint work with Kalai and Meshulam [12]. The main difficulty is the connectedness of the underlying (matroidal) simplicial complex. Algebraic topology is used. In another generalization (joint with P Soberon) we give conditions under which a Tverberg-type partition exists with prescribed negative coefficients in the affine combinations. Let G be a graph of n vertices and e>4n edges. According to the Crossing Lemma, the number of crossings in any drawing of G is at least c{e^3\over n^2}. Clearly, this result does not hold for multigraphs in general. G Toth, together with J. Pach, found some natural conditions that imply the statement for multigraphs [27]. It was futher generalized by Kaufmann, Pach, Toth and Ueckert [31], they got different bounds under different conditions. Some of them are tight.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=111827
Decision
Yes





 

List of publications

  
I. B'ar'any, D. Hug, M. Reitzner, R. Schneider: Random points on halfspheres, Random Structures and Alg., 2017
I. B'ar'any, A. Akopyan, S. Robins: Algebraic vertices of non-convex polytopes, Advances in Mathematics, 2017
I. B'ar'any, J Matou\v sek, A. P'or: Curves in $R^d$ intersecting every hyperplane at most $d+1$ times, J. European Math. Soc., 2016
I. B'ar'any, D. Hug, R. Schneider: Affine diameters of convex bodies, Proc. AMS, 2016
G. Ambrus, I. B'ar'any, V. Grinberg: Small subset sums, Linear Alg. Appl, 2016
I. B'ar'any, A. P'or: Spherical paths without small angles, Springer Proceedings in M-athematics and Statistics, 2016
I. B'ar'any, P. Blagojevi'c, G. M Ziegler: Tverberg's theorem at 50: extensions and counterexamples, Notices of the AMS, 2016
I. B'ar'any, K. Buchin, A. Libenau, M Hoffman: Embedding trees into lattices, Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG '16), 2016
I. B'ar'any, D. Hug, M. Reitzner, R. Schneider: Random points on halfspheres, Random Structures and Alg. 50, 3-22., 2017
I. B'ar'any, A. Akopyan, S. Robins: Algebraic vertices of non-convex polytopes, Advances in Mathematics 308, 627-644., 2017
I. B'ar'any, J Matou\v sek, A. P'or: Curves in $R^d$ intersecting every hyperplane at most $d+1$ times, J. European Math. Soc. 18, 2469-2482., 2016
I. B'ar'any, D. Hug, R. Schneider: Affine diameters of convex bodies, Proc. AMS 144, 797-812, 2016
G. Ambrus, I. B'ar'any, V. Grinberg: Small subset sums, Linear Alg. Appl 499, 66-78, 2016
I. B'ar'any, A. P'or: Paths on the Sphere Without Small Angles, Springer Proceedings in Mathematics and Statistics 148, Convexity and Discrete Geometry Including Graph Theory, 239-249, 2016
I. B'ar'any, P. Blagojevi'c, G. M Ziegler: Tverberg's theorem at 50: extensions and counterexamples, Notices of the AMS 63, 732-739., 2016
I. B'ar'any, K. Buchin, A. Libenau, M Hoffman: An Improved Bound for Orthogeodesic Point Set Embeddings of Trees, Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG '16) 47-51., 2016
I. Barany, C. Thale: Intrinsic volumes and Gaussian polytopes: the missing piece of the jigsaw, Documenta Math 22, 1323-1335., 2017
I. Barany: Helge Tverberg is eighty: a personal tribute, European Journal of Combinatorics 66, 24-27., 2017
I. Barany, G. Kalai, R. Meshulam: A Tverberg-type theorem for matroids, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, Springer, 115-123., 2017
I. Barany, J. Solymosi: Gershgorin circles for eigenvalues with multiplicity, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, Springer, 123-135., 2017
I. Barany, P. Soberon: Tverberg plus minus, Discrete and Computational Geometry, accepted, 2017
I. Barany, E. Csoka, Gy. Karolyi, G. Toth: Block partitions: an extended view, Acta Mathematica Hungarica, Bisztriczky-Fejes Toth-Makai birthday volume, accepted, 2017
L. Szekely, J. Pach, C. D. Toth, G. Toth: Note on the k-planar crossing numbers, Computational Geometry: Theory and Applications, Ferran Hurtado Memorial Issue 68, 2-6., 2018
Zs. Langi, M. Naszodi, J. Pach, G. Tardos, G. Toth: Separation with restricted families of sets, J. Combinatorial Theory Ser A 144, 292-305., 2016
J. Barat, G. Toth: Improvements on the density of maximal 1-planar graphs, Journal of Graph Theory, accepted, 2018
J. Pach, G. Toth: Disjointness graphs of segments, Proc. 33rd Annual Symposium on Computational Geometry (SOCG 17, Brisbane Australia) LIPIcs 77, 59:1-15, 2017
J. Pach, G. Toth: Many touchings force many crossings, Discrete geometry and convexity in honour of Imre Barany, Ambrus, Boroczky, Furedi, eds, Typotex, Budapest, 82-89, 2017
I. Kovacs, D. Soltesz: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Ser B, accepted, 2018
I. Barany, G. Kalai, R. Meshulam: A Tverberg-type theorem for matroids, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, eds. Loebl, Nesetril, Thomas, Springer, 115-121., 2017
I. Barany, J. Solymosi: Gershgorin circles for eigenvalues with multiplicity, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, eds. Loebl, Nesetril, Thomas, Springer, 123-133., 2017
I. Barany, P. Soberon: Tverberg plus minus, Discrete and Computational Geometry 60, 588-598., 2018
I. Barany, E. Csoka, Gy. Karolyi, G. Toth: Block partitions: an extended view, Acta Mathematica Hungarica 155, 36-46, Discrete Geometry Fest, Bisztriczky-Fejes Toth-Makai birthday volume,, 2018
J. Barat, G. Toth: Improvements on the density of maximal 1-planar graphs, Journal of Graph Theory 88, 101-109., 2018
J. Pach, G. Tardos, G. Toth: Disjointness graphs of segments, Proc. 33rd Annual Symposium on Computational Geometry (SOCG 17, Brisbane Australia) LIPIcs 77, 59:1-15., 2017
J. Pach, G. Toth: Many touchings force many crossings, International Symposium of Graph Drawing and Network Visualization, Lecture Notes in Computer Science 10692, Springer, Cham, 153-159., 2018
I. Kovacs, D. Soltesz: Triangle-different Hamiltonian paths, Journal of Combinatorial Theory Ser B 129, 1-17., 2018
J. Pach, G. Toth: Crossing lemma for multigraphs, 34rd Annual Symposium of Computational Geometry LIPIcs 99, 1-13., 2018
G. Tardos, G. Toth: Attores az Erdos-Szekeres problemaban, Erinto 7, 2018
M. Kaufmann, J. Pach, G. Toth, T. Ueckert: The number of crossings in multigraphs with no empty lens, International Symposium of Graph Drawing and Network Visualization, Lecture Notes in Computer Science 11282, Springer, 242-254., 2018
I. Barany, R. Meshulam, E. Nevo, M. Tancer: Pach's homogeneous selection theorem does not admit a topological extension, Discrete Comp. Geometry, 60, 420--429., 2018
I. Barany, G. Martin, E. Naslund, S. Robins: Primitive points in convex polygons, Canadian Math. Bull. submitted, 2018
I. Barany, N. Mustafa: Applications of the universal theorem for Tverberg partitions, Journal of Combinatorial Theory Ser. A, 2018
Z. Furedi, I. Barany: Almost similar configurations, Bull Hellenic Math Soc, 2018
K. Adiprasito, I. Barany, N.Mustafa, T. Terpai: Theorems of Carathedory, Helly, and Tverberg without dimension, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018
M. Ausserhofer, S. Dann, Zs. Langi, G. Toth: An algorithm to find maximum area polygons circumscribed about a convex polygon, Discrete Applied Mathematics, accepted, 2018
I. Kovacs, G. Toth: Dense point sets with many halving lines, Discrete and Computational Geometry, accepted, 2018
I. Barany, P. Soberon: Tverberg's theorem is 50 years old: a survey, Bull AMS 55, 459-492, 2017
I. Barany, J. Bureaux, B. Lund: Limit shape of integer partitions and integral zonotopes, Adv. Math 331, 143-169., 2018



Back »