Combinatorial and convex geometry

Help

Back »

Details of project

Identifier

83767

Type

Principal investigator

Bárány, Imre

Title in Hungarian

Kombinatorikus es diszkret geometria

Title in English

Combinatorial and convex geometry

Keywords in Hungarian

Konvexitas, diszkret geometria, geometriai grafok, veletlen es racs politopok

Keywords in English

Convexity, discrete geometry, geometric graphs, random and lattice polytopes

Discipline

Mathematics (Council of Physical Sciences)	100 %
Ortelius classification: Geometry

Panel

Mathematics and Computing Science

Department or equivalent

Alfréd Rényi Institute of Mathematics

Participants

Barát, János
Tóth, Géza

Starting date

2011-03-01

Closing date

2015-02-28

Funding (in million HUF)

7.678

FTE (full time equivalent)

2.60

state

closed project

Summary in Hungarian

Terveink között hét problémakör vizsgálata és megoldása szerepel. A határidõk folyamatosak.

1. Többszörös fedések felbontása: Egy síkbeli P halmazt fedés-felbonthatónak nevezünk, ha van
olyan k konstans, hogy ha a sík P eltoltjaival k-szor van fedve, akkor ez a fedés felbontható
két egyszeres fedésre. Minden ismert fedés-felbonthatósági eredmény, (pozitív és negatív
egyaránt) poligonokra vonatkozik, egyetlen kivétel az egységkör. Szeretnénk kiterjeszteni
ezeket az eredményeket más síkbeli halmazokra is.

2. Konvex rácspolitopokra vonatkozó extremális problémák: Két konvex rácspolitop ekvivalens,
ha az egyiket átviszi a másikba egy rácstartó affin leképezés. Meg szeretnénk javítani az
N(d,V)-re vonatkozó ismert becsléseket. Itt N(d,V) jelöli az R^d-beli, legföljebb V térfogatú
rácspolitopok ekvivalencia osztályainak számát.

3. Konvex testekbe irt véletlen politopok: Tovább szeretnénk vizsgálni a véletlen politopokon
értelmezett funkcionálok viselkedését. Például meg kellene határozni a véletlen politop
térfogatának szórását.

4. Az egész konvex burok: Meg szeretnénk határozni a véletlen egész konvex burok mindenféle
dimenziós lapjai számának várható értékét. Ez valószínûleg Buffon típusú sztochasztikus
geometriai problémákhoz vezet.

5. A metszési szám: A metszési szám különbözõ definícióinak kapcsolatát, a közöttûk levõ
összefüggéseket szeretnénk jobban megérteni.

6. A metszési szám és kromatikus szám: A Négy Szín Tétel egyszerû általánosításaként
belátható, hogy a kromatikus szám felülrõl becsülhetõ a metszési szám segítségével. Ezt az
összefüggést szeretnénk mélyebben megérteni.

7. Topológiai módszerek a diszkrét és konvex geometriában: például adott két valószínûségi
mérték a síkon, van-e olyan 3- vagy 4-legyezõ amelynél minden szektor ugyanolyan (elõírt)
mértékû mindkét mértékben? Pozitív eredményeket és ellenpéldákat remélünk, továbbá arra az
esetre való kiterjesztést, mikor csak egy mérték van, és egy a szektorokon értelmezett
függvény.

Summary

This is a short description of the 7 problems we propose to investigate. The work on them is
spread out evenly on the whole period.

1. Decomposing multiple coverings: A planar set P is said to be cover-decomposable if there
is a constant k such that every k-fold covering of the plane with translates of P can be
decomposed into two coverings. With the exception of the unit disc, all cover-decomposability
results (positive and negative as well) are for polygons, almost nothing is known for other
planar sets. We plan to extend these results to other planar sets.

2. Extremal problems for convex lattice polytopes: Two polytopes are equivalent if there is a
lattice preserving affine transformation carrying one polytope to the other. We plan to
improve the known bounds on N(d,V), the number of equivalence classes of convex lattice
polytopes in R^d of volume at most V.

3. Random polytopes in convex bodies: We wish to further investigate the behaviour of various
functionals associated with random polytopes. For instance we plan to determine the variance
of the volume of random polytopes.

4. The integer convex hull: We want to determine the expected number of facets, and smaller
dimensional faces as well, of the randomized integer convex hull of convex bodies. This will
probably lead to Buffon type problems in stochastic geometry.

5. Crossing numbers: We plan to understand better the relationships of different versions of
the crossing number.

6. Crossing number and chromatic number: As an easy generalization of the Four Color Theorem,
one can give an upper bound on the chromatic number in terms of the crossing number. We would
like to understand better this connection between the two parameters.

7. Topological methods in discrete and convex geometry: for instance, given two probability
measures in the plane, is there a (convex) 3-fan or 4-fan so that each sector of the the same
(prescribed) measure in both measures? Positive results and counterexamples are expected, and
extensions to the case of one measure and a continuous function on the sectors.

Final report

Results in Hungarian

G. Toth, with I. Kovacs, proved that every closed, centrally symmetric convex polygon P is coverdecomposable, in a very strong and general sense. With Pach and Radoicic, Toth investigated modifications of the thrackle problem, where touching edges are also allowed. They proved tight bounds on the number of edges of such a graph. With D. Gerbner they showed that any set of n points in the plane can be separated by O(n log log n/log n) convex sets, and this bound is almost tight. With J. Kyncl, J. Pach and R. Radoicic, G. Toth constructed non-extendable simple topological graphs with only linear number of edges. I. Barany answered a question of V I Arnold on the number of (equivalence classes) of lattice polytopes in R^d of volume exactly V. He extended Caratheodory's classical theorem in many directions (with R. Karasev). Significant new results were reached in the geometry of Alexandrov spaces: every point is a farthest point from some other point of the space (with Itoh et al). Barany (with J Matousek and A Por) has determined the order of magnitude of a geometric Ramsey number. I Barany, E Roldan-Pensado and G Toth have extended the famous Erdos-Szekeres theorem to finite families of lines in the plane. The outcome is a surprise: the number in question is roughly 4^n, while in the original case (that is, for point sets) it is only known to be between 2^n and 4^n. In summary, several significant results have been proved in the directions targeted by the proposal.

Results in English

Toth G. es Kovacs I. belattak, hogy minden zart, kozeppontosan szimmetrikus konvex sokszog fedes-felbonthato, nagyon altalanos feltetelek mellett. Pach, Radoicic es Toth a thrackle problema olyan valtozatait tanulmanyoztak, ahol az elek kozotti erintes is megengedett. Pontos korlatokat adtak egy ilyen graf elszamara. Gerbner es Toth bebizonyitottak, hogy n pont a sikon szeparalhato O(n log log n/log n) konvex halmazzal, es ez a korlat majdnem pontos. Kyncl, Pach, Radoicic es Toth konstrualtak olyan nem bovitheto egyszeru topologikus grafot, amelynek csak linearis szamu ele van. I. Barany megvalaszolta V I Arnold kerdeset: Hany R^d-beli pontosan V terfogatu racspolitop van (ekvivalenciatol eltekintve). Tobb iranyban is kiterjeszette Caratheodory klasssikus tetelet (kozos munka R. Karasevval). Fontos uj eredmenyt bizonyitott Alexandrov terekrol: a ter minden pontja legtavolabbi pont a ter valamely masik pontjatol (Barany, Itoh et al). Matousekkel and Porral kozosen meghataroztak egy geometriai Ramsey szam nagysagrendjet. Barany, Roldan-Pensado es Toth altalanositottak a hires Erdos-Szekeres tetelt sikbeli egyenesek veges halmazara. Az eredmeny meglepo: a kerdeses szam lenyegeben 4^n, mig az eredeti (ponthalmazokra vonatkozo) esetben csak annyit tudunk, hogy 2^n es 4^n kozott van. Osszefoglalva, szamos jelentos eredmenyt sikerult igazolnunk a palyazatban kijelolt iranyokban.

Full text

https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=83767

Decision

Yes

List of publications

I. Barany, V. Grinberg: Block partitions of sequences, Israel J. Math, 2014

I Barany, E Roldan Pensado: Longest convex lattice chains in triangles, Computational Geometry: Theory and Appl., 2014

I. Barany, J. Jeronimo-Castro: Helly type theorems for the sum of unit vectors, Lin Alg. Appl., 2015

I. Barany, Liping Yuan: Volumes of lattice polytopes and a question of V. I. Arnold, Acta Math. Hung., 2014

I. Barany, D. Hug, R. Schneider: Affine diameters of convex bodies, accepted in Proc. AMS, 2014

I. Barany, R Schneider: Typical curvature behaviour of bodies of constant width, Advances in Math., 2015

I. Barany, J Matousek, A. Por: Curves in R^d intersecting every hyperplane at most d+1 times, accepted in JEMS (2014) (with J Matousek and A P'or), accepted in J . European Math. Soc, 2014

I. Barany, A. Holmsen, R. Karasev: Topology of the geometric join, {\it}, {\bf } (2013) (with, accepted in Discrete Comp. Geom., 2014

I. Barany, F Fodor, L. Montejano, A. Martinez-Perez, D. Oliveros, A. Por: Fractional Helly for boxes in R^d, Comp. Geom. Theory Appl., 2015

I. Barany, R. Fabilla-Monroy, B. Vogtenuber: Antipodal coverings of spheres, (with ), accepted in the Dolbilin'70 volume, 2014

I. Barany, M. Laczkovich: Magic mirrors, dense diameteres, Baire category, accepted in J Convex Anal., 2014

D. Palvolgyi, J. Pach, G. Toth:: Survey on the decomposition of of multiple coverings,, Geometry--Intuitive, Discrete and Convex, Bolyai Math. Soc. Studies, 2013

E. Ackerman, J. Pach, R. Pinchasi, R. Radoicic, G. Toth: A note on coloring line arrangements, Electronic Journal of Combinatorics, 2014

J. Kyncl, J. Pach, R. Radoicic, G. Toth: Saturated simple and $k$-simple topological graphs, Computational Geometry: Theory and Applications, 2015

I. Kovacs, G. Toth: Multiple coverings with closed polygons, Electronic Journal of Combinatorics, 2015

I. Barany, E. Roldan Pensado, G. Toth: Erdos-Szekeres theorem for lines, submitted, Discrete Computational Geometry, 2015

I. Barany, J-I. Ito, A. Vilcu, T. Zamfirescu:: Every points is critical,, accepted in Advances in Math., 2013

J. Pach, G. Toth: Monotone crossing number, Moscow Journal of Combinatorics and Number Theory 2, 18-33, 2012

G. Toth: A better bound for the pair-crossing number, Thirty Essays in Geometric Graph Theory (J. Pach ed.) Springer, New York, 563-567, 2013

J. Pach, R. Radoicic, G. Toth: Tangled thrackles, Proc. EGC 2011, 45-53, 2012

I Barany: On a question of V. I. Arnold, Acta Math Hung 137, 72–81, 2012

I Barany, E Roldan Pensado: Longest convex lattice chains in triangles, Computational Geometry: Theory and Appl. 47 367–376, 2014

I Barany, J Pach: Homogeneous selections from hyperplanes, JCT B 104, 81–87, 2011

I Barany, E Roldan Pensado:: On a forgotten question from a famous paper of Erdos,, Discrete and Comp. Gometry, 50, 253–261, 2013

I. Barany J-F. Marckert, M. Reitzner ,: Many empty triangles have a common edge,, Discrete and Comp. Geometry, 50, 244–252, 2013

I. Barany, J-I. Ito, A. Vilcu, T. Zamfirescu:: Every points is critical,, Advances in Math. 235, 390–397, 2013

G. Tóth: A better bound for the pair-crossing number, In: J Pach (szerk.) 30 Essays in Geometric Graph Theory. 563-567, 2013

D Gerbner, G Toth: Separating families of convex sets., COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 46: pp. 1056-1058., 2013

Černý J; Kynčl J; Tóth G: Improvement on the Decay of Crossing Numbers, GRAPHS AND COMBINATORICS (ISSN: 0911-0119) 29: (3) pp. 365-371., 2013

Pach. J; Tóth G.: Monochromatic empty triangles in two-colored point sets, DISCRETE APPLIED MATHEMATICS (ISSN: 0166-218X) 161: pp. 1259-1261., 2013

Bárány I.; Fodor F.; Montejano, L.; Oliveros, D.; Pór, A.: Colourful and Fractional (p, q)-theorems, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) In press Published online: 12 November 2013, 2014

Bárány I.; Pach J.: Homogeneous selections from hyperplanes, JOURNAL OF COMBINATORIAL THEORY SERIES B (ISSN: 0095-8956) 104: pp. 81-87., 2014

BárányI.; Ginzburg BD; Grinberg VS: 2013 unit vectors in the plane, DISCRETE MATHEMATICS (ISSN: 0012-365X) &: p. &. Article in Press, 2014

Bárány I; Steiger W: On the variance of random polygons, COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS (ISSN: 0925-7721) 46: (2) pp. 173-180., 2013

Bárány I.; Blagojević P; Dimitrijević Blagojević A: Functions, Measures, and Equipartitioning Convex k-Fans, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) 49: (2) pp. 382-401., 2013

Bárány I.; Roldán-Pensado E: A Question from a Famous Paper of Erdős, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) 50: (1) pp. 253-261., 2013

Bárány I; Marckert J-F; Reitzner M: Many Empty Triangles have a Common Edge, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) 50: (1) pp. 244-252., 2013

Bárány I; Itoh J-I; Vîlcu C; Zamfirescu T: Every point is critical, ADVANCES IN MATHEMATICS (ISSN: 0001-8708) 235: pp. 390-397., 2013

Bárány I; Zamfirescu T: Holding Circles and Fixing Frames, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) 50: (4) pp. 1101-1111., 2013

Bárány I.; Zamfirescu T: On circles holding convex bodies, LIBERTAS MATHEMATICA (ISSN: 0278-5307) 33: pp. 21-26., 2013

I Barany: On a question of V. I. Arnold, Acta Math Hung, 2012

I Barany, E Roldan Pensado: Longest convex lattice chains in triangles, submitted to Computational Geometry: Theory and Appl., 2011

I Barany, J Pach: Homogeneous selections from hyperplanes, submitted to JCT B, 2011

I Barany, R Karasev: Notes on the Caratheodory number, Discrete and Comp. Geometry, 2012

J. Cerny, J. Kyncl, G. Toth: Improvement on the decay of crossing numbers, to appear in Graphs and Combinatorics, 2012

J. Pach, G. Toth: Monotone crossing number, Graph Drawing 2011, Lecture Notes in Computer Science 7034 (2012) 278-289, 2012

G. Toth: A better bound for the pair--crossing number, Proceedings of the Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto, 473-477, 2011

J. Pach, R. Radoicic, G. Toth: Tangled thrackles, Geombinatorics 21, 4, 2012

I Barany, E Roldan Pensado:: On a forgotten question from a famous paper of Erdos,, accepted in Discrete and Comp. Gometry, 2013

I. Barany:: Tensors, colours, octahedra, Pisa conference, 2013

I. Barany J-F. Marckert, M. Reitzner ,: Many empty triangles have a common edge,, submitted in Discrete and Comp. Geometry, 2013

I. Barany, R Schneider:: Universal points of convex bodies and bisectors in Minkowski spaces,, accepted in Advances in Geometry, 2013

I. Barany, P. Blagojevic and A. Dmitrijevic Blagojevic:: Functions, measures, and equipartitioning convex $k$-fans,, Discrete and Comp. Geometry, 2013

Events of the project

2012-11-14 13:25:28

Résztvevők változása

Back »