Inverse symmetric Dammann gratings

Inverse symmetric Dammann grating is a special grating, whose transition points are reflection symmetric about the midpoint with inverse phase offset in one period. It can produce even-numbered or odd-numbered array illumination when the phase modulations are pi or a specific value. Numerical solutions optimized by the steepest-descent algorithm for binary phase and multilevel phases with splitting ratio from I x 4 to 1 x 14 are given. Fabrication of 1 x 6 array without the zero-order intensity and 1 x 7 array with the zero-order intensity are made from the same amplitude mask. A 6 x 6 output without the crossed zero-orders was achieved by crossing two one-dimensional 1 x 6 inverse symmetric Dammann gratings. This grating may have potential value for practical applications. (C) 2008 Elsevier B.V. All rights reserved.

The most persistent soft-clique in a set of sampled graphs

When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques. We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations. Copyright 2012 by the author(s)/owner(s).

Stabilization of symmetric formations to motion around convex loops

We provide a cooperative control algorithm to stabilize symmetric formations to motion around closed curves suitable for mobile sensor networks. This work extends previous results for stabilization of symmetric circular formations. We study a planar particle model with decentralized steering control subject to limited communication. Because of their unique spectral properties, the Laplacian matrices of circulant graphs play a key role. We illustrate the result for a skewed superellipse, which is a type of curve that includes circles, ellipses, and rounded parallelograms. © 2007 Elsevier B.V. All rights reserved.

Collective motion of self-propelled particles: Stabilizing symmetric formations on closed curves

We provide feedback control laws to stabilize formations of multiple, unit speed particles on smooth, convex, and closed curves with definite curvature. As in previous work we exploit an analogy with coupled phase oscillators to provide controls which isolate symmetric particle formations that are invariant to rigid translation of all the particles. In this work, we do not require all particles to be able to communicate; rather we assume that inter-particle communication is limited and can be modeled by a fixed, connected, and undirected graph. Because of their unique spectral properties, the Laplacian matrices of circulant graphs play a key role. The methodology is demonstrated using a superellipse, which is a type of curve that includes circles, ellipses, and rounded rectangles. These results can be used in applications involving multiple autonomous vehicles that travel at constant speed around fixed beacons. ©2006 IEEE.

On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Antimedian graphs

Antimedian graphs are introduced as the graphs in which for every triple of vertices there exists a unique vertex x that maximizes the sum of the distances from x to the vertices of the triple. The Cartesian product of graphs is antimedian if and only if its factors are antimedian. It is proved that multiplying a non-antimedian vertex in an antimedian graph yields a larger antimedian graph. Thin even belts are introduced and proved to be antimedian. A characterization of antimedian trees is given that leads to a linear recognition algorithm.

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O.mlog n/ time whether G is a median graph with geodetic number 2

Equal opportunity networks, distance-balanced graphs, and Wiener game

Given a graph G and a set X ⊆ V(G), the relative Wiener index of X in G is defined as WX (G) = {u,v}∈X 2  dG(u, v) . The graphs G (of even order) in which for every partition V(G) = V1 +V2 of the vertex set V(G) such that |V1| = |V2| we haveWV1 (G) = WV2 (G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u ∈ V(G) have the same total distance DG(u) = v∈V(G) dG(u, v). Some related problems are posed along the way, and the so-called Wiener game is introduced.

Raman selection rules for vibration-rotation transitions in symmetric top molecules

Symmetry restrictions on Raman selection rules can be obtained, quite generally, by considering a Raman allowed transition as the result of two successive dipole allowed transitions, and imposing the usual symmetry restrictions on the dipole transitions. This leads to the same results as the more familiar polarizability theory, but the vibration-rotation selection rules are easier to obtain by this argument. The selection rules for symmetric top molecules involving the (+l) and (-l) components of a degenerate vibrational level with first-order Coriolis splitting are derived in this paper. It is shown that these selection rules depend on the order of the highest-fold symmetry axis Cn, being different for molecules with n=3, n=4, or n ≧ 5; moreover the selection rules are different again for molecules belonging to the point groups Dnd with n even, and Sm with 1/2m even, for which the highest-fold symmetry axes Cn and Sm are related by m=2n. Finally it is shown that an apparent anomaly between the observed Raman and infra-red vibration-rotation spectra of the allene molecule is resolved when the correct selection rules are used, and a value for the A rotational constant of allene is derived without making use of the zeta sum rule.

Conditional symmetric instability in sting-jet storms

Sting jets are transient mesoscale jets of air that descend from the tip of the cloud head towards the top of the boundary layer in severe extratropical cyclones and can lead to damaging surface wind gusts. This recently identified jet is distinct from the well-documented jets associated with the cold and warm conveyor belts. One mechanism proposed for their development is the release of conditional symmetric instability (CSI). Here the spatial distribution and temporal evolution of several CSI diagnostics in four severe storms are analysed. A sting jet has been identified in three of these storms; for comparison, we also analysed one storm that did not have a sting jet, even though it hadmany of the apparent features of sting-jet storms. The sting-jet storms are distinct from the non-sting-jet storms by having much greater andmore extensive conditional instability (CI) and CSI. CSI is released by ascending air parcels in the cloud head in two of the sting-jet storms and by descending air parcels in the other sting-jet storm. By contrast, only weak CI to ascending air parcels is present at the cloud-head tip in the non-sting-jet storm. CSI released by descending air parcels, as diagnosed by decaying downdraught slantwise convective available potential energy (DSCAPE), is collocated with the sting jets in all three sting-jet storms and has a localisedmaximum in two of them. Consistent evolutions of saturated moist potential vorticity are found.We conclude that CSI release has a role in the generation of the sting jet, that the sting jet may be driven by the release of instability to both ascending and descending parcels, and that DSCAPE could be used as a discriminating diagnostic for the sting jet based on these four case-studies.

Symmetric Push-Sum Protocol for decentralised aggregation

Gossip (or Epidemic) protocols have emerged as a communication and computation paradigm for large-scale networked systems. These protocols are based on randomised communication, which provides probabilistic guarantees on convergence speed and accuracy. They also provide robustness, scalability, computational and communication efficiency and high stability under disruption. This work presents a novel Gossip protocol named Symmetric Push-Sum Protocol for the computation of global aggregates (e.g., average) in decentralised and asynchronous systems. The proposed approach combines the simplicity of the push-based approach and the efficiency of the push-pull schemes. The push-pull schemes cannot be directly employed in asynchronous systems as they require synchronous paired communication operations to guarantee their accuracy. Although push schemes guarantee accuracy even with asynchronous communication, they suffer from a slower and unstable convergence. Symmetric Push- Sum Protocol does not require synchronous communication and achieves a convergence speed similar to the push-pull schemes, while keeping the accuracy stability of the push scheme. In the experimental analysis, we focus on computing the global average as an important class of node aggregation problems. The results have confirmed that the proposed method inherits the advantages of both other schemes and outperforms well-known state of the art protocols for decentralized Gossip-based aggregation.

The importance of surface pressure changes in the response of the atmosphere to zonally-symmetric thermal and mechanical forcing

he classical problem of the response of a balanced, axisymmetric vortex to thermal and mechanical forcing is re-examined, paying special attention to the lower boundary condition. The correct condition is DΦ/Dt = 0, where Φ is the geopotential and D/Dt the material derivative, which explicitly accounts for a mass redistribution as part of the mean-flow response. This redistribution is neglected when using the boundary condition Dp/Dt = 0, which has conventionally been applied in this problem. It is shown that applying the incorrect boundary condition, and thereby ignoring the surface pressure change, leads to a zonal wind acceleration δū/δt that is too strong, especially near the surface. The effect is significant for planetary-scale forcing even when applied at tropopause level. A comparison is made between the mean-flow evolution in a baroclinic life-cycle, as simulated in a fully nonlinear, primitive-equation model, and that predicted by using the simulated eddy fluxes in the zonally-symmetric response problem. Use of the correct lower boundary condition is shown to lead to improved agreement.

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

The disk-percolation model on graphs

We study a long-range percolation model whose dynamics describe the spreading of an infection on an infinite graph. We obtain a sufficient condition for phase transition and prove all upper bound for the critical parameter of spherically symmetric trees. (C) 2008 Elsevier B.V. All rights reserved.