Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Hyperbolic unit groups and quaternion algebras

We classify the quadratic extensions K = Q[root d] and the finite groups G for which the group ring o(K)[G] of G over the ring o(K) of integers of K has the property that the group U(1)(o(K)[G]) of units of augmentation 1 is hyperbolic. We also construct units in the Z-order H(o(K)) of the quaternion algebra H(K) = (-1, -1/K), when it is a division algebra.

Integral group ring of the Suzuki sporadic simple group

Using the Luthar-Passi method, we investigate the classical Zassenhaus conjecture for the normalized unit group of the integral group ring of the Suzuki sporadic simple group Suz. As a consequence, for this group we confirm the Kimmerle`s conjecture on prime graphs.

Hypercentral unit groups and the hyperbolicity of a modular group algebra

We classify groups G such that the unit group U-1 (ZG) is hypercentral. In the second part, we classify groups G whose modular group algebra has hyperbolic unit groups U-1 (KG).

UNIT VECTOR FIELDS ON ANTIPODALLY PUNCTURED SPHERES: BIG INDEX, BIG VOLUME

We establish in this paper a lower bound for the volume of a unit vector field (v) over right arrow defined ou S(n) \ {+/-x}, n = 2,3. This lower bound is related to the sum of the absolute values of the indices of (v) over right arrow at x and -x.

Existence of orthogonal geodesic chords on Riemannian manifolds with concave boundary and homeomorphic to the N-dimensional disk

In this paper we give a proof of the existence of an orthogonal geodesic chord on a Riemannian manifold homeomorphic to a closed disk and with concave boundary. This kind of study is motivated by the link (proved in Giambo et al. (2005) [8]) of the multiplicity problem with the famous Seifert conjecture (formulated in Seifert (1948) [1]) about multiple brake orbits for a class of Hamiltonian systems at a fixed energy level. (C) 2010 Elsevier Ltd. All rights reserved.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Fast and reliable analyses of sulphite in fruit juices using a supramolecular amperometric detector encompassing in flow gas diffusion unit

A new compact system encompassing in flow gas diffusion unit and a wall-jet amperometric FIA detector, coated with a supramolecular porphyrin film, was specially designed as an alternative to the time-consuming Monier-Williams method, allowing fast, reproducible and accurate analyses of free sulphite species in fruit juices. In fact, a linear response between 0.64 and 6.4 ppm of sodium sulphite. LOD = 0.043 ppm, relative standard deviation of +/- 1.5% (n = 10) and analytical frequency of 85 analyses/h were obtained utilising optimised conditions. That superior analytical performance allows the precise evaluation of the amount of free sulphite present in foods, providing an important comparison between the standard addition and the standard injection methods. Although the first one is most frequently used, it was strongly influenced by matrix effects because of the unexpected reactivity of sulphite ions with the juice matrixes, leading to its partial consumption soon after addition. In contrast, the last method was not susceptible to matrix effects yielding accurate results, being more reliable for analytical purposes. (C) 2011 Elsevier Ltd. All rights reserved.

Spatiotemporal Pattern Formation in the Oscillatory Electro-Oxidation of Sulfide on a Platinum Disk

Spatiotemporal pattern formation in the electrocatalytic oxidation of sulfide on a platinum disk is investigated using electrochemical methods and a charge-coupled device (CCD) camera simultaneously. The system is characterized by different oscillatory regions spread over a wide potential range. An additional series resistor and a large electrode area facilitate observation of multiple regions of kinetic instabilities along the current/potential curve. Spatiotemporal patterns on the working electrode, such as fronts, pulses, spirals, twinkling eyes, labyrinthine stripes, and alternating synchronized deposition and dissolution, are observed at different operating conditions of series resistance and sweep rate.