Discrete geometry and combinatorial convexity  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
46246
Type K
Principal investigator Bárány, Imre
Title in Hungarian Diszkrét geometria és kombinatorikus konvexitás
Title in English Discrete geometry and combinatorial convexity
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Füredi, Zoltán
Kincses, János
Pach, János
Pór, Attila
Solymosi, Jozsef
Tóth, Géza
Starting date 2004-01-01
Closing date 2006-12-31
Funding (in million HUF) 6.262
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
Ez az OTKA palyazat viszonylag rovid, mindossze ket eves volt. Ehhez kepest sok jelentos eredmenyet ertunk el, es a kituzott feladatok nagyreszeben komoly elorelepes tortent. Barany Imrenek peldaul sikerult egy sikbeli konvex halmaz maximalis affin keruletu reszhalmazat karakterizalnia. Furedi Zoltan tobbek kozott azt vizsgalta, hogy egy adott haromszog milyen feltetelek mellett fedheto le pozitiv es negativ homotetikus peldanyainak segitsegevel gazdasagosan. Pach Janos es Toth Geza tovabb folytattak geometriai grafok keresztezesi szamara vontakozo kutatasaikat, ezen kivul tobb diszkret geometriai problemat oldottak meg. Por Attila (Barany Imrevel es Pavel Valtrral kozosen) megoldotta azt a sejtest, miszerint n tetszoleges sikbeli pontot fol lehet fuzni egy olyan torottvonalra, amelynek minden szoge legalabb 20 fokos. Solymosi Jozsef kombinatorikus modszerek alkalmazasait vizsgalta szamelmeleti problemakban. A kutatasaiban kiemelt szerepet jatszott diszkret geometriai eredmenyek hasznalata szamelmeleti kerdesekben.
Results in English
This OTKA project has been short, only two year long. Yet we have succeeded to have many significant results, and produced real improvements in most of the targeted areas. Imre Barany, for instance, proved a characterization theorem for the maximal affine perimeter convex subset of a given convex body in the plane. Zoltan Furedi studied, among other things, under what condition a given triangle can be economically covered by its positive and negative homothetic copies. Janos Pach and Geza Toth have continued their investigations into the theory of crossing numbers and geometric graphs. They further solved several problems from discrete geometry. Attila Por, together with Imre Barany and Pavel Valtr, has solved the conjecture stating that, given an n point set in the plane, there exists a polygonal path through these points with all of its angles larger than 20 degrees. Jozsef Solymosi studied applications of combinatorial methods in number theory, in particular, the use of results from discrete geometry in number theory problems.
Full text http://real.mtak.hu/1357/
Decision
Yes





 

List of publications

  
Füredi Z, Chen Jachen.: Minimum vertex-diameter-2-critical graphs, J. Graph Theory. 50, 293-315., 2005
Barany I., Matousek J.,: Berge's theorem, fractional Helly, and art galleries, Discrete Math. 306 (2006), 2303--2313, 2006
Barany I., Simanyi, N.,: A note on the size of the largest ball inside a convex polytope, Periodica Math. Hung. 51 (2005) 15-18, 2005
J. Pach, G. Tóth: Disjoint edges in topological graphs, Combinatorial Geometry and Graph Theory (eds. J. Aklyama et al.), Lecture Notes in Comp Sci 3330, Springer-Verlag, Berlin, 133-140, 2005
J. Pach, A. Dumitrescu: Pushing squares around, Graphs and Combinatorics 22 (2006), 37-50, 2006
J. Pach, R. Radoicic, G. Tardos, G. Tóth: Improving the Crossing Lemma by finding more crossings in sparse graphs, Discrete and Computational Geometry 36 (2006), 527--552, 2006
J. Pach, R. Pinchasi and M. Sharir:: Solution of Scott\'s problem on the number of directions determined by a point set in $3$-space,, 20th ACM Symposium on Computational Geometry, ACM Press, New York, 2004, 76--85., 2004
P. Brass, J. Pach: Problems and results on geometric patterns, Graph Theory and Combinatorial Optimization (eds. D. Avis et al.), Kluwer Acad. Publ. accepted, 2005
J. Kyncl, J. Pach, G. Tóth: Long alternating paths in bicolored point sets, in: Graph Drawing (J. Pach, ed.), Lecture Notes in Computer Science 3383, Springer, 340-348, 2004
A. Fiat, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl: Online conflict-free coloring for intervals, ACM-SIAM Symposium on Disc. Algorithms (SODA 2005), accepted, 2005
J. Solymosi,: A note on a question of Erdos and Graham,, Combinatorics, Probability, & Computing , 2004, Vol. 13. Issue 2 263-267., 2004
J. Pach, R. Radoicic, J. Vondrak: On the diameter of separated point sets with many nearly equal distances, European J. Combinatorics 27 (2006), 1321--1332, 2006
S. Bereg, A. Dumitrescu, J. Pach: Sliding disks in the plane,, in: Discrete and Computational Geometry (JCDCG 2004) (J. Akiyama et al., eds.), Lecture Notes in Computer Science 3742, Springer-Verlag, Tokyo, 2005, 37-47., 2005
G. Toth, P. Valtr:: The Erdős-Szekeres theorem, upper bounds and generalizations upper bounds and generalizations, Discrete and Computational Geometry - MSRI volume, 52, 557-568, 2005
G. Tardos, G. Tóth: Crossing stars in topological, Japan Conference on Discrete and Computational Geometry 2004, Lecture Notes in Computer Science 3742, Springer-Verlag, Berlin, 2005, 184-197, 2005
J. Nesetril, J. Solymosi, and P. Valtr,: A Ramsey property of planar graphs,, Towards a Theory of Geometric Graphs, Contemporary Mathematics, Amer.Math.Soc. V.342, (Edited by J. Pach) 169-176., 2004
J. Solymosi and V. Vu,: Distinct Distances in Homogeneous Sets,, Towards a theory of geometric graphs; Contemp. Math. (Amer. Math. Soc, 2004), pp. 259-268., 2004
J. Solymosi, Cooper, J.N.,: Distinct distances in high dimensional homogeneous sets,, Amer.Math.Soc. V342, (Edited by J. Pach) 259-268., 2005
U. Adamy, M. Hoffmann, J. Solymosi, and M. Stojakovic,: Coloring Octrees,, Computing and combinatorics; Lecture Notes in Comput. Sci (COCOON), (Springer, 2004), pp. 62-71., 2004
Z. Füredi, B. Sudakov: Extremal set systems with restricted k-wise intersections,, J of Combinatorial Theory, Ser. A, 105(2004), 143-159, 2004
Z. Füredi, Zs. Katona: Multiply intersecting families of sets,, J. Combinatorial Theory, Ser. A 106 (2004), 315-326., 2004
Z. Füredi, R. P. Kurshan:: Minimal length test vectors for multiple-fault detection,, Theoretical Computer Science, Special issue: Math. Found. of Prog. Semantics, (ed. M Mislove), 315(2004) 191-208, 2004
Z. Füredi, J-H. Kang:: Distance graph on Z^n with \ell_1 norm,, Theoretical Computer Science 319(2004) 357-366, Special issue on combinatoricsaof the discrete plane and tilings, 2004
Füredi Z: A Feuerbach körérinti az érintő köröket, KöMaL (2004) 5., 2004
J. Pach, G. Tardos, G. Tóth: Indecomposable coverings, The China--Japan Joint Conference on Discrete Geometry, Combinatorics and Graph Theory(CJCDGCGT 2005), Lecture Notes in Computer Science Springer, submitted, 2006
J. Fiala, J. Kratochvil, A. Pór: On the computational complexity of partial covers of Theta graphs, Proceedings of GRACO2005, 79-85, Electronic Notes in Discrete Mathematics, 19 (2005), 2005
A. Por, D.R. Wood: No-three-in-line-in 3D, Graph Drawing, J. Pach (ed.) Lect. Notes, Springer 3383, 395-402, 2005
J.E. Goodman, J. Pach, E. Welzl:: Combinatorial and computational geometry, Cambridge Univ Press, Cambridge, 2005
Füredi Z, Kostochka, A., Stiebitz, M., Skrekovski, R., West, D.,: Nordhaus-Gaddum-type theoremss for decompositions into many parts, J. Graph Theory. 50, 273-292., 2005
Föredi Z, Gyarfas, A, Simonyi, G.: Connected matchings and Hadwiger's conjecture, Comb., Prob, Comp. 14, 435-438., 2005
Füredi Z, Simonovits, M..: Triple systems not containing a Fano configuration, Comb., Prob, Comp. 14, 467-484., 2005
Füredi Z, Pikhurko, O., Simonovits, M..: On triple systems with independent neighbourhoods, Comb., Prob, Comp. 14, 795-813., 2005
J. Solymosi.: On sum-sets and product-sets of complex numbers sets,, J. Theorie Nombres Bordeaux. 17, 921-941 Amer.Math.Soc. V342, (Edited by J. Pach) 259-268., 2005
J. Solymosi.: On the number of sums and products, Bull. London Math. Soc. 37, 491-494, 2005
J. Solymosi.: Regularity, Uniformity, and Quasirandomness sets,, Proc. Acad. USA. 102, 8075-8076 Amer.Math.Soc. V342, (Edited by J. Pach) 259-268., 2005
J. Solymosi, Cooper, J.N.,: Collinear points in Permutations sets,, Annals Comb. 9, 169-175 Amer.Math.Soc. V342, (Edited by J. Pach) 259-268., 2005
P. Brass, W. Moser, J. Pach:: Research problems in discrete geometry, Springer, New York,, 2005
Barany I., Matousek J.,: Randomized integer convex hull, Discrete Comp. Geom. 33, 3-25, 2005
Barany I., Fukuda, K.,: A case when the union of convex polytopes is convex, Lin. Algebra and Appl., 397, 381-388, 2005
Barany I., Vempala, S., Vetta, A.,: Nash equilibrium in random gamesProc., Proc. 46th Symposium on the Foundations of Computer Science, FOCS volume 2005, 123--131, 2005
J. Pach, R. Pinchasi:: A long noncrossing path among disjoint segments in the plane, MSRI volume, Comb. Comp. Geom., Cambridge Univ Press, 495-500, 2005
J. Pach, R. Pinchasi, M. Sharir, G. Toth:: Topological graphs with no large grid, Graphs and Combinatorics, 21, 355-364, 2005
J. Pach, R. M. Sharir:: Incidences number of directions determined by a point set in $3$-space,, Haifa Workshop on Graph theory, 267-292 Symposium on Computational Geometry, ACM Press, New York, 2004, 76--85., 2005
J. Pach:: Graph drawing, Springer, Berlin, 2005
J. Pach: Directions in Combinatorila Geometry, Jahresb. Deutschen Math.-Vereinigung, 107, 215-225, 2005
J. Pach, N.Alon, R. Pinchasi, R. Radiocic, M. Sharir:: Crossing patterns in semialgebraic sets, J. Comb. Theory A 111, 310-326, 2005
j. Kara, A. Por, D.R. Wood: On the chromatic number of the visibility graph of a set of points in the plane, Discrete Comp. Geom. 34, 497-506, 2005
Barany I, Reitzner: The central limit theorem for random polytopes in a convex polytope, to appear, 0
Fiala, Jirrí; Kratochvíl, Jan; Pór, Attila: On the computational complexity of partial covers of theta graphs, Proceedings of GRACO2005, 79-85 (electronic), 2005
J. Klára, A. Pór, D. Wood: On the chromatic Number of the visibility graph of a set of points in the plane, Discrete and Computational Geometry, 34 No.3 (2005), 497-506, 2005
G. Karolyi, J. Solymosi: Erdos-Szekeres theorem with forbidden order types, Journal of Combinatorial Theory, Series A (3) 113 (2006) 455-465., 2006
Barany I, Tokushige N: The minimum area convex lattice n-gon, Combinatorica, 24 (2004), 171--185, 2004
Barany I, Van H Vu: Central limit theorems for Gaussian polytopes, to appear in Annals of Prob, 0
Barany I, Valtr P: Planar point sets with few empty convex polygons, Studia Math. Hung. 41 (2004), 243-266, 2004
Barany I,: Discrete and convex geometry, in: A Panorama of Hungarian Mathematics in the Twentith Century, ed.: J. Horvath, Bolyai Society Mathematical Studies 14 (2006), 427-456, 2006
Barany I,: Geometic applications of graph and hypergraph theory, in Combinatorial and computational geometry, (ed.: J E Goodman et al.) MSRI pulications, 52 (2005) 31--50 (Cambridge Univ. Press), 2005
Barany I, Doerr B: Balanced partitions of vector sequences, Lin. Alg. Appl. 414 (2006), 464--469, 2006
Barany I,, Prodromou M,: On maximal convex lattice polygons inscribed in a plane convex set, Israel J. Math. 154 (2006), 337--360, 2006
Barany I,: Convex bodies, random polytopes, and approximation, Chapter in Stochastic Geometry, ed. W. Weil, Springer, 2007, 2007
Barany I,: The probability that a convex body is lattice point free: a relative of Buffon's needle problem, accepted to Random Structures and Alg. (2005), 2005
Barany I, Rote G: Strictly convex drawings of planar graphs, Documenta Math. 11 (2006), 369--391, 2006
Barany I, Matousek: Quadratic lower bound for the number of colourful simplices, to appear in SIAM J. Discrete Math, 0
Barany I, Matousek: Packing cones and their negatives in space, to appear in DCG, 0
J. Pach, P. K. Agarwal, E Nevo, R. Pinchasi, M. Sharir, Sh. Smorodinsky: Lenses in arrangements of pseudo-circles and their applications, Journal of ACM 51 (2004), 139-186, 2004
J. Pach, R. Pinchasi, G. Tardos, G. Tóth: Geometric graphs with no self-intersecting path of length three, European Journal of Combinatorics 25 (2004), 793--811, 2004
J. Pach, G. Tóth: Monotone drawings of planar graphs, Journal of Graph Theory 46 (2004), 39--47., 2004
J. Pach: Geometric graph theory, Chapter 10, in: Handbook of Discrete and Computational Geometry, 2nd edition (J.E. Goodman and J. O'Rourke, eds.), CRC Press, Boca Raton, 2004, 219--238, 2004
J. Pach, B. Aronov, M. Sharir, and G. Tardos: Distinct distances in three and higher dimensions, Combinatorics, Probability and Computing 13 (2004), 283-293, 2004
J. Pach, R. Radoicic, G. Tóth: Relaxing planarity for topological graphs, in: More Sets, Graphs and Numbers, (E. Gyori, G. O. H. Katona, L. Lovasz, eds.), Bolyai Soc. Math. Studies 15, J. Bolyai Math. Society, Budapest, 2006, 285-300, 2006
J. Pach, G. Tóth: How many ways can one draw a graph?, Combinatorica 26 (2006), 559--576, 2006
J. Pach, R. Pinchasi and M. Sharir: A tight bound for the number of different directions in three dimensions, Journal of Combinatorial Theory, Ser. A 108 (2004), 1-16., 2004
J. Pach, M. Sharir: Geometric incidences, Graph Theory, Combinatorics and Algorithms -- InterdisciplinaryApplications (M. Golumbic and I. Ben-Arroyo Hartman, eds.), Springer Verlag, New York, 2005, 267-292., 2005
J. Pach, R. Radoicic, G. Tóth: A generalization of quasi-planarity, in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics 342, AMS, Providence, RI, 2004, 177--183., 2004
J. Pach, R. Radoicic, J. Vondrák: Forbidden paths and cycles in ordered graphs and matrices, Israel J. Math. 155 (2006), 309--334., 2006
J. Pach, R. Radoicic, J. Vondrak: Nearly equal distances and Szemeredi's regularity lemma, Computational Geometry: Theory and Appls. 34 (2006), 11--19, 2006
J. Pach, A. Dumitrescu, G. Tóth: The maximum number of empty congruent triangles determined by a point set, ) Revue Roumaine de Mathématiques Pures et Appliquées 50 (2005), 613-618, 2005
J. Pach, G. Tóth: Crossing number of toroidal graphs, in: Graph Drawing 2005 (P. Healy et al., eds.), Lectur334--342e Notes in Computer Science 3843, Springer, Berlin, 2006,, 2005
J. Pach: The discrete charm of geometry (In memoriam Laszlo Fejes Toth), Középiskolai Matematikai Lapok 2005/5, 2005
J. Pach, G. Calinescu, A. Dumitrescu: Reconfigurations in graphs and grids, Proc. LATIN '06 (Latin American Theoretical INformatics conference), Lecture Notes in Computer Science 3887, Springer, 2006, 262--273., 2006
J. Pach, G. Tóth: Degenerate crossing numbers, 22nd ACM Symposium on Computational Geometry, ACM Press, New York, 2006, 255--258., 2006
J. Pach, H. Brönnimann: Opposite-quadrant depth in the plane, Proceedings 15th Annual Fall Workshop on Computational Geometry (http://www.research.att.com/~suresh/fwcg05/abstracts/12.pdf)., 2006
J. Pach, D. Pálvölgyi: Bounded-degree graphs can have arbitrarily large slope numbers, Electronic J. Combinatorics 13 (1) (2006), N1., 2006
R. Anstee, Balin Fleming, Z. Füredi,A. Sali: Color critical hypergraphs and forbidden configurations, Discrete Math. and Theoretical Computer Science AE (2005) 117--122, 2005
J. Pach, G. Tóth: Comments on Fox News, Geombinatorics 15 (2006), 150-154., 2006
J. Pach, K. Böröczky G. Tóth: Planar crossing numbers of graphs embeddable in another surface, Internat. J. of Foundations of Comp. Science 17 (2006), 1005-1011, 2006
P. L. Erdös, Z. Füredi, G. O. H. Katona: Two-part and k-Sperner families: new proofs using permutations,, SIAM J. Discrete Math. 19 (2005), 489-500, 2005
Z. Füredi, A. Kündgen: Moments of graphs in monotone families, Journal of Graph Theory 51 (2006), 37-48, 2006
Z. Füredi, G. O. H. Katona: 2-bases of quadruples, Combinatorics, Computing and Probabality 15 (2006), 131--141, 2006
Z. Füredi, O. Pikhurko, and M. Simonovits: 4-books of three pages, J. of Combinatatorial Th., Ser.A 113 (2006), 882--891, 2006
Z. Füredi, A. Naor, J. Verstraete: On the Turán number for the hexagon, Advances in Math. 203 (2006), 476--496, 2006
Z. Füredi, K-W. Hwang, and P. Weichsel: A proof and generalizations of the Erdő s-Ko-Rado theoremusing the method of linearly independent polynomials, Topics in discrete mathematics, pp. 215--224, Algorithms Combin.bf 26, Springer, Berlin, 2006, 2006
Z. Füredi, Robert H. Sloan, Ken Takata, Gy. Turán: On set systems with a threshold property, Discrete Mathematics 306 (2006), 3097--3111, 2006
G. Tardos, G. Tóth: Decomposing multiple coverings with triangles, Discrete and Computational Geometry, accepted, 2006
B. Keszegh, J. Pach, D. Pálvölgyi, G. Tóth: Drawing cubic graphs with at most five slopes, Graph Drawing 2006, Lecture Notes in Computer Science, 2006
J. J. Montellano-Ballesteros, A. Pór, R. Strausz: Tverberg-type theorems for separoids, Discrete Comput. Geom., 35, No.3 (2006), 513--523, 2006
A. Pór, P. Valtr: On the Positive Fraction Erdős-Szekeres Theorem for Convex Sets, European Journal of Combinatorics, 27 (2006) 1199-1205, 2006



Back »