An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

Embeddings of m-cycle systems and incomplete m-cycle systems: m<=14

In this paper we completely settle the embedding problem for m-cycle systems with m less than or equal to 14. We also solve the more general problem of finding m-cycle systems of K-v - K-u when m is an element of {4,6,7,8,10,12,14}.

A conjecture on small embeddings of partial Steiner triple systems

A well-known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order v for all v equivalent to 1 or 3 (mod 6), v greater than or equal to 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order v < 2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. (C) 2002 Wiley Periodicals, Inc.

Metrics on diagram groups and uniform embeddings in a Hilbert space

"Vegeu el resum a l'inici del document del fitxer adjunt".

Quantum symmetries for exceptional SU(4) modular invariants associated with conformal embeddings

Three exceptional modular invariants of SU(4) exist at levels 4, 6 and 8. They can be obtained from appropriate conformal embeddings and the corresponding graphs have self-fusion. From these embeddings, or from their associated modular invariants, we determine the algebras of quantum symmetries, obtain their generators,and, as a by-product, recover the known graphs E4, E6 and E8 describing exceptional quantum subgroups of type SU(4). We also obtain characteristic numbers (quantum cardinalities, dimensions) for each of them and for their associated quantum groupoïds.

Discourse Type Clustering using POS n-gram Profiles and High-Dimensional Embeddings

Abstract: To cluster textual sequence types (discourse types/modes) in French texts, K-means algorithm with high-dimensional embeddings and fuzzy clustering algorithm were applied on clauses whose POS (part-ofspeech) n-gram profiles were previously extracted. Uni-, bi- and trigrams were used on four 19th century French short stories by Maupassant. For high-dimensional embeddings, power transformations on the chi-squared distances between clauses were explored. Preliminary results show that highdimensional embeddings improve the quality of clustering, contrasting the use of bi and trigrams whose performance is disappointing, possibly because of feature space sparsity.

From Word Embeddings to Large Vocabulary Neural Machine Translation

Dans ce mémoire, nous examinons certaines propriétés des représentations distribuées de mots et nous proposons une technique pour élargir le vocabulaire des systèmes de traduction automatique neurale. En premier lieu, nous considérons un problème de résolution d'analogies bien connu et examinons l'effet de poids adaptés à la position, le choix de la fonction de combinaison et l'impact de l'apprentissage supervisé. Nous enchaînons en montrant que des représentations distribuées simples basées sur la traduction peuvent atteindre ou dépasser l'état de l'art sur le test de détection de synonymes TOEFL et sur le récent étalon-or SimLex-999. Finalament, motivé par d'impressionnants résultats obtenus avec des représentations distribuées issues de systèmes de traduction neurale à petit vocabulaire (30 000 mots), nous présentons une approche compatible à l'utilisation de cartes graphiques pour augmenter la taille du vocabulaire par plus d'un ordre de magnitude. Bien qu'originalement développée seulement pour obtenir les représentations distribuées, nous montrons que cette technique fonctionne plutôt bien sur des tâches de traduction, en particulier de l'anglais vers le français (WMT'14).

Simultaneous Embeddings Of Graphs As Median And Antimedian Subgraphs

The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r 2, there exists a connected graph H such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G, J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H.

(In)Complete acquisition of Turkish among Turkish German bilinguals in Germany and Turkey: an analysis of complex embeddings in narratives

Although most researchers recognise that the language repertoire of bilinguals canmvary, few studies have tried to address variation in bilingual competence in any detail. This study aims to take a first step towards further understanding the way in which bilingual competencies can vary at the level of syntax by comparing the use of syntactic embeddings among three different groups of Turkish�German bilinguals. The approach of the present paper is new in that different groups of bilinguals are compared with each other, and not only with monolingual speakers, as is common in most studies in the field. The analysis focuses on differences in the use of embeddings in Turkish, which are generally considered to be one of the more complex aspects of Turkish grammar. The study shows that young Turkish� German bilingual adults who were born and raised in Germany use fewer, and less complex embeddings than Turkish�German bilingual returnees who had lived in Turkey for eight years at the time of recording. The present study provides new insights in the nature of bilingual competence, as well as a new perspective on syntactic change in immigrant Turkish as spoken in Europe.

On the manifold structure of the set of unparameterized embeddings with low regularity

Given manifolds M and N, with M compact, we study the geometrical structure of the space of embeddings of M into N, having less regularity than C(infinity) quotiented by the group of diffeomorphisms of M.