BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Márton Elekes

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.CAmath.LOmath.GNmath.PRDatabasesmath.DSmath.GR

Catalog footprint

Research overview

31works
7topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

31 publications

preprint2022arXiv

An analysis of the SIGMOD 2014 Programming Contest: Complex queries on the LDBC social network graph

This report contains an analysis of the queries defined in the SIGMOD 2014 Programming Contest. We first describe the data set, then present the queries, providing graphical illustrations for them and pointing out their caveats. Our intention is to document our lessons learnt and simplify the work of those who will attempt to create a solution to this contest. We also demonstrate the influence of this contest by listing followup works which used these queries as inspiration to design better algorithms or to define interesting graph queries.

Open access
preprint2016arXiv

Bruckner--Garg-type results with respect to Haar null sets in C[0,1]C[0,1]

A set A⊂C[0,1]\mathcal{A}\subset C[0,1] is \emph{shy} or \emph{Haar null } (in the sense of Christensen) if there exists a Borel set B⊂C[0,1]\mathcal{B}\subset C[0,1] and a Borel probability measure μμ on C[0,1]C[0,1] such that A⊂B\mathcal{A}\subset \mathcal{B} and μ(B+f)=0μ\left(\mathcal{B}+f\right) = 0 for all f∈C[0,1]f \in C[0,1]. The complement of a shy set is called a \emph{prevalent} set. We say that a set is \emph{Haar ambivalent} if it is neither shy nor prevalent. The main goal of the paper is to answer the following question: What can we say about the topological properties of the level sets of the prevalent/non-shy many f∈C[0,1]f\in C[0,1]? The classical Bruckner--Garg Theorem characterizes the level sets of the generic (in the sense of Baire category) f∈C[0,1]f\in C[0,1] from the topological point of view. We prove that the functions f∈C[0,1]f\in C[0,1] for which the same characterization holds form a Haar ambivalent set. In an earlier paper we proved that the functions f∈C[0,1]f\in C[0,1] for which positively many level sets with respect to the Lebesgue measure λλ are singletons form a non-shy set in C[0,1]C[0,1]. The above result yields that this set is actually Haar ambivalent. Now we prove that the functions f∈C[0,1]f\in C[0,1] for which positively many level sets with respect to the occupation measure λ∘f−1λ\circ f^{-1} are not perfect form a Haar ambivalent set in C[0,1]C[0,1]. We show that for the prevalent f∈C[0,1]f\in C[0,1] for the generic y∈f([0,1])y\in f([0,1]) the level set f−1(y)f^{-1}(y) is perfect. Finally, we answer a question of Darji and White by showing that the set of functions f∈C[0,1]f \in C[0,1] for which there exists a perfect Pf⊂[0,1]P_f\subset [0,1] such that f′(x)=∞f'(x) = \infty for all x∈Pfx \in P_f is Haar ambivalent.

Open access
preprint2016arXiv

Characterization of order types of pointwise linearly ordered families of Baire class 1 functions

In the 1970s M. Laczkovich posed the following problem: Let B1(X)\mathcal{B}_1(X) denote the set of Baire class 11 functions defined on an uncountable Polish space XX equipped with the pointwise ordering. Characterize the order types of the linearly ordered subsets of B1(X).\text{Characterize the order types of the linearly ordered subsets of $\mathcal{B}_1(X)$.} The main result of the present paper is a complete solution to this problem. We prove that a linear order is isomorphic to a linearly ordered family of Baire class 11 functions iff it is isomorphic to a subset of the following linear order that we call ([0,1]↘0<ω1,<altlex)([0,1]^{<ω_1}_{\searrow 0},<_{altlex}), where [0,1]↘0<ω1[0,1]^{<ω_1}_{\searrow 0} is the set of strictly decreasing transfinite sequences of reals in [0,1][0, 1] with last element 00, and <altlex<_{altlex}, the so called \emph{alternating lexicographical ordering}, is defined as follows: if (xα)α≤ξ,(xα′)α≤ξ′∈[0,1]↘0<ω1(x_α)_{α\leq ξ}, (x'_α)_{α\leq ξ'} \in [0,1]^{<ω_1}_{\searrow 0}, and δδ is the minimal ordinal where the two sequences differ then we say that (xα)α≤ξ<altlex(xα′)α≤ξ′  ⟺  (δ is even and xδ<xδ′) or (δ is odd and xδ>xδ′). (x_α)_{α\leq ξ} <_{altlex} (x'_α)_{α\leq ξ'} \iff (δ\text{ is even and } x_δ<x'_δ) \text{ or } (δ\text{ is odd and } x_δ>x'_δ). Using this characterization we easily reprove all the known results and answer all the known open questions of the topic.

Open access
preprint2015arXiv

A new fractal dimension: The topological Hausdorff dimension

We introduce a new concept of dimension for metric spaces, the so-called topological Hausdorff dimension. It is defined by a very natural combination of the definitions of the topological dimension and the Hausdorff dimension. The value of the topological Hausdorff dimension is always between the topological dimension and the Hausdorff dimension, in particular, this new dimension is a non-trivial lower estimate for the Hausdorff dimension. We examine the basic properties of this new notion of dimension, compare it to other well-known notions, determine its value for some classical fractals such as the Sierpinski carpet, the von Koch snowflake curve, Kakeya sets, the trail of the Brownian motion, etc. As our first application, we generalize the celebrated result of Chayes, Chayes and Durrett about the phase transition of the connectedness of the limit set of Mandelbrot's fractal percolation process. They proved that certain curves show up in the limit set when passing a critical probability, and we prove that actually `thick' families of curves show up, where roughly speaking the word thick means that the curves can be parametrized in a natural way by a set of large Hausdorff dimension. The proof of this is basically a lower estimate of the topological Hausdorff dimension of the limit set. For the sake of completeness, we also give an upper estimate and conclude that in the non-trivial cases the topological Hausdorff dimension is almost surely strictly below the Hausdorff dimension. Finally, as our second application, we show that the topological Hausdorff dimension is precisely the right notion to describe the Hausdorff dimension of the level sets of the generic continuous function (in the sense of Baire category) defined on a compact metric space.

Open access
preprint2015arXiv

Hausdorff and packing dimension of fibers and graphs of prevalent continuous maps

The notions of shyness and prevalence generalize the property of being zero and full Haar measure to arbitrary (not necessarily locally compact) Polish groups. The main goal of the paper is to answer the following question: What can we say about the Hausdorff and packing dimension of the fibers of prevalent continuous maps? Let KK be an uncountable compact metric space. We prove that the prevalent f∈C(K,Rd)f\in C(K,\mathbb{R}^d) has many fibers with almost maximal Hausdorff dimension. This generalizes a theorem of Dougherty and yields that the prevalent f∈C(K,Rd)f\in C(K,\mathbb{R}^d) has graph of maximal Hausdorff dimension, generalizing a result of Bayart and Heurteaux. We obtain similar results for the packing dimension. We show that for the prevalent f∈C([0,1]m,Rd)f\in C([0,1]^m,\mathbb{R}^d) the set of y∈f([0,1]m)y\in f([0,1]^m) for which dim⁡Hf−1(y)=m\dim_H f^{-1}(y)=m contains a dense open set having full measure with respect to the occupation measure λm∘f−1λ^m \circ f^{-1}, where dim⁡H\dim_H and λmλ^m denote the Hausdorff dimension and the mm-dimensional Lebesgue measure, respectively. We also prove an analogous result when [0,1]m[0,1]^m is replaced by any self-similar set satisfying the open set condition. We cannot replace the occupation measure with Lebesgue measure in the above statement: We show that the functions f∈C[0,1]f\in C[0,1] for which positively many level sets are singletons form a non-shy set in C[0,1]C[0,1]. In order to do so, we generalize a theorem of Antunović, Burdzy, Peres and Ruscher. As a complementary result we prove that the functions f∈C[0,1]f\in C[0,1] for which dim⁡Hf−1(y)=1\dim_H f^{-1}(y)=1 for all y∈(min⁡f,max⁡f)y\in (\min f,\max f) form a non-shy set in C[0,1]C[0,1]. We also prove sharper results in which large Hausdorff dimension is replaced by positive measure with respect to generalized Hausdorff measures, which answers a problem of Fraser and Hyde.

Open access
preprint2015arXiv

Naively Haar null sets in Polish groups

Let (G,⋅)(G,\cdot) be a Polish group. We say that a set X⊂GX \subset G is Haar null if there exists a universally measurable set U⊃XU \supset X and a Borel probability measure μμ such that for every g,h∈Gg, h \in G we have μ(gUh)=0μ(gUh)=0. We call a set XX naively Haar null if there exists a Borel probability measure μμ such that for every g,h∈Gg, h \in G we have μ(gXh)=0μ(gXh)=0. Generalizing a result of Elekes and Steprāns, which answers the first part of Problem FC from Fremlin's list, we prove that in every abelian Polish group there exists a naively Haar null set that is not Haar null.

Open access
preprint2015arXiv

Ranks on the Baire class ξξ functions

In 1990 Kechris and Louveau developed the theory of three very natural ranks on the Baire class 11 functions. A rank is a function assigning countable ordinals to certain objects, typically measuring their complexity. We extend this theory to the case of Baire class ξξ functions, and generalize most of the results from the Baire class 1 case. We also show that their assumption of the compactness of the underlying space can be eliminated. As an application, we solve a problem concerning the so called solvability cardinals of systems of difference equations, arising from the theory of geometric decompositions. We also show that certain other very natural generalizations of the ranks of Kechris and Louveau surprisingly turn out to be bounded in ω1ω_1. Finally, we prove a general result showing that all ranks satisfying some natural properties coincide for bounded functions.

Open access
preprint2014arXiv

Decomposing the real line into Borel sets closed under addition

We consider decompositions of the real line into pairwise disjoint Borel pieces so that each piece is closed under addition. How many pieces can there be? We prove among others that the number of pieces is either at most 3 or uncountable, and we show that it is undecidable in ZFCZFC and even in the theory ZFC+c=ω2ZFC + \mathfrak{c} = ω_2 if the number of pieces can be uncountable but less than the continuum. We also investigate various versions: what happens if we drop the Borelness requirement, if we replace addition by multiplication, if the pieces are subgroups, if we partition (0,∞)(0,\infty), and so on.

Open access
preprint2014arXiv

Haar null sets without GδG_δ hulls

Let GG be an abelian Polish group, e.g. a separable Banach space. A subset X⊂GX \subset G is called Haar null (in the sense of Christensen) if there exists a Borel set B⊃XB \supset X and a Borel probability measure μμ on GG such that μ(B+g)=0μ(B+g)=0 for every g∈Gg \in G. The term shy is also commonly used for Haar null, and co-Haar null sets are often called prevalent. Answering an old question of Mycielski we show that if GG is not locally compact then there exists a Borel Haar null set that is not contained in any GδG_δ Haar null set. We also show that GδG_δ can be replaced by any other class of the Borel hierarchy, which implies that the additivity of the σσ-ideal of Haar null sets is ω1ω_1. The definition of a generalised Haar null set is obtained by replacing the Borelness of BB in the above definition by universal measurability. We give an example of a generalised Haar null set that is not Haar null, more precisely we construct a coanalytic generalised Haar null set without a Borel Haar null hull. This solves Problem GP from Fremlin's problem list. Actually, all our results readily generalise to all Polish groups that admit a two-sided invariant metric.

Open access
preprint2013arXiv

Answer to a question of Kolmogorov

More than 80 years ago Kolmogorov asked the following question. Let E⊆R2E\subseteq \mathbb{R}^{2} be a measurable set with λ2(E)<∞λ^{2}(E)<\infty, where λ2λ^2 denotes the two-dimensional Lebesgue measure. Does there exist for every ε>0\varepsilon>0 a contraction f ⁣:E→R2f\colon E\to \mathbb{R}^{2} such that λ2(f(E))≥λ2(E)−ελ^{2}(f(E))\geq λ^{2}(E)-\varepsilon and f(E)f(E) is a polygon? We answer this question in the negative by constructing a bounded, simply connected open counterexample. Our construction can easily be modified to yield the analogous result in higher dimensions.

Open access
preprint2013arXiv

Haar null sets and the consistent reflection of non-meagreness

A subset XX of a Polish group GG is called \emph{Haar null} if there exists a Borel set B⊃XB \supset X and Borel probability measure μμ on GG such that μ(gBh)=0μ(gBh)=0 for every g,h∈Gg,h \in G. We prove that there exists a set X⊂RX \subset \mathbb{R} that is not Lebesgue null and a Borel probability measure μμ such that μ(X+t)=0μ(X + t) = 0 for every t∈Rt \in \mathbb{R}. This answers a question from David Fremlin's problem list by showing that one cannot simplify the definition of a Haar null set by leaving out the Borel set BB. (The answer was already known assuming the Continuum Hypothesis.) This result motivates the following Baire category analogue. It is consistent with ZFCZFC that there exist an abelian Polish group GG and a Cantor set C⊂GC \subset G such that for every non-meagre set X⊂GX \subset G there exists a t∈Gt \in G such that C∩(X+t)C \cap (X + t) is relatively non-meagre in CC. This essentially generalises results of Bartoszyński and Burke-Miller.

Open access
preprint2012arXiv

Reconstructing geometric objects from the measures of their intersections with test sets

Let us say that an element of a given family $\A$ of subsets of Rd\R^d can be reconstructed using nn test sets if there exist T1,...,Tn⊂RdT_1,...,T_n \subset \R^d such that whenever $A,B\in \A$ and the Lebesgue measures of A∩TiA \cap T_i and B∩TiB \cap T_i agree for each i=1,...,ni=1,...,n then A=BA=B. Our goal will be to find the least such nn. We prove that if $\A$ consists of the translates of a fixed reasonably nice subset of Rd\R^d then this minimum is n=dn=d. In order to obtain this result we reconstruct a translate of a fixed function using dd test sets as well, and also prove that under rather mild conditions the measure function $f_{K,θ} (r) = \la^{d-1} (K \cap \{x \in \RR^d : <x,θ> = r\})$ of the sections of KK is absolutely continuous for almost every direction θθ. These proofs are based on techniques of harmonic analysis. We also show that if $\A$ consists of the magnified copies rE+trE+t (r≥1,t∈Rd)(r\ge 1, t\in\R^d) of a fixed reasonably nice set E⊂RdE\subset \R^d, where d≥2d\ge 2, then d+1d+1 test sets reconstruct an element of $\A$. This fails in R\R: we prove that an interval, and even an interval of length at least 1 cannot be reconstructed using 2 test sets. Finally, using randomly constructed test sets, we prove that an element of a reasonably nice kk-dimensional family of geometric objects can be reconstructed using 2k+12k+1 test sets. A example from algebraic topology shows that 2k+12k+1 is sharp in general.

Open access
preprint2011arXiv

A cardinal number connected to the solvability of systems of difference equations in a given function class

Let RR\R^\R denote the set of real valued functions defined on the real line. A map D:RR→RRD: \R^\R \to \R^\R is a {\it difference operator}, if there are real numbers ai,bi (i=1,...,n)a_i, b_i \ (i=1,..., n) such that (Df)(x)=∑i=1naif(x+bi)(Df)(x)=\sum_{i=1}^n a_i f(x+b_i) for every f∈RRf\in \R^\R and x∈Rx\in \R. A {\it system of difference equations} is a set of equations S=Dif=gi:i∈IS={D_i f=g_i : i\in I}, where II is an arbitrary set of indices, DiD_i is a difference operator and gig_i is a given function for every i∈Ii\in I, and ff is the unknown function. One can prove that a system SS is solvable if and only if every finite subsystem of SS is solvable. However, if we look for solutions belonging to a given class of functions, then the analogous statement fails. For example, there exists a system SS such that every finite subsystem of SS has a solution which is a trigonometric polynomial, but SS has no such solution. This phenomenon motivates the following definition. Let F{\cal F} be a class of functions. The {\it solvability cardinal} $\solc (\iF)$ of F{\cal F} is the smallest cardinal κκ such that whenever SS is a system of difference equations and each subsystem of SS of cardinality less than κκ has a solution in F{\cal F}, then SS itselfhas a solution in F{\cal F}. In this paper we determine the solvability cardinals of most function classes that occur in analysis. As it turns out, the behaviour of $\solc ({\cal F})$ is rather erratic. For example, $\solc (\text{polynomials})=3$ but $\solc (\text{trigonometric polynomials})=ω_1$, $\solc ({f: f\ \text{is continuous}}) = ω_1$ but $\solc ({f: f\ \text{is Darboux}}) =(2^ω)^+$, and $\solc (\R^\R)=ω$. We consistently determine the solvability cardinals of the classes of Borel, Lebesgue and Baire measurable functions, and give some partial answers for the Baire class 1 and Baire class αα functions.

Open access
preprint2011arXiv

A covering theorem and the random-indestructibility of the density zero ideal

The main goal of this note is to prove the following theorem. If AnA_n is a sequence of measurable sets in a σσ-finite measure space (X,A,μ)(X, \mathcal{A}, μ) that covers μμ-a.e. x∈Xx \in X infinitely many times, then there exists a sequence of integers nin_i of density zero so that AniA_{n_i} still covers μμ-a.e. x∈Xx \in X infinitely many times. The proof is a probabilistic construction. As an application we give a simple direct proof of the known theorem that the ideal of density zero subsets of the natural numbers is random-indestructible, that is, random forcing does not add a co-infinite set of naturals that almost contains every ground model density zero set. This answers a question of B. Farkas.

Open access
preprint2011arXiv

Borel sets which are null or non-σσ-finite for every translation invariant measure

We show that the set of Liouville numbers is either null or non-σσ-finite with respect to every translation invariant Borel measure on $\RR$, in particular, with respect to every Hausdorff measure $\iH^g$ with gauge function gg. This answers a question of D. Mauldin. We also show that some other simply defined Borel sets like non-normal or some Besicovitch-Eggleston numbers, as well as all Borel subgroups of $\RR$ that are not FσF_σ possess the above property. We prove that, apart from some trivial cases, the Borel class, Hausdorff or packing dimension of a Borel set with no such measure on it can be arbitrary.

Open access
preprint2011arXiv

Can we assign the Borel hulls in a monotone way?

A \emph{hull} of A⊂[0,1]A \subset [0,1] is a set HH containing AA such that λ∗(H)=λ∗(A)λ^*(H)=λ^*(A). We investigate all four versions of the following problem. Does there exist a monotone (wrt. inclusion) map that assigns a Borel/GδG_δ hull to every negligible/measurable subset of [0,1][0,1]? Three versions turn out to be independent of ZFC (the usual Zermelo-Fraenkel axioms with the Axiom of Choice), while in the fourth case we only prove that the nonexistence of a monotone GδG_δ hull operation for all measurable sets is consistent. It remains open whether existence here is also consistent. We also answer a question of Z. Gyenes and D. Pálvölgyi which asks if monotone hulls can be defined for every chain (wrt. inclusion) of measurable sets. We also comment on the problem of hulls of all subsets of [0,1][0,1].

Open access
preprint2011arXiv

Chains of Baire class 1 functions and various notions of special trees

Following Laczkovich we consider the partially ordered set $\iB_1(\RR)$ of Baire class 1 functions endowed with the pointwise order, and investigate the order types of the linearly ordered subsets. Answering a question of Komjáth and Kunen we show (in ZFCZFC) that special Aronszajn lines are embeddable into $\iB_1(\RR)$. We also show that under Martin's Axiom a linearly ordered set L\mathbb{L} with ∣L∣<2ω|\mathbb{L}|<2^ω is embeddable into $\iB_1(\RR)$ iff L\mathbb{L} does not contain a copy of ω1ω_1 or ω1∗ω_1^*. We present a ZFCZFC-example of a linear order of size 2ω2^ω showing that this characterisation is not valid for orders of size continuum. These results are obtained using the notion of a compact-special tree; that is, a tree that is embeddable into the class of compact subsets of the reals partially ordered under reverse inclusion. We investigate how this notion is related to the well-known notion of an $\RR$-special tree and also to some other notions of specialness.

Open access
preprint2011arXiv

Continuous horizontally rigid functions of two variables are affine

Cain, Clark and Rose defined a function $f\colon \RR^n \to \RR$ to be \emph{vertically rigid} if $\graph(cf)$ is isometric to $\graph (f)$ for every c≠0c \neq 0. It is \emph{horizontally rigid} if $\graph(f(c \vec{x}))$ is isometric to $\graph (f)$ for every c≠0c \neq 0 (see \cite{CCR}). In an earlier paper the authors of the present paper settled Janković's conjecture by showing that a continuous function of one variable is vertically rigid if and only if it is of the form a+bxa+bx or a+bekxa+be^{kx} ($a,b,k \in \RR$). Later they proved that a continuous function of two variables is vertically rigid if and only if after a suitable rotation around the z-axis it is of the form a+bx+dya + bx + dy, a+s(y)ekxa + s(y)e^{kx} or a+bekx+dya + be^{kx} + dy ($a,b,d,k \in \RR$, k≠0k \neq 0, $s : \RR \to \RR$ continuous). The problem remained open in higher dimensions. The characterization in the case of horizontal rigidity is surprisingly simpler. C. Richter proved that a continuous function of one variable is horizontally rigid if and only if it is of the form a+bxa+bx ($a,b\in \RR$). The goal of the present paper is to prove that a continuous function of two variables is horizontally rigid if and only if it is of the form a+bx+dya + bx + dy ($a,b,d \in \RR$). This problem also remains open in higher dimensions. The main new ingredient of the present paper is the use of functional equations.

Open access
preprint2011arXiv

Covering locally compact groups by less than $2^\om$ many translates of a compact nullset

Gruenhage asked if it was possible to cover the real line by less than continuum many translates of a compact nullset. Under the Continuum Hypothesis the answer is obviously negative. Elekes and Steprāns gave an affirmative answer by showing that if CEKC_{EK} is the well known compact nullset considered first by Erd\H os and Kakutani then $\RR$ can be covered by $\cof(\iN)$ many translates of CEKC_{EK}. As this set has no analogue in more general groups, it was posed as an open question whether such a result holds for uncountable locally compact Polish groups. In this paper we give an affirmative answer in the abelian case. More precisely, we show that if GG is a nondiscrete locally compact abelian group in which every open subgroup is of index at most $\cof(\iN)$ then there exists a compact set CC of Haar measure zero such that GG can be covered by $\cof(\iN)$ many translates of CC. This result, which is optimal in a sense, covers the cases of uncountable compact abelian groups and of nondiscrete separable locally compact abelian groups. We use Pontryagin's duality theory to reduce the problem to three special cases; the circle group, countable products of finite discrete abelian groups, and the groups of pp-adic integers, and then we solve the problem on these three groups separately. In addition, using representation theory, we reduce the nonabelian case to the classes of Lie groups and profinite groups, and we also settle the problem for Lie groups. We remark that M.~Abért recently gave an affirmative answer for profinite groups.

Open access
preprint2011arXiv

Hausdorff measures of different dimensions are isomorphic under the Continuum Hypothesis

We show that the Continuum Hypothesis implies that for every 0<d1≤d2<n0<d_1\leq d_2<n the measure spaces $(\RR^n,\iM_{\iH^{d_1}},\iH^{d_1})$ and $(\RR^n,\iM_{\iH^{d_2}},\iH^{d_2})$ are isomorphic, where $\iH^d$ is dd-dimensional Hausdorff measure and $\iM_{\Hd}$ is the σσ-algebra of measurable sets with respect to $\Hd$. This is motivated by the well-known question (circulated by D. Preiss) whether such an isomorphism exists if we replace measurable sets by Borel sets. We also investigate the related question whether every continuous function (or the typical continuous function) is Hölder continuous (or is of bounded variation) on a set of positive Hausdorff dimension.

Open access
preprint2011arXiv

Is Lebesgue measure the only σσ-finite invariant Borel measure?

R.D.Mauldin asked if every translation invariant σσ-finite Borel measure on $\RR^d$ is a constant multiple of Lebesgue measure. The aim of this paper is to show that the answer is "yes and no", since surprisingly the answer depends on what we mean by Borel measure and by constant. We present Mauldin's proof of what he called a folklore result, stating that if the measure is only defined for Borel sets then the answer is affirmative. Then we show that if the measure is defined on a σσ-algebra \emph{containing} the Borel sets then the answer is negative. However, if we allow the multiplicative constant to be infinity, then the answer is affirmative in this case as well. Moreover, our construction also shows that an isometry invariant σσ-finite Borel measure (in the wider sense) on $\RR^d$ can be non-σσ-finite when we restrict it to the Borel sets.

Open access
preprint2011arXiv

Less than 2ω2^ω many translates of a compact nullset may cover the real line

We answer a question of Darji and Keleti by proving that there exists a compact set $C_0\subset\RR$ of measure zero such that for every perfect set $P\subset\RR$ there exists $x\in\RR$ such that (C0+x)∩P(C_0+x)\cap P is uncountable. Using this C0C_0 we answer a question of Gruenhage by showing that it is consistent with ZFCZFC (as it follows e.g. from $\textrm{cof}(\iN)<2^ω$) that less than 2ω2^ω many translates of a compact set of measure zero can cover $\RR$.

Open access
preprint2011arXiv

Level Sets of Differentiable Functions of Two Variables with Non-vanishing Gradient

We show that if the gradient of $f:\RR^2\rightarrow\RR$ exists everywhere and is nowhere zero, then in a neighbourhood of each of its points the level set $\{x\in\RR^2:f(x)=c\}$ is homeomorphic either to an open interval or to the union of finitely many open segments passing through a point. The second case holds only at the points of a discrete set. We also investigate the global structure of the level sets.

Open access
preprint2011arXiv

On a converse to Banach's Fixed Point Theorem

We say that a metric space (X,d)(X,d) possesses the \emph{Banach Fixed Point Property (BFPP)} if every contraction f:X→Xf:X\to X has a fixed point. The Banach Fixed Point Theorem says that every complete metric space has the BFPP. However, E. Behrends pointed out \cite{Be1} that the converse implication does not hold; that is, the BFPP does not imply completeness, in particular, there is a non-closed subset of $\RR^2$ possessing the BFPP. He also asked \cite{Be2} if there is even an open example in $\RR^n$, and whether there is a 'nice' example in $\RR$. In this note we answer the first question in the negative, the second one in the affirmative, and determine the simplest such examples in the sense of descriptive set theoretic complexity. Specifically, first we prove that if $X\su\RR^n$ is open or $X\su\RR$ is simultaneously $F_\si$ and $G_\de$ and XX has the BFPP then XX is closed. Then we show that these results are optimal, as we give an $F_\si$ and also a $G_\de$ non-closed example in $\RR$ with the BFPP. We also show that a nonmeasurable set can have the BFPP. Our non-$G_\de$ examples provide metric spaces with the BFPP that cannot be remetrised by any compatible complete metric. All examples are in addition bounded.

Open access
preprint2011arXiv

The structure of continuous rigid functions of two variables

A function $f:\RR^n \to \RR$ is called \emph{vertically rigid} if graph(cf)graph(cf) is isometric to graph(f)graph (f) for all c≠0c \neq 0. We settled Janković's conjecture in a separate paper by showing that a continuous function $f:\RR \to \RR$ is vertically rigid if and only if it is of the form a+bxa+bx or a+bekxa+be^{kx} ($a,b,k \in \RR$). Now we prove that a continuous function $f:\RR^2 \to \RR$ is vertically rigid if and only if after a suitable rotation around the z-axis f(x,y)f(x,y) is of the form a+bx+dya + bx + dy, a+s(y)ekxa + s(y)e^{kx} or a+bekx+dya + be^{kx} + dy ($a,b,d,k \in \RR$, k≠0k \neq 0, $s : \RR \to \RR$ continuous). The problem remains open in higher dimensions.

Open access
preprint2011arXiv

The structure of rigid functions

A function $f:\RR \to \RR$ is called \emph{vertically rigid} if graph(cf)graph(cf) is isometric to graph(f)graph (f) for all c≠0c \neq 0. We prove Janković's conjecture by showing that a continuous function is vertically rigid if and only if it is of the form a+bxa+bx or a+bekxa+be^{kx} ($a,b,k \in \RR$). We answer a question of Cain, Clark and Rose by showing that there exists a Borel measurable vertically rigid function which is not of the above form. We discuss the Lebesgue and Baire measurable case, consider functions bounded on some interval and functions with at least one point of continuity. We also introduce horizontally rigid functions, and show that a certain structure theorem can be proved without assuming any regularity.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.