Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial characterization of pseudometrics
84
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $X$, $Y$ be sets and let $Phi$, $Psi$ be mappings with the domains $X^{2}$ and $Y^{2}$ respectively. We say that $Phi$ is combinatorially similar to $Psi$ if there are bijections $f colon Phi(X^2) to Psi(Y^{2})$ and $g colon Y to X$ such that $Psi(x, y) = f(Phi(g(x), g(y)))$ for all $x$, $y in Y$. It is shown that the semigroups of binary relations generated by sets ${Phi^{-1}(a) colon a in Phi(X^{2})}$ and ${Psi^{-1}(b) colon b in Psi(Y^{2})}$ are isomorphic for combinatorially similar $Phi$ and $Psi$. The necessary and sufficient conditions under which a given mapping is combinatorially similar to a pseudometric, or strongly rigid pseudometric, or discrete pseudometric are found. The algebraic structure of semigroups generated by ${d^{-1}(r) colon r in d(X^{2})}$ is completely described for nondiscrete, strongly rigid pseudometrics and, also, for discrete pseudometrics $d colon X^{2} to mathbb{R}$.
rate research
Read More
Let $X$, $Y$ be sets and let $Phi$, $Psi$ be mappings with domains $X^{2}$ and $Y^{2}$ respectively. We say that $Phi$ and $Psi$ are combinatorially similar if there are bijections $f colon Phi(X^2) to Psi(Y^{2})$ and $g colon Y to X$ such that $Psi(x, y) = f(Phi(g(x), g(y)))$ for all $x$, $y in Y$. Conditions under which a given mapping is combinatorially similar to an ultrametric or a pseudoultrametric are found. Combinatorial characterizations are also obtained for poset-valued ultrametric distances recently defined by Priess-Crampe and Ribenboim.
For $3$-dimensional convex polytopes, inscribability is a classical property that is relatively well-understood due to its relation with Delaunay subdivisions of the plane and hyperbolic geometry. In particular, inscribability can be tested in polynomial time, and for every $f$-vector of $3$-polytopes, there exists an inscribable polytope with that $f$-vector. For higher-dimensional polytopes, much less is known. Of course, for any inscribable polytope, all of its lower-dimensional faces need to be inscribable, but this condition does not appear to be very strong. We observe non-trivial new obstructions to the inscribability of polytopes that arise when imposing that a certain inscribable face be inscribed. Using this obstruction, we show that the duals of the $4$-dimensional cyclic polytopes with at least $8$ vertices---all of whose faces are inscribable---are not inscribable. This result is optimal in the following sense: We prove that the duals of the cyclic $4$-polytopes with up to $7$ vertices are, in fact, inscribable. Moreover, we interpret this obstruction combinatorially as a forbidden subposet of the face lattice of a polytope, show that $d$-dimensional cyclic polytopes with at least $d+4$ vertices are not circumscribable, and that no dual of a neighborly $4$-polytope with $8$ vertices, that is, no polytope with $f$-vector $(20,40,28,8)$, is inscribable.
For the model of probabilistic labelled transition systems that allow for the co-existence of nondeterminism and probabilities, we present two notions of bisimulation metrics: one is state-based and the other is distribution-based. We provide a sound and complete modal characterisation for each of them, using real-valued modal logics based on the Hennessy-Milner logic. The logic for characterising the state-based metric is much simpler than an earlier logic by Desharnais et al. as it uses only two non-expansive operators rather than the general class of non-expansive operators.
Let $T$ be a random ergodic pseudometric over $mathbb R^d$. This setting generalizes the classical emph{first passage percolation} (FPP) over $mathbb Z^d$. We provide simple conditions on $T$, the decay of instant one-arms and exponential quasi-independence, that ensure the positivity of its time constants, that is almost surely, the pseudo-distance given by $T$ from the origin is asymptotically a norm. Combining this general result with previously known ones, we prove that The known phase transition for Gaussian percolation in the case of fields with positive correlations with exponentially fast decayholds for Gaussian FPP, including the natural Bargmann-Fock model; The known phase transition for Voronoi percolation also extends to the associated FPP; The same happens for Boolean percolation for radii with exponential tails, a result which was known without this condition. We prove the positivity of the constant for random continuous Riemannian metrics, including cases with infinite correlations in dimension $d=2$. Finally, we show that the critical exponent for the one-arm, if exists, is bounded above by $d-1$. This holds forbond Bernoulli percolation, planar Gaussian fields, planar Voronoi percolation, and Boolean percolation with exponential small tails.
We consider tropical hemispaces, defined as tropically convex sets whose complements are also tropically convex, and tropical semispaces, defined as maximal tropically convex sets not containing a given point. We introduce the concept of $(P,R)$-decomposition. This yields (to our knowledge) a new kind of representation of tropically convex sets extending the classical idea of representing convex sets by means of extreme points and rays. We characterize tropical hemispaces as tropically convex sets that admit a (P,R)-decomposition of certain kind. In this characterization, with each tropical hemispace we associate a matrix with coefficients in the completed tropical semifield, satisfying an extended rank-one condition. Our proof techniques are based on homogenization (lifting a convex set to a cone), and the relation between tropical hemispaces and semispaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
