The main result of this article is that any braided (resp. annular, planar) diagram group $D$ splits as a short exact sequence $1 \to R \to D \to S \to 1$ where $R$ is a subgroup of some right-angled ...Artin group and $S$ a subgroup of Thompson's group $V$ (resp. $T$, $F$). As an application, we show that several braided diagram groups embed into Thompson's group $V$, including Higman's groups $V_{n,r}$, groups of quasi-automorphisms $QV_{n,r,p}$, and generalised Houghton's groups $H_{n,p}$.
Condorcet domains are sets of linear orders with the property that, whenever the preferences of all voters belong to this set, the majority relation of any profile with an odd number of voters is ...transitive. Maximal Condorcet domains historically have attracted a special attention. We study maximal Condorcet domains that satisfy Arrow’s single-peakedness which is more general than Black’s single-peakedness. We show that all maximal Black’s single-peaked domains on the set of m alternatives are isomorphic but we found a rich variety of maximal Arrow’s single-peaked domains. We discover their recursive structure, prove that all of them have cardinality 2m−1, and characterise them by two conditions: connectedness and minimal richness. We also classify Arrow’s single-peaked Condorcet domains for m≤5 alternatives.
Nielsen et al. 35 proved that every 1-safe Petri net
N
unfolds into an event structure E
N
. By a result of Thiagarajan 46, these unfoldings are exactly the trace-regular event structures. ...Thiagarajan 46 conjectured that regular event structures correspond exactly to trace-regular event structures. In a recent paper (Chalopin and Chepoi 12), we disproved this conjecture, based on the striking bijection between domains of event structures, median graphs, and CAT(0) cube complexes. However, we proved that Thiagarajan’s conjecture is true for regular event structures whose domains are principal filters of universal covers of finite special cube complexes.
In the current article, we prove the converse: To any finite 1-safe Petri net
N
, one can associate a finite special cube complex X
N
such that the domain of the event structure E
N
(obtained as the unfolding of
N
) is a principal filter of the universal cover X̃
N
of X
N
. This establishes a bijection between 1-safe Petri nets and finite special cube complexes and provides a combinatorial characterization of trace-regular event structures.
Using this bijection and techniques from graph theory and geometry (MSO theory of graphs, bounded treewidth, and bounded hyperbolicity), we disprove yet another conjecture by Thiagarajan (from the paper with Yang 48) that the monadic second-order logic of a 1-safe Petri net (i.e., of its event structure unfolding) is decidable if and only if its unfolding is grid-free. It was proven by Thiagarajan and Yang 48 that the MSO logic is undecidable if the unfolding is not grid-free. Our counterexample is the trace-regular event structure that arises from a virtually special square complex Z. The domain of this event structure
Ė
Z
is the principal filter of the universal cover Z̃ of Z in which to each vertex we added a pendant edge. The graph of the domain of
Ė
Z
has bounded hyperbolicity (and, thus, the event structure
Ė
Z
is grid-free) but has infinite treewidth. Using results of Seese, Courcelle, and Müller and Schupp, we show that this implies that the MSO theory of the event structure
Ė
Z
is undecidable.
We characterize vertex-transitive median graphs of non-exponential growth as the Cartesian products of finite hypercubes with finite dimensional lattice graphs. Additionally, we prove that every ...median graph without convex subgraphs isomorphic to K1,3 or the 4-pan graph is isomorphic to the weak Cartesian product of finite paths, rays and two way infinite paths.
We characterize regular median graphs of linear growth as the Cartesian product of finite hypercubes with the two-way infinite path. This solves a problem posed by Imrich and Klavžar in 2011.
Simple rectilinear polygons (i.e. rectilinear polygons without holes or cutpoints) can be regarded as finite rectangular cell complexes coordinatized by two finite dendrons. The intrinsic
l
1
-metric ...is thus inherited from the product of the two finite dendrons via an isometric embedding. The rectangular cell complexes that share this same embedding property are called ramified rectilinear polygons. The links of vertices in these cell complexes may be arbitrary bipartite graphs, in contrast to simple rectilinear polygons where the links of points are either four-cycles or paths of length at most three. Ramified rectilinear polygons are particular instances of rectangular complexes obtained from cube-free median graphs, or equivalently simply connected rectangular complexes with triangle-free links. The underlying graphs of finite ramified rectilinear polygons can be recognized among graphs in linear time by a Lexicographic Breadth-First-Search. Whereas the symmetry of a simple rectilinear polygon is very restricted (with automorphism group being a subgroup of the dihedral group
D
4
), ramified rectilinear polygons are universal: every finite group is the automorphism group of some ramified rectilinear polygon.
Learning graph prototypes for shape recognition Raveaux, Romain; Adam, Sébastien; Héroux, Pierre ...
Computer vision and image understanding,
07/2011, Letnik:
115, Številka:
7
Journal Article
Recenzirano
Odprti dostop
► The computation of graph prototypes reduces the complexity of graph classification. ► Discriminative prototypes have a better classification power than median graphs. ► Generalized prototypes ...provide better classification results than set prototypes. ► Dedicated genetic algorithm are efficient for different prototype computation. ► Using many prototypes per class enable to improve classification accuracy
This paper presents some new approaches for computing graph prototypes in the context of the design of a structural nearest prototype classifier. Four kinds of prototypes are investigated and compared:
set median graphs,
generalized median graphs,
set discriminative graphs and
generalized discriminative graphs. They differ according to (i) the graph space where they are searched for and (ii) the objective function which is used for their computation. The first criterion allows to distinguish
set prototypes which are selected in the initial graph training set from
generalized prototypes which are generated in an infinite set of graphs. The second criterion allows to distinguish
median graphs which minimize the sum of distances to all input graphs of a given class from
discriminative graphs, which are computed using classification performance as criterion, taking into account the inter-class distribution. For each kind of prototype, the proposed approach allows to identify one or many prototypes per class, in order to manage the trade-off between the classification accuracy and the classification time.
Each graph prototype generation/selection is performed through a genetic algorithm which can be specialized to each case by setting the appropriate encoding scheme, fitness and genetic operators.
An experimental study performed on several graph databases shows the superiority of the generation approach over the selection one. On the other hand, discriminative prototypes outperform the generative ones. Moreover, we show that the classification rates are improved while the number of prototypes increases. Finally, we show that discriminative prototypes give better results than the median graph based classifier.
We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.
For cubic ...median graphs
G
the condition of linear growth can be weakened to the condition that
G
has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.
PDF
