Search

To cope with the increased complexity of systems, models are used to capture what is considered the essence of a system. Such models are typically represented as a graph, which is queried to gain insight into the modelled system. Often, the results of these queries need to be adjusted according to updated requirements and are therefore a subject of maintenance activities. It is thus necessary to support writing model queries with adequate languages. However, in order to stay meaningful, the analysis results need to be refreshed as soon as the underlying models change. Therefore, a good execution speed is mandatory in order to cope with frequent model changes. In this paper, we propose a benchmark to assess model query technologies in the presence of model change sequences in the domain of social media. We present solutions to this benchmark in a variety of 11 different tools and compare them with respect to explicitness of incrementalization, asymptotic complexity and performance.

We consider a real-valued function f defined on the set of infinite branches X of a countably branching pruned tree T. The function f is said to be a limsup function if there is a function $u \colon T \to \mathbb {R}$ such that $f(x) = \limsup _{t \to \infty } u(x_{0},\dots ,x_{t})$ for each $x \in X$ . We study a game characterization of limsup functions, as well as a novel game characterization of functions of Baire class 1.

Modelling languages play a central role in developing complex, critical systems. Having a precise, comprehensible, and high-quality modelling language specification is essential to all the different stakeholders using, implementing, or extending the language. Many good practices can be found that improve the understandability or consistency of the languages' semantics. However, designing a modelling language intended for a large audience is still challenging. In this paper, we investigate how to assess the specification of modelling language semantics: (i) how it helps professionals to understand the language (ii) whether it contains errors, contradictions, ambiguities, and (iii) how suitable it is to assess the correctness of the related modelling tools. We identified the various stakeholders' viewpoints on the language and argued why understanding the semantics is crucial for all of them, although on different levels that can be supported by different artefacts. Next, we assessed a state-of-the-art specification for a general-purpose modelling language, the Precise Semantics of UML State Machines (PSSM). We reviewed the text of the specification, analysed and executed PSSM's conformance test suite, and categorized our experiences according to questions that are generally relevant for modelling languages. Finally, we made recommendations for improving the development of future modelling languages by representing the semantic domain and traces more explicitly, applying diverse test design techniques to obtain conformance test suites, and using various tools to support early-phase language design.

A subsetXof a Polish groupGisHaar nullif there exists a Borel probability measure μ and a Borel setBcontainingXsuch that μ(gBh) = 0 for everyg,h∈G. A setXisHaar meagerif there exists a compact metric spaceK, a continuous functionf:K→Gand a Borel setBcontainingXsuch thatf−1(gBh) is meager inKfor everyg,h∈G. We calculate (inZFC) the four cardinal invariants (add, cov, non, cof) of these two σ-ideals for the simplest non-locally compact Polish group, namely in the case$G = \mathbb {Z}^\omega$. In fact, most results work for separable Banach spaces as well, and many results work for Polish groups admitting a two-sided invariant metric. This answers a question of the first named author and Vidnyánszky.

We survey results about Haar null subsets of (not necessarily locally compact) Polish groups. The aim of this paper is to collect the fundamental properties of the various possible definitions of Haar null sets, and also to review the techniques that may enable the reader to prove results in this area. We also present several recently introduced ideas, including the notion of Haar meager sets, which are closely analogous to Haar null sets. We prove some results in a more general setting than that of the papers where they were originally proved and prove some results for Haar meager sets which were already known for Haar null sets.

In order to understand the structure of the "typical" element of a homeomorphism group, one has to study how large the conjugacy classes of the group are. When typical means generic in the sense of Baire category, this is well understood, see e.g. the works of Glasner and Weiss, and Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behaviour of the homeomorphisms is entirely different from the generic case. For $\text{Homeo}^+([0,1])$ we describe the non-Haar null conjugacy classes and also show that their union is co-Haar null, for $\text{Homeo}^+(\mathbb{S}^1)$ we describe the non-Haar null conjugacy classes, and for $\mathcal{U}(\ell^2)$ we show that, apart from the classes of the multishifts, all conjugacy classes are Haar null. As an application we affirmatively answer the question whether these groups can be written as the union of a meagre and a Haar null set.

Following Darji, we say that a Borel subset B of an abelian Polish group G is Haar meager if there is a compact metric space K and a continuous function f: K → G such that the preimage of the translate f−1(B + g) is meager in K for every g ∈ G. The set B is called strongly Haar meager if there is a compact set C ⊆ G such that (B + g) ⋂ C is meager in C for every g ∈ G. The main open problem in this area is Darji’s question asking whether these two notions are the same. Even though there have been several partial results suggesting a positive answer, in this paper we construct a counterexample. More specifically, we construct a Gδ set in ℤω that is Haar meager but not strongly Haar meager. We also show that no Fσ counterexample exists, hence our result is optimal. © 2019, The Hebrew University of Jerusalem.

In order to understand the structure of the `typical' element of an automorphism group, one has to study how large the conjugacy classes of the group are. When typical is meant in the sense of Baire category, a complete description of the size of the conjugacy classes has been given by Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behavior of the automorphisms is entirely different from the Baire category case. In this paper, we generalize the theorems of Dougherty and Mycielski about $S_\infty$ to arbitrary automorphism groups of countable structures isolating a new model theoretic property, the Cofinal Strong Amalgamation Property. As an application we show that a large class of automorphism groups can be decomposed into the union of a meager and a Haar null set.

J. Zapletal asked if all the forcing notions considered in his monograph are homogeneous. Specifically, he asked if the forcing consisting of Borel sets of $\sigma$-finite 2-dimensional Hausdorff measure in $\mathbb{R}^3$ (ordered under inclusion) is homogeneous. We give a partial negative answer to both questions by showing that this $\sigma$-ideal is not homogeneous. Let $\mathcal{N}^1_2$ be the $\sigma$-ideal of sets in the plane of 1-dimensional Hausdorff measure zero. D. H. Fremlin determined the position of the cardinal invariants of this $\sigma$-ideal in the Cicho\'n Diagram. This required proving numerous inequalities, and in all but three cases it was known that the inequalities can be strict in certain models. For one of the remaining ones Fremlin posed this as an open question in his monograph. We answer this by showing that consistently $\mathrm{cov}(\mathcal{N}^1_2) > \mathrm{cov}(\mathcal{N})$, where $\mathcal{N}$ is the usual Lebesgue null ideal. We also prove that the remaining two inequalities can be strict. Moreover, we fit the cardinal invariants of the $\sigma$-ideal of sets of $\sigma$-finite Hausdorff measure into the diagram. P. Humke and M. Laczkovich raised the following question. Is it consistent that there is an ordering of the reals in which all proper initial segments are Lebesgue null but for every ordering of the reals there is a proper initial segment that is not null with respect to the $1/2$-dimensional Hausdorff measure? We determine the values of the cardinal invariants of the Cicho\'n Diagram as well as the invariants of the nullsets of Hausdorff measures in the first model mentioned in the previous paragraph, and as an application we answer this question of Humke and Laczkovich affirmatively.

The lower dimension $\dim_L$ is the dual concept of the Assouad dimension. As it fails to be monotonic, Fraser and Yu introduced the modified lower dimension $\dim_{ML}$ by making the lower dimension monotonic with the simple formula $\dim_{ML} X=\sup\{\dim_L E: E\subset X\}$. As our first result we prove that the modified lower dimension is finitely stable in any metric space, answering a question of Fraser and Yu. We prove a new, simple characterization for the modified lower dimension. For a metric space $X$ let $\mathcal{K}(X)$ denote the metric space of the non-empty compact subsets of $X$ endowed with the Hausdorff metric. As an application of our characterization, we show that the map $\dim_{ML} \colon \mathcal{K}(X)\to [0,\infty]$ is Borel measurable. More precisely, it is of Baire class $2$, but in general not of Baire class $1$. This answers another question of Fraser and Yu. Finally, we prove that the modified lower dimension is not Borel measurable defined on the closed sets of $\ell^1$ endowed with the Effros Borel structure., 10 pages. A new paragraph added to the introduction

The GraphBLAS standard defines a set of fundamental building blocks for formulating graph algorithms in the language of linear algebra. Since its first release in 2017, the expressivity of the GraphBLAS API and the performance of its implementations (such as SuiteSparse: GraphBLAS) have been studied on a number of textbook graph algorithms such as BFS, single-source shortest path, and connected components. However, less attention was devoted to other aspects of graph processing such as handling typed and attributed graphs (also known as property graphs), and making use of complex graph query techniques (handling paths, aggregation, and filtering). To study these problems in more detail, we have used GraphBLAS to solve the case study of the 2014 SIGMOD Programming Contest, which defines complex graph processing tasks that require a diverse set of operations. Our solution makes heavy use of multi-source BFS algorithms expressed as sparse matrix-matrix multiplications along with other GraphBLAS techniques such as masking and submatrix extraction. While the queries can be formulated in GraphBLAS concisely, our performance evaluation shows mixed results. For some queries and data sets, the performance is competitive with the hand-optimized top solutions submitted to the contest, however, in some cases, it is currently outperformed by orders of magnitude.

Graphs are increasingly important for modelling and analysing connected data sets. Traditionally, graph analytical tools targeted global fixed-point computations, while graph databases focused on simpler transactional read operations such as retrieving the neighbours of a node. However, recent applications of graph processing (such as financial fraud detection and serving personalized recommendations) often necessitate a mix of the two workload profiles. A potential approach to tackle these complex workloads is to formulate graph algorithms in the language of linear algebra. To this end, the recent GraphBLAS standard defines a linear algebraic graph computational model and an API for implementing such algorithms. To investigate its usability and efficiency, we have implemented a GraphBLAS solution for the “Social Media” case study of the 2018 Transformation Tool Contest. This paper presents our solution along with an incrementalized variant to improve its runtime for repeated evaluations. Preliminary results show that the GraphBLAS-based solution is competitive but implementing it requires significant development efforts.

Let ( G , ⋅ ) be a Polish group. We say that a set X ⊂ G is Haar null if there exists a universally measurable set U ⊃ X and a Borel probability measure μ such that for every g , h ∈ G we have μ ( g U h ) = 0 . We call a set X naively Haar null if there exists a Borel probability measure μ such that for every g , h ∈ G we have μ ( g X h ) = 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.

A setisshyorHaar null(in the sense of Christensen) if there exists a Borel setand a Borel probability measureμonC[0, 1] such thatandfor allf∈C[0, 1]. The complement of a shy set is called aprevalentset. We say that a set isHaar ambivalentif 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 manyf∈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] from the topological point of view. We prove that the functionsf∈C[0, 1] for which the same characterization holds form a Haar ambivalent set.In an earlier paper, Balkaet al. proved that the functionsf∈C[0, 1] for which positively many level sets with respect to the Lebesgue measure λ are singletons form a non-shy set inC[0, 1]. The above result yields that this set is actually Haar ambivalent. Now we prove that the functionsf∈C[0, 1] for which positively many level sets with respect to the occupation measure λ ◦f–1are not perfect form a Haar ambivalent set inC[0, 1].We show that for the prevalentf∈C[0, 1] for the genericy∈f([0, 1]) the level setf–1(y) is perfect. Finally, we answer a question of Darji and White by showing that the set of functionsf∈C[0, 1] for which there exists a perfect setPf⊂ [0, 1] such thatfʹ(x) = ∞ for allx∈Pfis Haar ambivalent.

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 K be an uncountable compact metric space. We prove that a prevalent f ∈ C ( K , R d ) has many fibers with almost maximal Hausdorff dimension. This generalizes a theorem of Dougherty and yields that a prevalent f ∈ C ( K , 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 a prevalent f ∈ C ( [ 0 , 1 ] m , R d ) the set of y ∈ f ( [ 0 , 1 ] m ) for which dim H ⁡ f − 1 ( y ) = m contains a dense open set having full measure with respect to the occupation measure λ m ∘ f − 1 , where dim H and λ m denote the Hausdorff dimension and the m-dimensional Lebesgue measure, respectively. We also prove an analogous result when [ 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 ] for which positively many level sets are singletons form a non-shy set in C [ 0 , 1 ] . In order to do so, we generalize a theorem of Antunovic, Burdzy, Peres and Ruscher. As a complementary result we prove that the functions f ∈ C [ 0 , 1 ] for which dim H ⁡ f − 1 ( y ) = 1 for all y ∈ ( min ⁡ f , max ⁡ f ) form a non-shy set in 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.

We give a complete description of the size of the conjugacy classes of the automorphism group of the random graph with respect to Christensen's Haar null ideal. It is shown that every non-Haar null class contains a translated copy of a nonempty portion of every compact set and that there are continuum many non-Haar null conjugacy classes. Our methods also yield a new proof of an old result of Truss., Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles

In order to understand the structure of the "typical" element of an automorphism group, one has to study how large the conjugacy classes of the group are. For the case when typical is meant in the sense of Baire category, Truss proved that there is a co-meagre conjugacy class in Aut(Q, Comment: Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles, including arXiv:1808.06121

Let G be an abelian Polish group, e.g., a separable Banach space. A subset X ⊂ G is called Haar null (in the sense of Christensen) if there exists a Borel set B ⊃ X and a Borel probability measure µ on G such that µ(B + g) = 0 for every g ∈ G. The term shy is also commonly used for Haar null, and co-Haar null sets are often called prevalent.

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.

More than 80 years ago Kolmogorov asked the following question. Let E ⊆ R 2 E\subseteq \mathbb {R}^{2} be a measurable set with λ 2 ( E ) > ∞ \lambda ^{2}(E)>\infty , where λ 2 \lambda ^2 denotes the two-dimensional Lebesgue measure. Does there exist for every ε > 0 \varepsilon >0 a contraction f : E → R 2 f\colon E\to \mathbb {R}^{2} such that λ 2 ( f ( E ) ) ≥ λ 2 ( E ) − ε \lambda ^{2}(f(E))\geq \lambda ^{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 an analogous result in higher dimensions.

Let us say that an element of a given family \(\mathcal{A}\) of subsets of ℝd can be reconstructed using n test sets if there exist T1,…,Tn⊂ℝd such that whenever \(A,B\in\mathcal{A}\) and the Lebesgue measures of A∩Ti and B∩Ti agree for each i=1,…,n then A=B. Our goal will be to find the least such n.

In an earlier paper (arxiv:1108.4292) we introduced a new concept of dimension for metric spaces, the so called topological Hausdorff dimension. For a compact metric space $K$ let $\dim_{H}K$ and $\dim_{tH} K$ denote its Hausdorff and topological Hausdorff dimension, respectively. We proved that this new dimension describes the Hausdorff dimension of the level sets of the generic continuous function on $K$, namely $\sup{\dim_{H}f^{-1}(y) : y \in \mathbb{R}} = \dim_{tH} K - 1$ for the generic $f \in C(K)$, provided that $K$ is not totally disconnected, otherwise every non-empty level set is a singleton. We also proved that if $K$ is not totally disconnected and sufficiently homogeneous then $\dim_{H}f^{-1}(y) = \dim_{tH} K - 1$ for the generic $f \in C(K)$ and the generic $y \in f(K)$. The most important goal of this paper is to make these theorems more precise. As for the first result, we prove that the supremum is actually attained on the left hand side of the first equation above, and also show that there may only be a unique level set of maximal Hausdorff dimension. As for the second result, we characterize those compact metric spaces for which for the generic $f\in C(K)$ and the generic $y\in f(K)$ we have $\dim_{H} f^{-1}(y)=\dim_{tH}K-1$. We also generalize a result of B. Kirchheim by showing that if $K$ is self-similar then for the generic $f\in C(K)$ for every $y\in \inter f(K)$ we have $\dim_{H} f^{-1}(y)=\dim_{tH}K-1$. Finally, we prove that the graph of the generic $f\in C(K)$ has the same Hausdorff and topological Hausdorff dimension as $K$., 20 pages

In 1990 Kechris and Louveau developed the theory of three very natural ranks on the Baire class 1 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. Finally, we prove a general result showing that all ranks satisfying some natural properties coincide for bounded functions. © 2016 American Mathematical Society.

An r -edge coloring of a graph or hypergraph G = ( V , E ) is a map c : E → { 0 , … , r − 1 } . Extending results of Rado and answering questions of Rado, Gyarfas and Sarkozy we prove that • the vertex set of every r -edge colored countably infinite complete k -uniform hypergraph can be partitioned into r monochromatic tight paths with distinct colors (a tight path in a k -uniform hypergraph is a sequence of distinct vertices such that every set of k consecutive vertices forms an edge); • for all natural numbers r and k there is a natural number M such that the vertex set of every r -edge colored countably infinite complete graph can be partitioned into M monochromatic k th powers of paths apart from a finite set (a k th power of a path is a sequence v 0 , v 1 , … of distinct vertices such that 1 ⩽ | i − j | ⩽ k implies that v i v j is an edge); • the vertex set of every 2 -edge colored countably infinite complete graph can be partitioned into 4 monochromatic squares of paths, but not necessarily into 3 ; • the vertex set of every 2 -edge colored complete graph on ω 1 can be partitioned into 2 monochromatic paths with distinct colors.

S. Saks and recently R.D. Mauldin asked if every translation invariant σ-finite Borel measure on R d is a constant multiple of Lebesgue measure. The aim of this paper is to investigate the versions of this question, since surprisingly the answer is “yes and no,” depending on what we mean by Borel measure and by constant. According to a folklore result, if the measure is only defined for Borel sets, then the answer is affirmative. We show that if the measure is defined on a σ-algebra 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 R d can be non-σ-finite when we restrict it to the Borel sets.

We show that the set of Liouville numbers is either null or non- σ -finite with respect to every translation invariant Borel measure on R , in particular, with respect to every Hausdorff measure H g with gauge function g . This answers a question of R.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 R that are not 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.

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 $(C_0+x)\cap P$ is uncountable. Using this $C_0$ we answer a question of Gruenhage by showing that it is consistent with $ZFC$ (as it follows e.g. from $\textrm{cof}(\iN)

We show that the existence of measurable envelopes of all subsets of R n with respect to the d-dimensional Hausdor measure (0 < d < n) is independent of ZFC. We also investigate the consistency of the existence ofH d -measurable Sierpi«ski sets. Introduction. The following denition was motivated by the theory of analytic sets. Definition 0.1. LetA be a -algebra of subsets of a set X. We call a set H X small (with respect toA) if every subset of H belongs toA. The -ideal of small subsets is denoted byA0. We say thatA2A is a measurable envelope of H X (with respect toA) if H A and for every B2A such that H B A we have AnB2A0.

In the 1970s M. Laczkovich posed the following problem: Let $\mathcal{B}_1(X)$ denote the set of Baire class $1$ functions defined on an uncountable Polish space $X$ equipped with the pointwise ordering. \[\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 $1$ functions iff it is isomorphic to a subset of the following linear order that we call $([0,1]^{x'_{\delta}). \] Using this characterization we easily reprove all the known results and answer all the known open questions of the topic.

We show that the Continuum Hypothesis implies that for every $ 0 < d_1 \leq d_2 < n $ the measure spaces $(\mathbb{R}^n,\mathcal{M}_{\mathcal{H}^{d_1}},\mathcal {H}^{d_1})$ and $(\mathbb{R}^n,\mathcal{M}_{\mathcal{H}^{d_2}},\mathcal{H}^{d_2})$ are isomorphic, where $\mathcal{H}^d$ is $d$-dimensional Hausdorff measure and $\mathcal{M}_{d}$ is the $\sigma$-algebra of measurable sets with respect to $\mathcal{H}^d$. 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 Holder continuous (or is of bounded variation) on a set of positive Hausdorff dimension.

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\'ath and Kunen we show (in $ZFC$) that special Aronszajn lines are embeddable into $\iB_1(\RR)$. We also show that under Martin's Axiom a linearly ordered set $\mathbb{L}$ with $|\mathbb{L}

We consider the set of Baire 1 functions endowed with the pointwise partial ordering and investigate the structure of the linearly ordered subsets.

A function $f : \mathbb{R}^n \to \mathbb{R}$ is called vertically rigid if $graph(cf)$ is isometric to $graph (f)$ for all $c \neq 0$. In [1] settled Janković's conjecture by showing that a continuous function $f : \mathbb{R}\to \mathbb{R}$ is vertically rigid if and only if it is of the form $a+bx$ or $a+be^{kx}$ ($a,b,k \in )$ prove that a continuous function $f :\mathbb{R}^2 \to \mathbb{R}$ is vertically rigid if and only if, after a suitable rotation around the $z$-axis, $f(x,y)$ is of the form $a + bx + dy$, $a + s(y)e^{kx}$ or $a + be^{kx} + dy$ ($a,b,d,k \in \mathbb{R}$, $k \neq 0$, $s : \mathbb{R} \to \mathbb{R}$ continuous). The problem remains open in higher dimensions.

A \emph{hull} of $A \subset [0,1]$ is a set $H$ containing $A$ such that $\lambda^*(H)=\lambda^*(A)$. We investigate all four versions of the following problem. Does there exist a monotone (wrt. inclusion) map that assigns a Borel/$G_\delta$ hull to every negligible/measurable subset of $[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_\delta$ 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\'alv\"olgyi 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]$.

We show that if the gradient of f : R 2 → R exists everywhere and is nowhere zero, then in a neighbourhood of each of its points the level set {x∈ R 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.

Let $\R^\R$ denote the set of real valued functions defined on the real line. A map $D: \R^\R \to \R^\R$ is a {\it difference operator}, if there are real numbers $a_i, b_i \ (i=1,..., n)$ such that $(Df)(x)=\sum_{i=1}^n a_i f(x+b_i)$ for every $f\in \R^\R $ and $x\in \R$. A {\it system of difference equations} is a set of equations $S={D_i f=g_i : i\in I}$, where $I$ is an arbitrary set of indices, $D_i$ is a difference operator and $g_i$ is a given function for every $i\in I$, and $f$ is the unknown function. One can prove that a system $S$ is solvable if and only if every finite subsystem of $S$ 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 $S$ such that every finite subsystem of $S$ has a solution which is a trigonometric polynomial, but $S$ has no such solution. This phenomenon motivates the following definition. Let ${\cal F}$ be a class of functions. The {\it solvability cardinal} $\solc (\iF)$ of ${\cal F}$ is the smallest cardinal $\kappa$ such that whenever $S$ is a system of difference equations and each subsystem of $S$ of cardinality less than $\kappa$ has a solution in ${\cal F}$, then $S$ itselfhas a solution in ${\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})=\omega_1$, $\solc ({f: f\ \text{is continuous}}) = \omega_1$ but $\solc ({f: f\ \text{is Darboux}}) =(2^\omega)^+$, and $\solc (\R^\R)=\omega$. 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 $\alpha$ functions.

Cain, Clark and Rose defined a function \({{f\colon\mathbb{R}^n \to \mathbb{R}}}\) to be vertically rigid if graph(cf) is isometric to graph(f) for every c ≠ 0. It is horizontally rigid if graph\({(f(c \vec{x}))}\) is isometric to graph(f) for every c ≠ 0 (see Cain et al., Real Anal. Exch. 31:515–518, 2005/2006). In Balka and Elekes (J. Math. Anal. Appl. 345:880–888, 2008) the authors of the present paper settled Jankovic’s conjecture by showing that a continuous function of one variable is vertically rigid if and only if it is of the form a + bx or \({{a+be^{kx} (a,b,k \in \mathbb{R})}}\). Later they proved in Balka and Elekes (Real. Anal. Exch. 35:139–156, 2009) 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 + dy, a +s(y)e^{kx}}\) or \({{a + be^{kx} + dy (a,b,d,k \in \mathbb{R}, k \neq 0, s\colon \mathbb{R}\to \mathbb{R}\,{\rm is\, continuous})}}\). The problem remained open in higher dimensions. The characterization in the case of horizontal rigidity is surprisingly simpler. Richter (Real Anal. Exch. 35:343–354, 2009) proved that a continuous function of one variable is horizontally rigid if and only if it is of the form \({{a+bx (a,b\in \mathbb{R})}}\). 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 + dy (a,b,d \in \mathbb{R})}}\). This problem also remains open in higher dimensions. The main new ingredient of the present paper is the use of functional equations.