Search

Two subsets $A, B$ of the plane are betweenness isomorphic if there is a bijection $f\colon A\to B$ such that, for every $x,y,z\in A$, the point $f(z)$ lies on the line segment connecting $f(x)$ and $f(y)$ if and only if $z$ lies on the line segment connecting $x$ and $y$. In general, it is quite difficult to tell whether two given subsets of the plane are betweenness isomorphic. We concentrate on the case when the sets $A,B$ belong to the family $ \mathcal A_c$ of unions of pairs of concentric circles in the plane. We prove that $A, B \in \mathcal A_c$ are betweenness isomorphic if and only if they are similar. In particular, there are continuum many betweenness isomorphism classes in $ \mathcal A_c$, and each of these classes consists exactly of all scaled translations of an arbitrary representative of the class. Furthermore, we show that every betweenness isomorphism between sets $A,B\in \mathcal A_c$ is exactly the restriction of a scaled isometry of the plane., Comment: 22 pages with 4 figures

We define and study a natural category of graph limits. The objects are pairs $(\pi,\mu)$, where $\pi$ (the distribution of vertices) is an abstract probability measure on some abstract measurable space $(X,\mathcal{A})$ and $\mu$ (the distribution of edges) is an abstract finite measure on the square $(X,\mathcal{A})^2$. Morphisms are random maps between the underlying measurable spaces which preserve the distribution of vertices as well as the distribution of edges. We also define a convergence notion (inspired by s-convergence) for sequences of graph limits. We apply tools from category theory to prove the compactness of the space of all graph limits., Comment: 44 pages

The representation of politics in media influences societal perceptions and attitudes. Video games, as a pervasive form of media, contribute significantly to this phenomenon. In this work, we explore political themes within video games by analyzing politically-themed games on game distribution platforms including Steam. We conducted a statistical examination of games with political context to identify patterns and use this as a basis to introduce a first taxonomy to categorize and better understand the interplay between politics and video games. This taxonomy offers a first framework for analyzing political content in games and also sets a foundation for future research in this field., Comment: 4 pages

We give a necessary and sufficient condition for two circles, each with finitely many points added inside, to be betweenness isomorphic. We fully characterize the betweenness isomorphism classes in the family consisting of all circles with three collinear points inside., Comment: 20 pages

We study the complexities of isometry and isomorphism classes of separable Banach spaces in the Polish spaces of Banach spaces recently introduced and investigated by the authors in [14]. We obtain sharp results concerning the most classical separable Banach spaces. We prove that the infinite-dimensional separable Hilbert space is characterized as the unique separable infinite-dimensional Banach space whose isometry class is closed, and also as the unique separable infinite-dimensional Banach space whose isomorphism class is $F_\sigma$. For $p\in\left[1,2\right)\cup\left(2,\infty\right)$, we show that the isometry classes of $L_p[0,1]$ and $\ell_p$ are $G_\delta$-complete sets and $F_{\sigma\delta}$-complete sets, respectively. Then we show that the isometry class of $c_0$ is an $F_{\sigma\delta}$-complete set. Additionally, we compute the complexities of many other natural classes of separable Banach spaces; for instance, the class of separable $\mathcal{L}_{p,\lambda+}$-spaces, for $p,\lambda\geq 1$, is shown to be a $G_\delta$-set, the class of superreflexive spaces is shown to be an $F_{\sigma\delta}$-set, and the class of spaces with local $\Pi$-basis structure is shown to be a $\boldsymbol{\Sigma}^0_6$-set. The paper is concluded with many open problems and suggestions for a future research., Comment: This paper is a result of splitting the original arxiv submission arXiv:1912.03994 into two parts and some polishing - based on the comments of the referees. This is the second part. The original submission arXiv:1912.03994 will be replaced by the first part of the split

We show that s-convergence of graph sequences is equivalent to the convergence of certain compact sets, called shapes, of Borel probability measures. This result is analogous to the characterization of graphon convergence (with respect to the cut distance) by the convergence of envelopes, due to Dole\v{z}al, Greb\'{i}k, Hladk\'{y}, Rocha, and Rozho\v{v}.

We present and thoroughly study natural Polish spaces of separable Banach spaces. These spaces are defined as spaces of norms, resp. pseudonorms, on the countable infinite-dimensional rational vector space. We provide an exhaustive comparison of these spaces with admissible topologies recently introduced by Godefroy and Saint-Raymond and show that Borel complexities differ little with respect to these two different topological approaches. We investigate generic properties in these spaces and compare them with those in admissible topologies, confirming the suspicion of Godefroy and Saint-Raymond that they depend on the choice of the admissible topology., Comment: Based on the referees' comments, the original submission has been split into two parts. The new version is the first part of the split. The second one is arXiv:2204.06834 [math.FA]

Given a measurable set $A\subset \mathbb R^d$ we consider the "large-distance graph" $\mathcal{G}_A$, on the ground set $A$, in which each pair of points from $A$ whose distance is bigger than 2 forms an edge. We consider the problems of maximizing the $2d$-dimensional Lebesgue measure of the edge set as well as the $d$-dimensional Lebesgue measure of the vertex set of a large-distance graph in the $d$-dimensional Euclidean space that contains no copies of a complete graph on $k$ vertices. The former problem may be seen as a continuous analogue of Tur\'an's classical graph theorem, and the latter as a graph-theoretic analogue of the classical isodiametric problem. Our main result yields an analogue of Mantel's theorem for large-distance graphs. Our approach employs an isodiametric inequality in an annulus, which might be of independent interest., Comment: 15 pages, 3 figure; minor edits including more details in the proof of Theorem 1.8

The theory of graphons comes with the so-called cut norm and the derived cut distance. The cut norm is finer than the weak* topology (when considering the predual of $L^{1}$-functions). Dole\v{z}al and Hladk\'y [J. Combin. Theory Ser. B 137 (2019), 232-263] showed, that given a sequence of graphons, a cut distance accumulation graphon can be pinpointed in the set of weak* accumulation points as a minimizer of the entropy. Motivated by this, we study graphon parameters with the property that their minimizers or maximizers identify cut distance accumulation points over the set of weak* accumulation points. We call such parameters cut distance identifying. Of particular importance are cut distance identifying parameters coming from homomorphism densities, $t(H,\cdot)$. This concept is closely related to the emerging field of graph norms, and the notions of the step Sidorenko property and the step forcing property introduced by Kr\'a\v{l}, Martins, Pach and Wrochna [J. Combin. Theory Ser. A 162 (2019), 34-54]. We prove that a connected graph is weakly norming if and only if it is step Sidorenko, and that if a graph is norming then it is step forcing. Further, we study convexity properties of cut distance identifying graphon parameters, and find a way to identify cut distance limits using spectra of graphons. We also show that continuous cut distance identifying graphon parameters have the {\guillemotleft}pumping property{\guillemotright}, and thus can be used in the proof of the Frieze-Kannan regularity lemma., Comment: 49 pages, 5 figures. Referees' comments incorporated. The most substantial change is a simplification of the proof of Proposition 2.15 (which does not rely on untrue (as we discovered) Exercise 4.18 from Lovasz's book anymore)

The theory of graphons is ultimately connected with the so-called cut norm. In this paper, we approach the cut norm topology via the weak* topology (when considering a predual of $L^{1}$-functions). We prove that a sequence $W_1,W_2,W_3,\ldots$ of graphons converges in the cut distance if and only if we have equality of the sets of weak* accumulation points and of weak* limit points of all sequences of graphons $W_1',W_2',W_3',\ldots$ that are weakly isomorphic to $W_1,W_2,W_3,\ldots$. We further give a short descriptive set theoretic argument that each sequence of graphons contains a subsequence with the property above. This in particular provides an alternative proof of the theorem of Lov\'asz and Szegedy about compactness of the space of graphons. We connect these results to "multiway cut" characterization of cut distance convergence from [Ann. of Math. (2) 176 (2012), no. 1, 151-219]. These results are more naturally phrased in the Vietoris hyperspace $K$ over graphons with the weak* topology. We show that graphons with the cut distance topology are homeomorphic to a closed subset of $K$, and deduce several consequences of this fact. From these concepts a new order on the space of graphons emerges. This order allows to compare how structured two graphons are. We establish basic properties of this "structurdness order"., Comment: 37 pages, 2 figures; added Sections 4.1 and 4.3, various fixes and improvements due to Ondrej Kurka and an anonymous referee

Motivated by a well-known result in extremal set theory, due to Nicolaas Govert de Bruijn and Paul Erd\H{o}s, we consider curves in the unit $n$-cube $[0,1]^n$ of the form \[ A=\{(x,f_1(x),\ldots,f_{n-2}(x),\alpha): x\in [0,1]\}, \] where $\alpha$ is a fixed real number in $[0,1]$ and $f_1,\ldots,f_{n-2}$ are injective measurable functions from $[0,1]$ to $[0,1]$. We refer to such a curve $A$ as an $n$-\emph{de~Bruijn-Erd\H{o}s-set}. Under the additional assumption that all functions $f_i,i=1,\ldots,n-2,$ are piecewise monotone, we show that the Hausdorff dimension of $A$ is at most $1$ as well as that its $1$-dimensional Hausdorff measure is at most $n-1$. Moreover, via a walk along devil's staircases, we construct a piecewise monotone $n$-de~Bruijn-Erd\H{o}s-set whose $1$-dimensional Hausdorff measure equals $n-1$., Comment: 15 pages

We prove that the accumulation points of a sequence of graphs $G_1,G_2,G_3,\ldots$ with respect to the cut-distance are exactly the weak$^*$ limit points of subsequences of the adjacency matrices (when all possible orders of the vertices are considered) that minimize the entropy over all weak$^*$ limit points of the corresponding subsequence. In fact, the entropy can be replaced by any map $W\mapsto \int\int f(W(x,y))$, where $f$ is a continuous and strictly concave function. Our proofs are elementary, and do not use the regularity lemma., Comment: 23 pages, 2 figures. Referees' comments incorporated

We present a simple generalization of $W$-spaces introduced by G. Gruenhage. We show that this generalization leads to a strictly larger class of topological spaces which we call $\widetilde W$-spaces, and we provide several applications. Namely, we use the notion of $\widetilde W$-spaces to provide sufficient conditions for the product of two spaces to be a Baire space, for a semitopological group to be a topological group, or for a separately continuous function to be continuous at the points of a certain large set.

Hladky, Hu, and Piguet [Tilings in graphons, preprint] introduced the notions of matching and fractional vertex covers in graphons. These are counterparts to the corresponding notions in finite graphs. Combinatorial optimization studies the structure of the matching polytope and the fractional vertex cover polytope of a graph. Here, in analogy, we initiate the study of the structure of the set of all matchings and of all fractional vertex covers in a graphon. We call these sets the matching polyton and the fractional vertex cover polyton. We also study properties of matching polytons and fractional vertex cover polytons along convergent sequences of graphons. As an auxiliary tool of independent interest, we prove that a graphon is $r$-partite if and only if it contains no graph of chromatic number $r+1$. This in turn gives a characterization of bipartite graphons as those having a symmetric spectrum., Comment: 32 pages, 2 figures; more background on graphons and analysis, a new section on spectra of bipartite graphons, numerous corrections based on suggestion by an anonymous referee

Let $G$ be an abelian Polish group. We show that there is a strongly Haar meager set in $G$ without any $F_{\sigma}$ Haar meager hull (and that this still remains true if we replace $F_{\sigma}$ by any other class of the Borel hierarchy). We also prove that there is a coanalytic naively strongly Haar meager set without any Haar meager hull. Further, we investigate the relationship of the collection of all compact sets to the collection of all Haar meager sets in non-locally compact Polish groups., Comment: 18 pages

We prove a result on perfect cliques with respect to countably many G-delta relations on a complete metric space. As an application, we show that a Polish group contains a free subgroup generated by a perfect set as long as it contains any uncountable free subgroup. This answers a recent question of G{\l}\c{a}b and Strobin., Comment: 10 pages

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant G(n,W) of the Erdos-Renyi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of G(n,W) for each fixed n, and give examples of graphons for which G(n,W) exhibits wild long-term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably-partite., Comment: 30 pages, 2 figure; accepted to publication in Random Structures and Algorithms

In the present article we investigate Darji's notion of Haar meager sets from several directions. We consider alternative definitions and show that some of them are equivalent to the original one, while others fail to produce interesting notions. We define Haar meager sets in nonabelian Polish groups and show that many results, including the facts that Haar meager sets are meager and form a $\sigma$-ideal, are valid in the more general setting as well. The article provides various examples distinguishing Haar meager sets from Haar null sets, including decomposition theorems for some subclasses of Polish groups. As a corollary we obtain, for example, that $\mathbb Z^\omega$, $\mathbb R^\omega$ or any Banach space can be decomposed into a Haar meager set and a Haar null set. We also establish the stability of non-Haar meagerness under Cartesian product., Comment: 19 pages

We study the complexity of the space $C^*_p(X)$ of bounded continuous functions with the topology of pointwise convergence. We are allowed to use descriptive set theoretical methods, since for a separable metrizable space $X$, the measurable space of Borel sets in $C^*_p(X)$ (and also in the space $C_p(X)$ of all continuous functions) is known to be isomorphic to a subspace of a standard Borel space. It was proved by A. Andretta and A. Marcone that if $X$ is a $\sigma$-compact metrizable space, then the measurable spaces $C_p(X)$ and $C^*_p(X)$ are standard Borel and if $X$ is a metrizable analytic space which is not $\sigma$-compact then the spaces of continuous functions are Borel-$\Pi^1_1$-complete. They also determined under the assumption of projective determinacy (PD) the complexity of $C_p(X)$ for any projective space $X$ and asked whether a similar result holds for $C^*_p(X)$. We provide a positive answer, i.e. assuming PD we prove, that if $n \geq 2$ and if $X$ is a separable metrizable space which is in $\Sigma^1_n$ but not in $\Sigma^1_{n-1}$ then the measurable space $C^*_p(X)$ is Borel-$\Pi^1_n$-complete. This completes under the assumption of PD the classification of Borel-Wadge complexity of $C^*_p(X)$ for $X$ projective.