Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized metric spaces. Relations with graphs, ordered sets and automata : A survey
84
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this survey we present a generalization of the notion of metric space and some applications to discrete structures as graphs, ordered sets and transition systems. Results in that direction started in the middle eighties based on the impulse given by Quilliot (1983). Graphs and ordered sets were considered as kind of metric spaces, where - instead of real numbers - the values of the distance functions $d$ belong to an ordered semigroup equipped with an involution. In this frame, maps preserving graphs or posets are exactly the nonexpansive mappings (that is the maps $f$ such that $d(f(x),f(y))leq d(x,y)$, for all $x,y$). It was observed that many known results on retractions and fixed point property for classical metric spaces (whose morphisms are the nonexpansive mappings) are also valid for these spaces. For example, the characterization of absolute retracts, by Aronszajn and Panitchpakdi (1956), the construction of the injective envelope by Isbell (1965) and the fixed point theorem of Sine and Soardi (1979) translate into the Banaschewski-Bruns theorem (1967), the MacNeille completion of a poset (1933) and the famous Tarski fixed point theorem (1955). This prompted an analysis of several classes of discrete structures from a metric point of view. In this paper, we report the results obtained over the years with a particular emphasis on the fixed point property.
rate research
Read More
We extend to binary relational systems the notion of compact and normal structure, introduced by J.P.Penot for metric spaces, and we prove that for the involutive and reflexive ones, every commuting family of relational homomorphisms has a common fixed point. The proof is based upon the clever argument that J.B.Baillon discovered in order to show that a similar conclusion holds for bounded hyperconvex metric spaces and then refined by the first author to metric spaces with a compact and normal structure. Since the non-expansive mappings are relational homomorphisms, our result includes those of T.C.Lim, J.B.Baillon and the first author. We show that it extends the Tarskis fixed point theorem to graphs which are retracts of reflexive oriented zigzags of bounded length. Doing so, we illustrate the fact that the consideration of binary relational systems or of generalized metric spaces are equivalent.
A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvatal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $Omega(sqrt{n})$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $Omega(n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $Omega(n^{4/7})$ lines, improving the previous $Omega(n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n / 5w$, where $w$ is the number of different distances in the space, and we give an $Omega(n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from {1, 2, 3}.
This article provides a link diagram to visualize relations between two ordered sets representing precedences on decision-making options or solutions to strategic form games. The diagram consists of floating loops whose any two loops cross just twice each other. As problems formulated by relations between two ordered sets, I give two examples: visualizing rankings from pairwise comparisons on the diagram and finding Pareto optimal solutions to a game of prisoners dilemma. At visualizing rankings, we can see whether a ranking satisfies Condorcets principle or not by checking whether the top loop is splittable or not. And at finding solutions to the game, when a solution of the game of prisoners dilemma is Pareto optimal, the loop corresponding to the solution has no splittable loop above it. Throughout the article, I point out that checking the splittability of loops is an essence. I also mention that the diagram can visualize natural transformations between two functors on free construction categories.
This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahns information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but it may be irregular in the other, the extended entropy-based proof technique yields the same bound that was conjectured by Kahn (2001) and proved by Sah et al. (2019).
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $n times n$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA 21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollobas, and Morris [Eur. J. Comb. 06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
