Let $T_{s}H$ be the graph obtained from a given graph $H$ by subdividing each edge $s$ times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph $H$, there exist graphs $G$ with $O\left(s\right)$ edges that are Ramsey with respect to $T_{s}H$.

Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

In this paper, we consider a possible representation of a DNA sequence in a quaternary tree, in which one can visualize repetitions of subwords (seen as suffixes of subsequences). The CGR-tree turns a sequence of letters into a Digital Search Tree (DST), obtained from the suffixes of the reversed sequence. Several results are known concerning the height, the insertion depth for DST built from independent successive random sequences having the same distribution. Here the successive inserted words...

Inspired by probabilistic number theory, we establish necessary and sufficient conditions under which the numbers of cycles with lengths in arbitrary sets posses an asymptotic limit law. The approach can be extended to deal with the counts of components with the size constraints for other random combinatorial structures.

Relative dimensions of isotypic components of $N$th order tensor representations of the symmetric group on $n$ letters give a Plancherel-type measure on the space of Young diagrams with $n$ cells and at most $N$ rows. It was conjectured by G. Olshanski that dimensions of isotypic components of tensor representations of finite symmetric groups, after appropriate normalization, converge to a constant with respect to this family of Plancherel-type measures in the limit when $\frac{N}{\sqrt{n}}$ converges to a constant. The main...

In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand’s lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini–Kalai–Schramm (BKS) noise sensitivity theorem....

Let $m\ge 3$ be an integer. The so-called$m$-ary search treeis a discrete time Markov chain which is very popular in theoretical computer science, modelling famous algorithms used in searching and sorting. This random process satisfies a well-known phase transition: when $m\le 26$, the asymptotic behavior of the process is Gaussian, but for $m\ge 27$ it is no longer Gaussian and a limit $W^{DT}$ of a complex-valued martingale arises. In this paper, we consider the multitype branching process which is the continuous time version...

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set $S\subset [1,n]$ satisfies $\left|S\right|\ge \frac{n}{2}$, then $S$ must contain a non-degenerate Hilbert cube of dimension $\lfloor {log}_2{log}_{2}n-3\rfloor$. In this paper we prove that in a random set $S$ determined by $\mathrm{Pr}\{s\in S\}=\frac{1}{2}$ for $1\le s\le n$, the maximal dimension of non-degenerate Hilbert cubes is a.e. nearly ${log}_2{log}_{2}n+{log}_2{log}_2{log}_{2}n$ and determine the threshold function for a non-degenerate $k$-cube.

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ’ₖ(G). Let fₖ be defined by $fₖ\left(\Delta \right)=ma{x}_{G:\Delta \left(G\right)=\Delta }{\chi }^{\text{'}}ₖ\left(G\right)$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.

We study the relations between several notions of dimension for an additive set, some of which are well-known and some of which are more recent, appearing for instance in work of Schoen and Shkredov. We obtain bounds for the ratios between these dimensions by improving an inequality of Lev and Yuster, and we show that these bounds are asymptotically sharp, using in particular the existence of large dissociated subsets of {0,1}ⁿ ⊂ ℤⁿ.

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph...