Ramsey numbers for a disjoint union of good graphs

We give the Ramsey number for a disjoint union of some G-good graphs versus a graph G generalizing the results of Stahl (1975) [5] and Baskoro et al. (2006) [1] and the previous result of the author Bielak (2009) [2]. Moreover, a family of G-good graphs with s(G)>1 is presented.     

Stable routing under the Spanning Tree Protocol

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.     

Random walks and Brownian motion on cubical complexes

Cubical complexes are metric spaces constructed by gluing together unit cubes in an analogous way to the construction of simplicial complexes. We construct Brownian motion on such spaces, define random walks, and prove that the transition kernels of the random walks converge to that for Brownian motion. The proof involves pulling back onto the complex the distribution of Brownian sample paths on a single cube, combined with a distribution on walks between cubes. The main application lies in analysing sets of evolutionary trees: several tree spaces are cubical complexes and we briefly describe our results and applications in this context.     

Maker–Breaker domination game

We introduce the Maker–Breaker domination game, a two player game on a graph. At his turn, the first player, Dominator, selects a vertex in order to dominate the graph while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn. This game is a particular instance of the so-called Maker–Breaker games, that is studied here in a combinatorial context. In this paper, we first prove that deciding the winner of the Maker–Breaker domination game is pspace-complete, even for bipartite graphs and split graphs. It is then showed that the problem is polynomial for cographs and trees. In particular, we define a strategy for Dominator that is derived from a variation of the dominating set problem, called the pairing dominating set problem.     

Dirichlet forms and associated heat kernels on the Cantor set induced by random walks on trees

Transient random walk on a tree induces a Dirichlet form on its Martin boundary, which is the Cantor set. The procedure of the inducement is analogous to that of the Douglas integral on S¹ associated with the Brownian motion on the unit disk. In this paper, those Dirichlet forms on the Cantor set induced by random walks on trees are investigated. Explicit expressions of the hitting distribution (harmonic measure) ν and the induced Dirichlet form on the Cantor set are given in terms of the effective resistances. An intrinsic metric on the Cantor set associated with the random walk is constructed. Under the volume doubling property of ν with respect to the intrinsic metric, asymptotic behaviors of the heat kernel, the jump kernel and moments of displacements of the process associated with the induced Dirichlet form are obtained. Furthermore, relation to the noncommutative Riemannian geometry is discussed.     

具有固定直径的树的拉普拉斯谱半径

一个图称为毛毛虫,如果从它删去所有的悬挂点后得到的图是一个路.研究了具有固定直径的毛毛虫树的拉普拉斯谱半径,确定了其中具有最大拉普拉斯谱半径的毛毛虫树并且讨论了该树的一些性质.     

The mixed Lipschitz space and its dual for tree metrics

This paper develops a theory of harmonic analysis on spaces with tree metrics, extending previous work in this direction by Gavish, Nadler and Coifman (2010) [30] and Gavish and Coifman (2011, 2012) [28], [29]. We show how a natural system of martingales and martingale differences induced by a partition tree leads to simple and effective characterizations of the Lipschitz norm and its dual for functions on a single tree metric space. The restrictions we place on the tree metrics are far more general than those considered in previous work. As the dual norm is equal to the Earth Mover's Distance (EMD) between two probability distributions, we recover a simple formula for EMD with respect to tree distances presented by Charikar (2002) [36].We also consider the situation where an arbitrary metric is approximated by the average of a family of dominating tree metrics. We show that the Lipschitz norm and its dual for the tree metrics can be combined to yield an approximation to the corresponding norms for the underlying metric.The main contributions of this paper, however, are the generalizations of the aforementioned results to the setting of the product of two or more tree metric spaces. For functions on a product space, the notion of regularity we consider is not the Lipschitz condition, but rather the mixed Lipschitz condition that controls the size of a function's mixed difference quotient. This condition is extremely natural for datasets that can be described as a product of metric spaces, such as word-document databases. We develop effective formulas for norms equivalent to the mixed Lipschitz norm and its dual, and extend our results on combining pairs of trees.     

The tree property at double successors of singular cardinals of uncountable cofinality

Assuming the existence of a strong cardinal κ and a measurable cardinal above it, we force a generic extension in which κ is a singular strong limit cardinal of any given cofinality, and such that the tree property holds at ${\kappa }^{++}$.     

Redistribution of uranium and thorium by soil/plant interaction in a recultivated mining area

During the recultivation of the uranium mining area of K?vágósz?l?s (Hungary), the tailings were covered with clay and loess soil layers having a thickness of 30 cm and 100 cm, respectively. In the loess covering layer, acacia (Robinia pseudoacacia), poplars (Populus × albus, Populus × canescens), oak (Quercus pubescens), silver tree (Eleagnus angustifolia) were planted between 1996 and 2004. In order to establish the extent of the uranium and thorium transport from the sludge to the leaves by uptake and translocation processes through roots with a length higher than 1.3 m results in a remarkable redistribution of these pollutants, a gray poplar tree, growing spontaneously in the last uncovered tailing, being selected as reference tree. The U and Th concentrations in the leaves of the above-mentioned trees, in the covering layers as well as in the original sludge were determined by inductively coupled plasma sector field mass spectrometry (ICP-SF-MS). Generally, the Th concentration of the soils was about 4 times higher than that of uranium, while uranium concentration was about 10-130 times higher than that of thorium in the leaf samples and its concentration ranged from 28 to 1045 ng g^− 1, the last value belonging to the poplar tree growing on the last uncovered tailing. In order to assume the mobility and bioavailability of uranium if the dry leaves fall down, the uranium species in the leaves of the poplar tree growing in the uncovered reservoir were determined applying ultrasound-assisted extraction with distilled water and ammonium acetate as well as high performance liquid chromatographic (HPLC)-ICP-SF-MS technique. About 20% of total uranium could be extracted in form of uranyl cations and a presumably negatively charged uranium compound. Estimations revealed that the annual increment of U in the soil surface layer due to the dead fallen leaves in case of the investigated gray poplar (Populus × canescens) is about 1.2%.