Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution $p$ over a finite set $V$ of $n$ discrete variables and a positive integer $k$, find a decomposable model with tree-width $k$ that best fits $p$. If $\mathscr{H}$ is the generating hypergraph of a decomposable model and $p_{\mathscr{H}}$ is the estimate of $p$ under the model, we can measure...

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_k$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_k$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_k$(n) in amortized time O(1) and in space O($\sqrt{n}$).

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_k$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_k$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_k$(n) in amortized time O(1) and in space O($\sqrt{n}$).

We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following. For every integer $k\ge 2$ and every set $A$ of words over $k$ satisfying $\lim {\sup }_{n\to \infty }|A\cap {\left[k\right]}^n|/k^n>0$ there exist a word $c$ over $k$ and a sequence $\left(w_n\right)$ of left variable words over $k$ such that the set $c\cup \{c^{}{w}_0{\left(a_0\right)}^{}..{.}^{}{w}_n\left(a_n\right):n\in \mathbb{N}\text{and}{a}_0,...,a_n\in \left[k\right]\}$ is contained in $A$. While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

A Content Distribution Network (CDN) can be defined as an overlay system that replicates copies of contents at multiple points of a network, close to the final users, with the objective of improving data access. CDN technology is widely used for the distribution of large-sized contents, like in video streaming. In this paper we address the problem of finding the best server for each customer request in CDNs, in order to minimize the overall cost. We consider the problem as a transportation problem...

We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v=a_1{a}_2...a_m$ of integers such that 1) $1\le a_i\le n$, 2) $a_i=a_j,i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $$f(u,n)=O\left(n{2}^{O\left(\alpha {\left(n\right)}^{\left|u\right|-4}\right)}\right).$$ Here $\left|u\right|$ is the length of $u$ and $\alpha \left(n\right)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

We generalize to all interval exchanges the induction algorithm defined by Ferenczi and Zamboni for a particular class. Each interval exchange corresponds to an infinite path in a graph whose vertices are certain unions of trees we call castle forests. We use it to describe those words obtained by coding trajectories and give an explicit representation of the system by Rokhlin towers. As an application, we build the first known example of a weakly mixing interval exchange outside the hyperelliptic...