26.08.2015  Discrete Geometry in September
detailed...

13.01.2015  Discrete Geometry workshop
detailed...

14.09.2012  A course in measure partitions
detailed...

 We follow the works of Milena Radnovi? and Serge Tabachnikov, studying the questions when two different not necessarily symmetric norms produce the same billiard reflection law and the same billiard trajectories. It is clear from the symplectic point of view on billiards that whenever we translate or positively scale the polar of the unit ball of the norm, the billiard trajectories do not change. It remains to note that the original unit ball is then changed by a projective transformation that fixes the origin and preserves every line through the origin without changing its orientation at the origin. Our observation is connected to the previous work by the fact that a Euclidean ball centered at the origin under such a projective transformation becomes an ellipsoid of revolution about a line that has a focus at the origin. We show that the deleted product obstruction for removing r-tuple points of maps to the Euclidean space of dimension at least 2 totally vanishes if r is not a prime power. As a consequence of this, we improve the existence results of such maps without r-tuple points from pairwise disjoint faces and build stronger counterexamples to the topological Tverberg conjecture for non-prime-power r. In this note we give a version of Hao Huang's proof of the sensitivity conjecture, shedding some light on the origin of the magical matrix A in that proof. This text only contains the proof of the core fact: Consider the n-dimensional boolean cube Qn as a graph, whose edges connect pairs of vertices differing in one coordinate. Then any its induced subgraph on greater than 2n-1 (the half) vertices has degree of some vertex at least square root of n. In this paper we study so-called envy-free division problems. The classical approach to some of such problem reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster-Kuratowski-Mazurkiewicz theorem) is a boundary condition. This time we try to replace the boundary condition by a certain equivariance condition under all permutations, or a weaker condition of “pseudoequivariance”, which has some economic meaning for the problem of partitioning a segment. Such versions of the problem have positive solutions when then number of persons among whom we partition is a prime power, and in some cases we provide respective counterexamples for the case when the number of persons is not a prime power. In this paper I use the symplectic interpretation of Mahler's conjecture to establish its particular cases, for hyperplane section of l_p balls and Hanner polytopes, and for their hyperplane projections. Those particular cases (and conjecturally the general case) are related to the study of the behavior of the symplectic volume under the symplectic reduction. We study some particular cases of Viterbo's conjecture relating volumes of convex bodies and actions of closed characteristics on their boundaries, focusing on the case of a Hamiltonian of classical mechanical type, splitting into summands depending on the coordinates and the momentum separately. We manage to establish the conjecture for sublevel sets of some convex 2-homogeneous Hamiltonians of this kind and in one more relatively easy case: we also discuss open particular cases of this conjecture. This paper continues the study of bisection of measures by several hyperplanes in the Euclidean space, started in arXiv:1803.02842. A measure is bisected by an arrangement of D hyperplanes if, after properly coloring the cells of the complement of the arrangement of hyperplanes in two colors, the measure of each color is the half of the whole measure. Apart from the previously established case when the dimension n is a power of two, we establish one more similar case with slightly non-optimal number of hyperplanes. We also note that the case D=2 of this problem is equivalent to the projective ham sandwich theorem, previously established by Pavle Blagojevic and me in [arXiv:1011.0869, Theorem 10]. In this paper we consider the Hedetniemi conjecture about the chromatic number of the product of graphs, and its generalization by Zhu for hypergraphs. We verify this conjecture to certain families of graphs, and we also study the closely related conjectures about the equivariant index of the product of two Z/p-spaces, where p is a prime. For p=2, when the geometrical index is replaced by the homological index, we confirm the conjectured value of the index of the product; the same result was done independently by Alexey Volovikov. In this paper we continue to study the Gromov waist in the sense of t-neighborhoods for measures in the Euclidean space. Unlike our recent papers, now we are interested in an estimate holding for arbitrary value of t, not only asymptotically for t tending to 0. We are motivated by the famous theorem of Gromov about the waist of radially symmetric Gaussian measures and try to extend this results to other measures. In particular, it turns our possible to have a sharp estimate in the case of not necessarily radially symmetric Gaussian measure. We also provide examples of measures having no t-neighborhood waist property, including a rather wide class of compactly supported radially symmetric measures and their maps into the Euclidean space of dimension at least 2. We use a simpler form of Gromov's pancake argument to produce some estimates of t-neighborhoods of (weighted) volume-critical submanifolds in the spirit of the waist theorems, including neighborhoods of algebraic manifolds in the complex projective space. In the appendix of this paper we provide for reader's convenience a more detailed explanation of the Caffarelli theorem that we use to handle not necessarily radially symmetric Gaussian measures. In this paper we once again touch the topic of K-strong convexity, where K is a given convex body and the K-strong convex hull of a point set X is the intersection of translates of K that contain X. We investigate the Caratheodory number for K-strong convexity and prove some general facts about it. In particular, we show that this number is always greater or equal to the dimension of K. This bound is attained for nontrivial products of “generating sets”, in particular for products of convex bodies of dimension at most 2. We also give a simpler example of K with unbounded Caratheodory number and make several other observations on the topic. In this paper we continue to investigate the problem (by Nandakumar and Ramana Rao) of cutting a convex shape in the plane into m convex parts of equal areas and perimeters. In the series of previous works the existence problem was solved affirmatively for m=pk, a prime power. This paper (in its second version) establishes the result for arbitrary number of parts m. In this paper we study the following problem: How many measures in Rn can be simultaneously bisected by D hyperplanes? A measure is bisected by an arrangement of D hyperplanes if, after properly coloring the cells of the complement of the arrangement of hyperplanes in two colors, the measure of each color is the half of the whole measure. We show that when the dimension n is a power of two, a set of nD measures can be bisected simultaneously; this is tight by the dimension considerations. For other values of n we only have partial result be reducing to the case of power of two. In this paper we improve the estimate of Gluskin and Ostrover for the Ekeland-Hofer-Zehnder capacity of a convex body in the symplectic R2n. The estimate follows from a lower bound of the length of a closed characteristic on the boundary of K in the norm (gauge) with unit ball K, which is similar to what we studied in 1401.0442. In the case of centrally symmetric K we show that one of the closed characteristics of the minimal action on the boundary of K must itself be centrally symmetric. This allows to use the length lower bounds established by Schaffer. We generalize this symmetry observation to the case when K is invariant with respect to multiplication by a root of unity, under the identification R2n=Cn. In this paper we continue the work of arXiv:1006.2263 and study the involution on the real oriented or non-oriented Grassmannian of half-dimensional subspaces, sending a subspace to its orthogonal complement. This time we manage to calculate the homological index of this action for all dimensions, which allows to infer certain Borsuk-Ulam-type theorems. In this paper we study the waist theorems in the sense of Gromov for balls in the model spaces of constant curvature. In particular, we prove that for a continuous map from such an n-dimensional ball to the Euclidean space of dimension k, the (n-k)-dimensional Minkowski content of some fiber of the map is at least the volume of the (n-k)-dimensional ball of the same radius and same curvature. We also obtain some results for the balls in the spaces of bounded from above curvature (CAT-spaces) and not necessarily symmetric normed spaces. Along the way we study the behavior of the Minkowski content under Lipschitz maps between Riemannian manifolds. We consider geometrical optimization problems related to optimizing the error probability in the presence of a Gaussian noise. One famous question in the field is the “weak simplex conjecture”, saying that the regular simplex is optimal among other sets of n+1 points on the unit (n-1)-dimensional sphere. We discuss possible approaches to it, and state related conjectures about the Gaussian measure, in particular, the conjecture about minimizing of the Gaussian measure of a simplex. We also consider antipodal codes, apply the Šidák inequality and establish some theoretical and some numerical results about their optimality. We continue investigating Gromov's waist of different spaces. Several results of the paper follow the idea of Bo'az Klartag, also used by two of us in the work arxiv:1608.06279. We also extend some of the results from waists in terms of fibers of a continuous map to the waist in terms of families of cycles carrying a non-vanishing power of the fundamental cohomology class. The third direction is to address the waist in terms of the Hausdorff measure of fibers for maps into arbitrary polyhedron, with a constant given in terms of the dimension only. Dolnikov, Zivaljevic, and Vrecica established the center transversal theorem: Any m nice measures in Rn+m-1 can be linearly projected to Rn so that they have a common point with depth at least 1/(n+1) with respect to any of the projected measures. Following the previous result of Magazinov and Por, we slightly improve the constant 1/(n+1) in expense of increasing the dimension from n+m-1 to 2m+n-1 or 3m+n-1 depending on whether n+1 is a power of two or not. We use the idea of Bo'az Klartag to prove Gromov-type waist theorems for the Minkowski measure using a Lipschitz map of one measure to the other; and answer a question of Gromov about the waist of the Euclidean ball. Another tool of the proof in the fact, going back to Archimedes, that the standard projection from the (n+1)-dimensional sphere to the n-dimensional ball maps the uniform measure in the sphere to a multiple of the uniform measure in the ball. This paper develops the ideas from the previous preprints arxiv:1002.0660 and arxiv:1106.6176 about the ways to guarantee the multiplicity of a continuous map between two manifolds. This time we have done more careful calculation using the previous work of Pavle and managed to write down the characteristic classes responsible for local multiple points. Warning. We have noticed an error in the calculation and will try to correct it, possibly arriving at a different final formula for the characteristic classes. The "first selection lemma" by Imre Bárány asserts that given many points in Rn it is possible to find another point p such that the probability that it is covered by a randomly chosen simplex formed by some n+1 of the given points is at least some positive constant cn. Recently Gromov designed a new technique to prove such results, improving the constant cn. We examine Gromov’s method in order to understand the dependence of such a "heavily covered" point on parameters. We cannot prove the continuous dependence on parameters, but manage to utilize the "homological continuous dependence" of the heavily covered point. This allows us to infer some corollaries in a usual way. We also give an elementary argument to prove the simplest of these corollaries: Given several straight lines in the plane in general position, it is possible to find a point that is surrounded by a randomly chosen triple of lines with probability at least 2/9. In this note we discuss certain analogues of the Carathéodory theorem for the notion of strong convexity. In my PhD and a paper published in Russian I established such a theorem in 2001. Now we generalize that result to have an analogue of the colorful Caratéodory theorem, established for ordinary convexity by Imre Bárány, and the “very colorful theorems”, established by several people including Andreas Holmsen. These theorems require the gauge body to satisfy a certain “generating convex set” assumption introduced by Polovinkin and Balashov. This assumption is satisfied by any convex body in the plane, but in 3-space we give an example where this assumption fails and the corresponding analogue of the Carathéodory theorem also fails. We also try to give a topological criterion for one convex body to be a Minkowski summand of another. We managed to do so, but under a somewhat artificial assumption that one of the bodies is closed and the other one is open. János Pach proved that there exists a constant cd such that for any collection of finite sets X0, ... , Xd in Rd it is possible to choose the subsets Yi of Xi for every i and a point p in Rd so that |Yi| is no less than cd|Xi| and every system of representatives of the collection Y0, ... , Yd contains point p in its convex hull. This paper provides upper bounds for the constant cd by providing examples of the collection of finite sets. Actually, the example is rather straightforward, while the calculation of the constant is not so. In particular, there arises the problem of bounding from above the minimal solid angle at a vertex of arbitrary simplex in Rd. This is where my contribution allowed to improve the bound on the solid angle, given in Theorem 6 of the current version of the text. The problem of bounding the minimal solid angle of a simplex is also studied in the parallel paper of Arseniy Akopyan and myself, where precise estimates in dimension d=3 and 4 are given. This paper is described below. Also available on arxiv.org. We investigate the following question raised by Kynčl, Paták, Safernová, and Tancer: Does every simplex in Rn has a solid angle at a vertex that is no greater than the solid angle at any vertex of a regular simplex in Rn? It turned out that it is possible to answer the question affirmatively for dimensions 3 and 4. This argument uses certain facts about the isoperimetry for simplices in spherical geometry. We also formulate several generalizations for other regular polytopes. Update after peer reviewing: In turned out that we misunderstood the result on isoperimetry for spherical tetrahedra in the paper of Böhm. So the case of dimension 4 in our problem remains open. We start from the expression of the Combinatorial Nullstellensatz of Noga Alon as a certain equality, connecting a coefficient of a multivariate polynomial and its values at certain points. This formula was proposed by Fedya Petrov in our joint paper “Partitions of nonzero elements of a finite field into pairs”. In this text we observe that this formula is actually a multidimensional residue formula. This point of view allows to better understand old and prove some new results. We also mention some open (or partially open) problems about point configurations with algebraic flavor. This paper was written by my coauthors Pablo and Edgardo, who studied the question of simultaneous partitioning several measures into two (or more) equal parts in a way, similar to the “ham sandwich” and “splitting necklace” theorems. The partitions were made by iterated hypeplane cuts, where the directions of the hyperplanes were prescribed. My contribution is explained in Section 4, where we consider certain very general Voronoi partitions and make a statement that generalizes Noga Alon's “splitting necklace” theorem and Rade Živaljević's “curtain partition” theorem at the same time. Also, with a small technical effort this approach handles iterated partitions as well. In this paper we find more applications of the symplectic techniques to convex geometry. We address the Tarski-Bang problem about covering a convex body by “planks” (regions between two parallel hyperplanes) and its relatives; we examine what can and what cannot be done using the symplectic techniques. The translation of the Tarski-Bang problem to the symplectic setting, along with the results of Keith Ball, gives rise to a certain conjecture about the subadditivity property of symplectic capacities. We are not able to establish this property fully, but we prove some its particular cases. We also prove several related results with non-symplectic techniques, including one new particular case of the Tarski-Bang problem in its original form. We continue to study billiards in convex bodies, presumably related to the Mahler conjecture on the product of volumes of a convex body and its polar. This time we consider norms that are not symmetric with respect to the origin, one may call this case flat Finsler billiard. Our goal is to make lower bounds on the length of a closed billiard trajectory in a convex body. The technique of Karoly Bezdek and Daniel Bezdek, developed in the Euclidean case, works in this asymmetric norm case as well. This allows to give elementary proofs of some known results (previously proved with symplectic techniques) and prove the tight estimate for the shortest closed billiard trajectory in a convex body measured with the norm taking this convex body as a unit ball. The third version of the paper has changed its title. The previous title was “Elementary results in non-reflexive Finsler billiards”. In this text we consider geometric joins of a family of m finite point sets X1, X2, ..., Xm in d-dimensional Euclidean space. This is just the set of all possible convex combinations of systems of representatives of this family. It is not hard to prove that for sufficiently large m this set becomes contractible, and we prove this for m>d(d+1)/2, and also prove that for m>d(d+1) it is startshaped. But we conjecture that a geometric join of m sets is contractible already for m=d+1, and we manage to prove this conjecture for d = 2 and d = 3. Here is an arxiv link to this paper. Rade Živaljević proved a version of ham sandwich theorem in arbitrary dimension, named &lsqou;the curtain partition theorem’. Its 2-dimensional case is rather simple: Given two nice measures in the plane and a 3-fan, one can choose an angle of the 3-fan and translate it so that the resulting angle cuts precisely half of every measure. We extend this result in the plane by considering fans with arbitrary number of angles. In some cases it is possible to prove the positive assertion, and in some cases we find counterexamples. Here is a link to the arxiv version of this paper. In this paper I observe that the "quantitative covering dimension" theorems, like the Lebesgue theorem about the cube and the Knaster-Kuratowski-Mazurkiewicz theorem about the simplex, have a simple explanation in terms of toric geometry. This provides a unified point of view on such results and allows to generalize them to some extent. In particular, it gives an answer to a question of Domotor Palvolgyi on mathoverflow.net. Available at arxiv.org. This paper is merged from the two texts: arXiv:1011.4762 of myself and arXiv:1010.4611 of Alfredo Hubard and Boris Aronov. In this version we make a clearer and slightly more general statements of the main theorems and spend some effort to explain the proof of the topological lemma. Our approach to the topological lemma is the same that D.B. Fuks and V.A. Vasiliev used to establish its particular cases. Another, more combinatorial approach to the topological lemma can be found in the paper arXiv:1202.5504 of P. Blagojevic and G. Ziegler. Available at arxiv.org. In this paper we present a new approach to the Mahler conjecture relating it to the Viterbo conjecture from symplectic geometry. My coauthors have already established the correspondence between the shortest closed billiard length in a convex body K measured with a norm and the Hofer-Zehnder symplectic capacity c(KxT), where T is the unit ball of the dual norm. In this paper we establish the following lower bound by non-symplectic methods: this value is at least 4 when K is the unit ball of a norm and T is its polar body (unit ball of the dual norm). In symplectic geometry, Viterbo conjectured that the volume of a convex body X in R2n is at least c(X)n/n!. If it is true then vol KxT ≥ 4n/n! for a centrally symmetric convex body in Rn and its polar, this is the classical Mahler conjecture. So to finish the Mahler conjecture it remains to prove the Viterbo conjecture. Available at arxiv.org. B. Knaster conjectured that for a continuous function f on the round sphere of dimension n-1 and a finite subset X of n points on the sphere it is always possible to find an isometric copy X' of X on the sphere so that f becomes constant on X'. This conjecture turned out to be wrong, as proved by Boris Kashin and Stanislaw Szarek, though some particular cases were established. We analyze the known approaches to particular cases of Knaster's problem and notice that in many cases the set X is required to be an orbit of a finite group action. Morevover, this group G is usually a p-torus, that is a product of several copies of the same cyclic group of prime order. We then observe that a weak form of the Knaster conjecture (when the dimension of the sphere is allowed to be arbitrarily larger than the cardinality of X) holds for sets X that can be included into an orbit of a p-torus, we call them spherical sub-p-toral sets. In the Euclidean Ramsey theory, that studies monochromatic sets in an arbitrary coloring of the Euclidean space in a given number of colors, the notion of a suborbit of a finite group action already proved to be useful. By borrowing ideas from Ramsey theory we prove weak Knaster properties of non-equatorial triangles in spheres, and of simplices in Euclidean spaces. We also find some sets already on S1 that are not sub-p-toral for any p and show that Knaster-type approaches to the Dvoretzky theorem are still insufficient. Available at arxiv.org. In this paper we make the following observation about the topology of the Stiefel manifold of orthonormal k-frames in Rn: The Schwarz genus of the natural action of Wk on this space is maximal possible, that is equal to its dimension plus one. Here Wk is the group that permutes the frame vectors and changes signs of some of them. This result has certain geometric consequences about critically outscribed parallelotopes for a given convex body and Birkhoff–James orthogonal bases in normed spaces, see the definitions in the text. In both cases we estimate the number of such objects from below by n( n -1)/2+1, where n is the dimension. This paper is also available on arxiv.org. In this paper we start from M. Gromov's method of contraction in the space of (co)cycles, and observe that this method applies well to the classical theorems of Borsuk-Ulam and Hopf. This method turns out to be useful and allows us to prove certain generalizations of these theorems. Using those topological results, we study some analogues of the notion of the Urysohn width and the Gromov waist for metric spaces, and prove some results in this direction. However, in the field of widths and waists there remain a lot of open questions. The center point theorem asserts that for a finite point set X in Rd one may select the center point c so that every halfspace containing c must contain at least 1/(d+1) of the points of X. In one of my previous papers the "dual" center point theorem was proved: For a finite set X of hyperplanes in general position one may select the center point c so that every ray starting at c intersects at least 1/(d+1) members of X. This theorem does not follow from projectively dualizing the original center point theorem. Its projective dualization gives another fact, I let the reader check it. Benjamin Matschke proposed to make a theorem that interpolates between the original center point theorem and its "dual" version. The main idea is to start from a subspace V of RPd and find another subspace W of complementary dimension d-dimV-1 so that every pair of hyperplanes H and J containing V and W respectively does not cut too little of the given finite point set X. Here it is miportant that a pair of hyperplanes partition the projective space in two parts. So we prove a general projective center point theorem as well as the corresponding version of the Tverberg theorem. Then we give a very general theorem that also includes the Tverberg transversal theorem as a particular case, and stude several similar problems. Available at arxiv.org. We study the possibility to cut the same fraction of d+1 measures in Rd. One particular case is cutting by a hyperplane a same (not prescribed) fraction of every measure. In general it is not possible, but under some additional assumptions in term of geometric permutations this is possible. The other case is to cut a prescribed fraction α of every measure with a convex set. We show that (without other assumptions) this is possible for α=1/m with positive integer m and is not possible for other α. Some remaining open problems are also outlined in this paper. This paper is also available on arxiv.org. The Carathéodory theorem asserts that a point x belongs to the convex hull of a subset X in Rn if and only if it belongs to the convex hull of some at most n+1 element subset of X. Several cases were known when the constant n+1 can be made less. For example, the Fenchel theorem asserts that this constant is at most n for a compact X whose components cannot be separated by a hypeplane. In this note we consider results resembling that theorem of Fenchel. We also prove the corresponding versions of the colorful Carathéodory theorem and give a Tverberg type theorem for families of convex compacta. This paper is also available on arxiv.org. We consider a d-dimensional cube Q subdivided into nd small cubes in an obvious way. Then we color the small cubes into m+1 colors and want to have some lower bound on the size of a monochromatic connected component. For m=d-1 (which is d colors) it is well known that one monochromatic connected component connects two opposite facets of Q thus giving the lower bound n. For m=1 (2 colors) Matousek and Privetivy established the lower bound approximately nd-1. In this paper Gromov's method of contraction in the space of cycles allows to prove the lower bound f(d,m) nd-m with some non-optimal coefficient f(d, m). This paper is also available at arxiv.org. The Turan number ex(H, n) of a graph H is the maximum number of edges in a graph G on n vertices having no subgraph isomorphic to H. For full bipartite graphs H=Ks,t there exist constructions of G with large number of edges given by an algebraic relation between two points in Fpd. In this paper we study such relations on Rd or Cd that are defined over integers and therefore give graphs over Fp, for which asymptotic (as p grows) number of edges can be found. We show that any hypersurface in RdxRd must contain a grid (which is a product of finite sets SxT) of size approximately (2d-3)x(2d-3) by a topological reason. This rules out the construction of corresponding Ks,s-free graphs (interesting from the point of view of the Turan problem) with s at least 4. On the other hand we construct hypersurfaces in RdxRd with no dxd4d-grid. The construction of hypersurfaces without dxd2 grids, for example, remains an open question. This paper is also available on arxiv.org. In this paper we consider the following question: Does every convex polytope P admits an inscribed regular octahedron? By “inscribed” we mean that the vertices of the octahedron are on the boundary of P. For smooth convex bodies in place of P, and more generally, for smooth embedded 2-spheres in space the answer was already shown to be positive by Vladimir Makeev. But the usual “going to the limit” argument does not allow to deduce the result for a plytope from the result for a smooth surface. In this paper we make going to the limit carefully enough to answer the question positively for simple polytopes P. The case of nonsimple P generally remains open. This paper is also available at arxiv.org A couple of typical geometric problems about coincidence were posed by B. Grünbaum: How many affine diameters of a convex body in Rn must have a common point? How many centers (in some reasonable sense) of hyperplane sections of a convex body in Rn must coincide? One possible approach to such problems is to find topological reasons for multiple coincidences for a continuous map between manifolds of equal dimension. In other words, we need topological estimates for the multiplicity of a map. In these particular problems we have to estimate from below the multiplicity of any continuous map from the projective space to the sphere of the same dimension. For certain values of n some nontrivial lower bounds are obtained; though they are far from n+1, which was conjectured by Grünbaum. For convex partitions of a convex body B we try to put a homothetic copy of B into each set of the partition so that the sum of homothety coefficients is at least 1. In the plane it is possible for any partition, while in higher dimensions we need certain restrictions on the partition. This problem has much in common with the Bang conjecture. The difference is that in the Bang conjecture instead of a partition of B into convex parts we consider a covering of B by rather simple objects: planks between pairs of parallel hyperplanes. Even in the plane these two problems are not equivalent; so we make no advance in the Bang conjecture. You may also download this paper from arxiv.org. In this paper we study higher topological complexity of spheres. Less formally, we study the following question: Can one span any m-tuple of distinct points in the sphere Sn by a continous image of the wedge of m segments so that everything depends continuously on the m-tuple. This question for m=2 was studied before as a natural question of planning the motion between two points on the sphere. We prove that the answer to this question in negative in most cases. The proof is based on examining the maps between cohomology of certain spaces and the generalized Hopf invariant of maps. In fact, we do not know any construction giving a positive answer to this question. The smallest remaining open case is m=3 and n=4. If you do not have access to the journal version, you can download the paper from arxiv.org. In this paper we generalize the sphere waist theorem of Gromov and the Borsuk--Ulam type measure partition lemma of Gromov--Memarian for maps to manifolds. Informally, this result claims that for any continuous map f : Sn-> M to a manifold of dimension m < n the preimage of some point is at least as "large" as the standard (n-m)-dimensional subsphere of Sn. In this note the following result is proved: Suppose d+1 vertices are distributed in Rd randomly and independently; then there exists a "central point" c such that the probability for this point to be covered by the random siimplex is at least pd=1/(d+1)!. In case of discrete and equal distributions for all vertices this theorem was proved by Imre Barany with estimate on pd of order 1/(d+1)d+1. That proof used the Tverberg theorem and the colorful Caratheodory theorem. Boros and Furedi improved the esitmate for d=2 to 2/9, and Janos Pach considered a similar problem for d+1 vertices with different distributions. In 2010 Mikhail Gromov published another approach to this problem and obtained better bounds (the same as in this note). But the proofs were not elementary and not accessible to most experts in discrete geometry. In this note the proof of Gromov is translated to the elementary language, its size dramatically shrunk. Another difference in this note is considering different distributions for different vertices. If you do not have access to SpringerLink, you can download the paper from arxiv.org. In this paper I prove several results of the following type: any d measures in Rd can be partitioned simultaneously into k equal parts by a convex partition (this particular result was proved before by Pablo Soberon). Another example is: any convex body in the plane can be partitioned into q parts of equal areas and perimeters provided q is a prime power. The above questions we posed by A. Kaneko, M. Kano, R. Nandakumar, N. Ramana Rao, and I. Barany. These results are also inspired by the generalization of the Borsuk-Ulam theorem by M. Gromov and Y. Memarian, in this paper I provide a theorem that further generalizes their result. I also tried to deduce the theorem of Noga Alon about partitioning measures on the segment in a similar fashion, but did not succeed. By the way there arose a question about polynomials in one variable that may be interesting itself. The discrete central point theorem claims the following: for a set X of n=(d+1)(r-1)+1 points in d-dimensional Euclidean space there exists a central point с such that any halfspace containing c contains at least r points of X. A strong generalization of this theorem is the Tverberg theorem. The Tverberg theorem also has a generalization: the topological Tverberg theorem for continuous maps from (n-1)-dimensional simplex to d-dimensional Euclidean space; the number r is required to be a prime power in this theorem. In this paper a topological generalization of the central point theorem is proved for continuous maps from (n-1)-dimensional simplex to some d-dimensional metric space (not necessarily Euclidean), here n=(d+1)(r-1)+1 and r is arbitrary. Similar analogues of the Tvergerb theorem for maps to d-dimensional metric spaces are considered; the number n has to be larger in such theorems. If you do not have access to sciencedirect, you can download the paper from arxiv.org. The Rattray theorem claims that every odd continuous map Sn-1->Sn-1 maps some orthonormal basis to another orthonormal basis. Makeev used the underlying topological fact to prove another theorem: for any two absolutely continuous probabilistic measures in Rn there exists a set of n hyperplanes such that any two of them partition each measure into 4 equal parts. In this paper we extend such results for the case of several maps or measures. Of course, in the Rattray type theorem we cannot obtain a basis, but we may ask for the larges possible k such that an orthonormal frame of k vectors is mapped to another orthonormal k-frame by every map. The measure partition result should be changed accordingly; moreover, we prove a result that interpolates between the result of Makeev and the results of Ramos-Zivaljevic-Vrecica-Mani-Levitska on measure partitions. Another result that is worth mentioning is the “projective ham sandwich theorem” that relates partitioning of several measures by two hyperplanes in the projective space to the problem of embedding of this projective space to the Euclidean space. This paper is also available at arxiv.org. In this paper we prove the following fact, known as the Gromov-Milman conjecture: for every positive integer k and positive even d there exists a positive integer n=n(d,k) such that any polynomial of degree d in n variables equals (x12+...+xn2)d/2 after restriction to a k-dimensional linear subspace of Rn. We also consider similar results for odd degrees and complex polynomials (known as the Birch theorem), and improve the bounds for n(d,k) in such cases. Note that in the main case of even d we do not have the explicit value of n(d,k) at the moment. The results proved by the ordinary cohomology calculations are due to Dol'nikov, the case of even degree is made by me, with use of the generalized Borsuk-Ulam theorem for p-groups. If you do not have access to SpringerLink, you can download the paper from arxiv.org. In this paper I continue to study the analogues of the central point theorem for intersecting a family of convex sets by rays, see the previous paper on this subject. In the previous paper the problem was: for a given family of convex compact sets, find a point such that every ray starting at this point intersects a large enough fraction of the family. Here we want a point such that any ray starting at this point misses a large enough fraction of the family. In the first case the sufficient condition was the d-intersection property in Rd, in this case the sufficient condition is an upper bound for the covering multiplicity of the family. Actually, in this paper the analogue of the central point theorem is deduced from the corresponding analogue of the Tverberg theorem, the latter is proved by topological methods. This paper is also available at arxiv.org. The real Grassmann manifold G2nn of n-dimensional linear subspaces in R2n has a natural involution, given by the orthogonal complement. In this paper I estimate from above and from below the homological index of this involution. When n is a power of two, the estimates coincide and the index is 2n-1. These estimates have straightforward geometrical consequences. Let us give an example: if n is a power of two and K1,...,K2n-1 are convex compact sets in R2n, then there exist two orthogonal n-subspaces L and M, such that for any i the projections of Ki to L and M have equal measures. In this paper I again study the configuration spaces of manifolds, with applications to regular embeddings, that is continuous maps f : M->R^m such that images of every pairwise distinct k points are affinely (linearly) independent. In this work some new obstructions to existence of regular embeddings are given in terms of some characteristic classes of the tangent bundle of M. I consider the subspace Q^q(M) of the q-configuration space of a manifold M that can be identified with a bundle over M with fiber Q^q(R^m), where Q^q(R^m) is a certain submanifold of the q-configuration space of R^m (m = dim M, q is a power of 2). The cohomology of Q^q(M) (or its parts) can be computed to give some explicit results on regular embeddings. The explicit cohomology computations are also applied to the problem of multiple self-coincidences of a continuous map between manifolds, which was studied in one of my previous papers. In this paper we study affine planes of dimension m that intersect all members of a given family F of convex compacta. Such planes are called m-transversals. The main lemma (Theorem 1) in this paper claims that if a family F has “many” m-transversals (in terms of nonvanishing of a certain cohomology class on the space of m-transversals), then F has at least one r-transversal. Here r The above result (together with the Schubert calculus and the Lusternik-Schnirelmann category of the Grassmannian) allows to make some generalizations of the colorful Helly theorem to the case, when the number of colors if less than d+1 (d is the dimension of Rd in question). My contribution to this paper is the proof of Theorem 1, some remarks on the colorful-Helly-type theorems, and the case of complex vector space Cd and complex transversals. This paper is also available at arxiv.org. In this paper we prove two theorems. Informally, they claim that the nonzero elements of a finite field with odd characteristic can be partitioned into pairs with prescribed difference (maybe, with some alternatives) in each pair. We also consider some generalizations of these results to packing translates in a finite or infinite field. My contribution to this paper is the topological proofs. Fedor Petrov has given the algebraic proofs for the partitions of Fp* into pairs, and established several similar results with the same method. If you have no access to Springerlink then you may download the paper from arxiv.org. In this paper a measure of non-convexity for a simple polygonal region in the plane is introduced. Informally it can be described as the minimal (negative) rotation of the tangent vector when traveling along the boundary anticlockwise. It is proved that for “not far from convex” regions this measure does not decrease under the Minkowski sum operation, and guarantees that the Minkowski sum has no “holes”. If you do not have access to SpringerLink, you can download the paper from arxiv.org. The paper is accepted for publication in Journal of Mathematical Sciences. In this paper the following modification of the Knaster problem is considered: describe all four-point sets X in a two-dimensional sphere S such that for any continuous function f : S->R there exists a rotation that puts X into a level line of the function f. V.V. Makeev conjectured that this claim is true for any four points, lying on a single circle, this is a necessary condition for linear f. Here a counterexample is given for this conjecture. Another conjecture of Makeev claims that a quadrangle can be inscribed into any smooth closed simple curve on the plane iff it is inscribed into a circle.This conjecture does not have counterexamples by now, some new particular cases of this conjecture are solved positively. In this paper the following question is studied: consider a continuous map f :M-> N between two manifolds. Are there some sufficient conditions for existence of a coincident q-tuple, i.e. a q-tuple of pairwise distinct points x_1,..., x_q in M such that f(x_1) = f(x_2) = ... = f(x_q)? I show that there are certain characteristic classes of the vector bundle f^*TN-TM that guarantee the existence of a coincident q-tuple for f, resembling similar results on singularities of smooth maps. In particular, I prove some non-trivial lower bound on the multiplicity for a continuous map of a real projective space of certain dimension into a Euclidean space of same or moderately larger dimension. Some application to estimating the Krasnosel'skii-Schwarz genus of configuration spaces of manifolds are also given, continuing my previous results. In this paper we study configuration-like spaces, i.e. the spaces of ordered q-tuples of points in some topological space X with k-wise conincidences forbidden. In fact we mostly work with the case of the Euclidean space X=R^n. We study the measure of complexity for such spaces: the genus in the sense of Krasnosel'skii-Schwarz-Clapp-Puppe with respect to the action of some transitive permutation group on the q-tuples. Here we mostly give the upper bounds, the lower bounds were studied in my paper in “Topology Apps”. The upper bounds for the genus imply some results of Borsuk-Ulam-Cohen-Lusk type for self-coincidences of a continuous map, some versions of the Knaster problem are also considered. This paper is also available from arxiv.org. The paper was rejected in “Discrete and Computational Geometry”, the referee considered the main topological lemma known. In this paper the colored KKM theorem is generalized to give an analogue of KKM theorem for the product of two simplices. Actually, an important particular case of this lemma (when the simplices have equal dimensions) was known before, the method of proof being quite well-known. Still, the main lemma was not known before in the form, as stated in this paper. This lemma has some corollaries, concerning cutting a family of figures in the plane by a set of straight lines, parallel to the coordinate axes. This paper continues the series on inscribing crosspolytopes and partitioning measures into equal parts. The case of Z_2^k symmetry is considered here. It turns out that such a symmetry is not sufficient (unlike the case of (Z_p)^k for odd p). To obtain some results we need a larger noncommutative group of symmetry, isomorphic to D_8 \times (Z_2)^{k-1}. If you do not have access to SpringerLink, you can download the paper from arxiv.org. in this paper a family F of convex compact sets in Rd is considered, such that any d of the sets in F have a common point, this is the d-intersection property, the minimal weakening of the condition of Helly's theorem. The analogues of the central point theorem and Tverberg's theorem for such families are proved: A point p in Rd is found, such that any curve that passes through p and is unbounded, intersects at least about 1/(d+1) of the sets in F. Some analogues of the central transversal theorem are also proved. The author's version is available at arxiv.org Some results on the topology of the canonical bundle over the Grassmann variety are proved. They generalize the Borsuk-Ulam theorem on coverings of a sphere and a ball. Some corollaries are deduced: Sufficient conditions for existence of a flat k-transversal for a family of n+1 compacts in R^n; Sufficient conditions for dividing n absolutely continuous probabilistic measures in R^n into parts of given size by a hyperplane; Some Helly-type theorems for flat transversals. The English version of this paper is available at arxiv.org. Some new cases of the Knaster conjecture on the functions on a sphere are proved. The set that is put into a level surface of the function is the orbit of a p-torus action with one point omitted. The proof is mainly based on the previous proofs of A.Yu. Volovikov for the Knaster conjecture for (full) p-tori orbits. This paper is also available at arxiv.org. This paper develops the ideas of the paper about billiards (see above). The configuration-like spaces of smooth manifolds are considered. The lower bounds on the cohomological index i_G, introduced by A.Yu. Volovikov, on the genus in the sense of Krasnosel'skii-Schwarz, and the equivariant Lyusternik-Schnirelmann category of such spaces are given, with respect to the action of p-tori by permuting points in the configuration. The action of the symmetric group is also considered and some little generalization of the results of Fuks and Vassiliev on the Krasnosel'skii-Schwarz genus of the classical configuration space is proved. The author's version can be downloaded from arxiv.org, if you do not have access to ScienceDirect. In this paper the billiards in smooth convex bodies in R^n are considered. Consider the closed trajectories that make m reflections at the boundary per period. Using the Lyusternik-Schnirelmann theory, in the modification of Krasnosel'skii-Schwarz, I obtain the lower bound (n-2)(m-1)+2 for the number of distinct such trajectories, in the case of prime m. This paper is also available at arxiv.org. The Russian version is also submitted to (and seems to be lost in) Mathematical Notes. In this paper I prove that any smooth hypersurface S in Rd, which is diffeomorphic to an n-1-dimensional sphere, admits an inscribed crosspolytope (high-dimensional octahedron) in the case, when n is an odd prime power. Possible weakenings of the smoothness condition are considered. The case of n=2k is considered in a separate paper (see below). In this paper a theorem on partitioning a measure in R^n into 2n equal parts by a system of cones is proved. The system of cones is obtained from some symmetrical system of cones, centered at the origin, by rigid motions. The results are mainly based on A.Yu. Volovikov's proof of the particular case of Knaster's problem on the functions on a sphere, where the orbits of p-tori were considered. The author's version can be downloaded from arxiv.org, if you do not have access to SpringerLink. In the published version the proof in Section 4 was incorrect; in this version it is corrected. In this review some applications of algebraic topology to the combinatorial and convex geometry are considered. In particular, some author's results in the area are cited. The author's version (in Russian) can be downloaded here. In this paper the “dual” version of the central point theorem is considered: Suppose n hyperplanes in general position are given in R^d. Then there exists a point x such that any ray starting at x intersects at least n/(d+1) of the given hyperplanes. Some generalizations of this result are also proved, that can be called the "dual" Tverberg theorem, and the "dual" central transversal theorem. Besides, some generalization of the Brouwer fixed point theorem is proved for several fiber-wise maps of a vector bundle into itself. The published version of this paper contained an incorrect proof of the lemma on existence of a compact convex set that is mapped into itself by a given set of orthogonal projections onto affine hyperplanes. Later it was pointed out to me by Imre Barany that this lemma is known since 1984. The corrected English version is available at arxiv.org. Helly's theorem states that a family of convex compact sets in R^d has non-empty intersection iff every its subfamily of size at most d+1 has non-empty intersection. In this paper we study the families such that every subfamily of size at most d has non-empty intersection, and try to find some upper bounds for the piercing number (see above). A family of hyperplanes in general position shows that there cannot be a uniform upper bound for the piercing number, still the upper bounds can be found for families of balls, homothets of a single simplex, and some other families. The author's version of this paper can be downloaded here, if you do not have access to SpringerLink. In this paper we consider results of the following type: Suppose a topological space X is mapped to a d-dimensional metric space Y. Then there exists a point p in Y such that the Lyusternik-Schnirelmann category of its preimage (or a neighborhood of its preimage) in X is at least the category of X, divided by d+1. It is proved that such results hold for other integer functions on open subsets of topological spaces, that are similar to the Lyusternik-Schnirelmann category in the sense of three axioms (monotonicity, subadditivity, and the upper bound for the disjoint union). The corrected English version of this paper is available at arxiv.org. In this paper the Tverberg transversal conjecture and its generalizations are considered. Some particular cases of this conjecture are proved. The Tverberg transversal conjecture is stated as follows: Suppose that m+1 finite sets S_0, ... , S_m in R^d are given. Then each set S_i can be partitioned into r_i parts S_i1, ... , S_ir_i so that the convex hulls of all the sets S_ij can be intersected by a single m-flat (affine subspace of dimension m), such a flat is called m-transversal. The requirement that the cardinality of S_i is at least (r_i-1)(d-m+1) + 1 is also needed. In this paper this conjecture is proved for the case, when the numbers r_i are powers of the same prime. If this prime is odd, than the number d-m is required to be even. Other cases of this conjecture, for example when the numbers r_i are equal to the same prime, were known before. The author's version can be downloaded here, if you do not have access to SpringerLink. In this paper the results on the conjecture of A. Bezdek, and polytope partitiones are generalized. Actually, a "colored" generalization of the Knaster-Kuratowski-Mazurkiewicz theorem (KKM) theorem is proved, which implies some of the previous results directly. In this paper the ideas around the problem of Proizvolov and the cojecture of A. Bezdek are developed. In particular, it is proved that any convex polytope P of unit volume with facets F_i can be partitioned into convex sets A_i so that the following holds: The intersection of each A_i with the boundary of P equals F_i; The volumes of A_i are equal to the given positive numbers with unit sum. The author's version can be downloaded here, if you do not have access to SpringerLink. This paper is a piece of PhD thesis, where two definitions of M-strong convexity are compared. It is shown that they are equivalent for generating sets M. The thesis is mainly composed of the previous publications. The chapter about the strong convexity, generating sets, and bodies of constant width in Banach spaces is rewritten, some of the results are formaluted for any Banach space instead of R^n. In this paper I prove some generalizations of the following well-known problem (as far as I known, by Proizvolov). Let P be a convex n-gon in the plane, and suppose n points inside P are given. Then there exists a bijection between the points and the edges of P, such that all the corresponding triangles (formed by a point and its respective edge) cover P. There is another version, when triangles are required to be pairwise disjoint, instead of covering P. The problem has generalizations to higher dimensions. The question of A. Bezdek was: what is changed if the n points are not required to be inside P. This paper answers this question, along with some other results. In this paper the notion of M-strongly convex set is studied. Let M be a closed convex set, then any intersection of a family of translates of M is called M-strongly convex set. It was shown before that M-strongly convex sets behave well, if the set M is generating (see above). In particular, in this paper an analogue of the Caratheodory theorem is established for M-strong covexity. It should be mentioned, that in this paper a lemma was proved, that could be of its own interest. Let A and B be convex compact sets in R^n, then the set difference of A and A+B (here is the Minkowski sum) is a contractible set. In this paper the following type of closed convex sets is studied. The closed convex set M is called "generating" if any intersection of a finite number of translates of M is a summand of M w.r.t. the Minkowski sum. There is a large number of examples of generating sets, unit balls are generating, and any Cartesian product of generating sets is again generating. The main result of this paper claims that in the definition of generating sets it suffices to consider intersections of two translates instead of arbitrary number of translates. In this paper a conjecture of Grunbaum is proved. Consider a family F of translates of a convex compact set in the plane, such that every two members of the family have a common point. Then the family F can be pierced by three points. The term "pierced" means that a set T of three points exists, such that any set K of the family F has non-empty intersection with T. In general, a point set, that "pierces" a family of sets F is called a "transversal" of F, the minimal size of a transversal for F is called the "piercing number" of F. The results were also published in Russian in Proceedings of the seminars at St.-Petersburg Department of the Mathematical Institute.
© 2009 Roman Karasev