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, HAS
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 running project





 

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 »