Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree ?. We use the Lovasz local lemma to show the following two results about colourings ? of the edges of the complete graph Kn. If for each vertex v of Kn the colouring ? assigns each colour to at most (n - 2)/(22.4?2) edges emanating from v, then there is a copy of G in Kn which is properly edge-coloured by ?. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409433, 2003]. On the other hand, if ? assigns each colour to at most n/(51?2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from ?. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Szekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernandez, Procacci, and Scoppola [preprint, arXiv:0910.1824]. (c) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425436, 2012

Weak quasi-randomness for uniform hypergraphs

We study quasi-random properties of k-uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung-Graham-Wilson theorem for quasi-random graphs. Moreover, let K(k) be the complete graph on k vertices and M(k) the line graph of the graph of the k-dimensional hypercube. We will show that the pair of graphs (K(k),M(k)) has the property that if the number of copies of both K(k) and M(k) in another graph G are as expected in the random graph of density d, then G is quasi-random (in the sense of the Chung-Graham-Wilson theorem) with density close to d. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 1-38, 2012

The Tripartite Ramsey Number for Trees

We prove that for all epsilon>0 there are alpha>0 and n(0)is an element of N such that for all n >= n(0) the following holds. For any two-coloring of the edges of Kn, n, n one color contains copies of all trees T of order t <=(3 - epsilon)n/2 and with maximum degree Delta(T)<= n(alpha). This confirms a conjecture of Schelp. (c) 2011 Wiley Periodicals, Inc. J Graph Theory 69: 264300, 2012

Measurements of atmospheric neutrinos and antineutrinos in the MINOS far detector

This paper reports measurements of atmospheric neutrino and antineutrino interactions in the MINOS Far Detector, based on 2553 live-days (37.9 kton-years) of data. A total of 2072 candidate events are observed. These are separated into 905 contained-vertex muons and 466 neutrino-induced rock-muons, both produced by charged-current nu(mu) and (nu) over bar (mu) interactions, and 701 contained-vertex showers, composed mainly of charged-current nu(e) and (nu) over bar (e) interactions and neutral-current interactions. The curvature of muon tracks in the magnetic field of the MINOS Far Detector is used to select separate samples of nu(mu) and (nu) over bar (mu) events. The observed ratio of (nu) over bar (mu) to v(mu) events is compared with the Monte Carlo ( MC) simulation, giving a double ratio of R((nu) over bar/nu)data/R(nu) over bar/nu MC = 1.03 +/- 0.08(stat) +/- 0.08(syst). The v(mu) and (nu) over bar (mu) data are separated into bins of L/E resolution, based on the reconstructed energy and direction of each event, and a maximum likelihood fit to the observed L/E distributions is used to determine the atmospheric neutrino oscillation parameters. This fit returns 90% confidence limits of |Delta m(2)| = (1.9 +/- 0.4) x 10(-3) eV(2) and sin(2)2 theta > 0.86. The fit is extended to incorporate separate nu(mu) and (nu) over bar mu oscillation parameters, returning 90% confidence limits of |Delta m(2)| - |Delta(m) over bar (2)| = 0.6(-0.8)(+2.4) x 10(-3) eV(2) on the difference between the squared-mass splittings for neutrinos and antineutrinos.

Texture descriptor based on partially self-avoiding deterministic walker on networks

Texture image analysis is an important field of investigation that has attracted the attention from computer vision community in the last decades. In this paper, a novel approach for texture image analysis is proposed by using a combination of graph theory and partially self-avoiding deterministic walks. From the image, we build a regular graph where each vertex represents a pixel and it is connected to neighboring pixels (pixels whose spatial distance is less than a given radius). Transformations on the regular graph are applied to emphasize different image features. To characterize the transformed graphs, partially self-avoiding deterministic walks are performed to compose the feature vector. Experimental results on three databases indicate that the proposed method significantly improves correct classification rate compared to the state-of-the-art, e.g. from 89.37% (original tourist walk) to 94.32% on the Brodatz database, from 84.86% (Gabor filter) to 85.07% on the Vistex database and from 92.60% (original tourist walk) to 98.00% on the plant leaves database. In view of these results, it is expected that this method could provide good results in other applications such as texture synthesis and texture segmentation. (C) 2012 Elsevier Ltd. All rights reserved.

Matrix-vector multiplication and triangular linear solver using GPGPU for symmetric positive definite matrices derived from elliptic equations

The modern GPUs are well suited for intensive computational tasks and massive parallel computation. Sparse matrix multiplication and linear triangular solver are the most important and heavily used kernels in scientific computation, and several challenges in developing a high performance kernel with the two modules is investigated. The main interest it to solve linear systems derived from the elliptic equations with triangular elements. The resulting linear system has a symmetric positive definite matrix. The sparse matrix is stored in the compressed sparse row (CSR) format. It is proposed a CUDA algorithm to execute the matrix vector multiplication using directly the CSR format. A dependence tree algorithm is used to determine which variables the linear triangular solver can determine in parallel. To increase the number of the parallel threads, a coloring graph algorithm is implemented to reorder the mesh numbering in a pre-processing phase. The proposed method is compared with parallel and serial available libraries. The results show that the proposed method improves the computation cost of the matrix vector multiplication. The pre-processing associated with the triangular solver needs to be executed just once in the proposed method. The conjugate gradient method was implemented and showed similar convergence rate for all the compared methods. The proposed method showed significant smaller execution time.

Nonlocal asymmetric exclusion process on a ring and conformal invariance

We present a one-dimensional nonlocal hopping model with exclusion on a ring. The model is related to the Raise and Peel growth model. A nonnegative parameter u controls the ratio of the local backwards and nonlocal forwards hopping rates. The phase diagram, and consequently the values of the current, depend on u and the density of particles. In the special case of half-lling and u = 1 the system is conformal invariant and an exact value of the current for any size L of the system is conjectured and checked for large lattice sizes in Monte Carlo simulations. For u > 1 the current has a non-analytic dependence on the density when the latter approaches the half-lling value.