Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAcyclic, connected and tree sets
144
0
0.0
(
0
)
Added by
Dominique Perrin
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a set $F$ of words, one associates to each word $w$ in $F$ an undirected graph, called its extension graph, and which describes the possible extensions of $w$ on the left and on the right. We investigate the family of sets of words defined by the property of the extension graph of each word in the set to be acyclic or connected or a tree. We prove that in a uniformly recurrent tree set, the sets of first return words are bases of the free group on the alphabet. Concerning acyclic sets, we prove as a main result that a set $F$ is acyclic if and only if any bifix code included in $F$ is a basis of the subgroup that it generates.
rate research
Read More
Tree sets are abstract structures that can be used to model various tree-shaped objects in combinatorics. Finite tree sets can be represented by finite graph-theoretical trees. We extend this representation theory to infinite tree sets. First we characterise those tree sets that can be represented by tree sets arising from infinite trees; these are precisely those tree sets without a chain of order type ${omega+1}$. Then we introduce and study a topological generalisation of infinite trees which can have limit edges, and show that every infinite tree set can be represented by the tree set admitted by a suitable such tree-like space.
Phylogenetic trees canonically arise as embeddings of phylogenetic networks. We recently showed that the problem of deciding if two phylogenetic networks embed the same sets of phylogenetic trees is computationally hard, blue{in particular, we showed it to be $Pi^P_2$-complete}. In this paper, we establish a polynomial-time algorithm for this decision problem if the initial two networks consists of a normal network and a tree-child network. The running time of the algorithm is quadratic in the size of the leaf sets.
A $k$-connected set in an infinite graph, where $k > 0$ is an integer, is a set of vertices such that any two of its subsets of the same size $ell leq k$ can be connected by $ell$ disjoint paths in the whole graph. We characterise the existence of $k$-connected sets of arbitrary but fixed infinite cardinality via the existence of certain minors and topological minors. We also prove a duality theorem for the existence of such $k$-connected sets: if a graph contains no such $k$-connected set, then it has a tree-decomposition which, whenever it exists, precludes the existence of such a $k$-connected set.
We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff from 1993, who proved that, under the same condition, there are four lines intersecting all the sets. In fact, we prove a colorful version of this result, under weakened conditions on the sets. A triple of sets $A,B,C$ in the plane is said to be a {em tight} if $textrm{conv}(Acup B)cap textrm{conv}(Acup C)cap textrm{conv}(Bcap C) eq emptyset.$ This notion was first introduced by Holmsen, where he showed that if $mathcal{F}$ is a family of compact convex sets in the plane in which every three sets form a tight triple, then there is a line intersecting at least $frac{1}{8}|mathcal{F}|$ members of $mathcal{F}$. Here we prove that if $mathcal{F}_1,dots,mathcal{F}_6$ are families of compact connected sets in the plane such that every three sets, chosen from three distinct families $mathcal{F}_i$, form a tight triple, then there exists $1le jle 6$ and three lines intersecting every member of $mathcal{F}_j$. In particular, this improves $frac{1}{8}$ to $frac{1}{3}$ in Holmsens result.
Recall that an excedance of a permutation $pi$ is any position $i$ such that $pi_i > i$. Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on $n$ letters is the same as those for which excedances happen exactly at ${1,dots, lfloor (n-1)/2 rfloor}$. Additionally, we show that the above is also the number of acyclic orientations with unique sink (AUSOs) of the complete bipartite graph $K_{lceil n/2 rceil, lfloor n/2 rfloor + 1}$. We also give a formula for the number of AUSOs of complete multipartite graphs. We conclude with observations on an extremal question of Cameron et al. concerning maximizers of (the number of) acyclic orientations, given a prescribed number of vertices and edges for the graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
