hely:

[Szokatlan IDŐ, a szokott hely, kezdjünk pontosan] a 2 előadás:

Abstract: There is continuing interest in the distribution of small subgraphs of graphs by isomorphism type. For trees, the corresponding question is the distribution of small subtrees by isomorphism type, as a small random subset of vertices in a tree likely has no edges at all. We prove the following conjecture of Bubeck and Linial: if in a sequence of trees, where the tree size goes to infinity, the proportion of $k$-vertex paths among $k$-vertex subtrees becomes negligible, then almost all $k$-vertex subtrees are stars. We also show that the maximum number of nonisomorphic subtrees (of all sizes) of trees on $n$ vertices is $O(5^{n/4})$.

It is joint work with Éva Czabarka, and Stephan Wagner.

Abstract: Leaf-labeled binary trees (a.k.a. phylogenetic trees) and tanglegrams are of interest to biologists. For a rooted binary tree on $n$ leaves, any subset of $k$ leaves induces a rooted binary tree by taking all paths connecting these leaves, placing the new root on the vertex closest to the original root of the tree, and suppressing all non-root degree two vertices in the resulting tree. The inducibility of a $k$-leaf rooted binary tree in an $n$-leaf rooted binary tree is the proportion of $k$-subsets of leaves that induce a tree isomorphic to that tree; the inducibility of any rooted binary tree is the limit superior of its inducibility in any sequence of binary trees. We show a number of results on the inducibility of certain types of binary trees. A tanglegram is a pair of rooted binary trees on the same number of leaves with a fixed matching on the leaves; its crossing number is the minimum number of crossings we can have when we draw this in the plane such that the two binary trees are drawn as plane trees and the crossings are only allowed on the edges corresponding to the given matchings. The tanglegram crossing number is used to estimate relevant biological quantities (e.g. in parasite-host trees). We show that the expected value of tangregram crossing number in a random tanglegram on $n$-leaf trees is $\Theta(n^2)$, i.e. as large as possible.

It is joint work with László Székely, and Stephan Wagner.

Minden érdeklődőt szeretettel várunk,

Péter