On the forced matching numbers of bipartite graphs

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.

A new indexing method for high dimensional dataset

Indexing high dimensional datasets has attracted extensive attention from many researchers in the last decade. Since R-tree type of index structures are known as suffering curse of dimensionality problems, Pyramid-tree type of index structures, which are based on the B-tree, have been proposed to break the curse of dimensionality. However, for high dimensional data, the number of pyramids is often insufficient to discriminate data points when the number of dimensions is high. Its effectiveness degrades dramatically with the increase of dimensionality. In this paper, we focus on one particular issue of curse of dimensionality; that is, the surface of a hypercube in a high dimensional space approaches 100% of the total hypercube volume when the number of dimensions approaches infinite. We propose a new indexing method based on the surface of dimensionality. We prove that the Pyramid tree technology is a special case of our method. The results of our experiments demonstrate clear priority of our novel method.

On a New Approach to Williamson's Generalization of Pólya's Enumeration Theorem

Pólya’s fundamental enumeration theorem and some results from Williamson’s generalized setup of it are proved in terms of Schur- Macdonald’s theory (S-MT) of “invariant matrices”. Given a permutation group W ≤ Sd and a one-dimensional character χ of W , the polynomial functor Fχ corresponding via S-MT to the induced monomial representation Uχ = ind|Sdv/W (χ) of Sd , is studied. It turns out that the characteristic ch(Fχ ) is the weighted inventory of some set J(χ) of W -orbits in the integer-valued hypercube [0, ∞)d . The elements of J(χ) can be distinguished among all W -orbits by a maximum property. The identity ch(Fχ ) = ch(Uχ ) of both characteristics is a consequence of S-MT, and is equivalent to a result of Williamson. Pólya’s theorem can be obtained from the above identity by the specialization χ = 1W , where 1W is the unit character of W.

Uncertain natural frequency analysis of composite plates including effect of noise – A polynomial neural network approach

Acknowledgement SN and SS gratefully acknowledge the financial support from Lloyd’s Register Foundation Centre during this work.

Effect of Geometric Uncertainties on the Aerodynamic Characteristic of Offshore Wind Turbine Blades

Offshore wind turbines operate in a complex unsteady flow environment which causes unsteady aerodynamic loads. The unsteady flow environment is characterized by a high degree of uncertainty. In addition, geometry variations and material imperfections also cause uncertainties in the design process. Probabilistic design methods consider these uncertainties in order to reach acceptable reliability and safety levels for offshore wind turbines. Variations of the rotor blade geometry influence the aerodynamic loads which also affect the reliability of other wind turbine components. Therefore, the present paper is dealing with geometric uncertainties of the rotor blades. These can arise from manufacturing tolerances and operational wear of the blades. First, the effect of geometry variations of wind turbine airfoils on the lift and drag coefficients are investigated using a Latin hypercube sampling. Then, the resulting effects on the performance and the blade loads of an offshore wind turbine are analyzed. The variations of the airfoil geometry lead to a significant scatter of the lift and drag coefficients which also affects the damage-equivalent flapwise bending moments. In contrast to that, the effects on the power and the annual energy production are almost negligible with regard to the assumptions made.

Spectral graph theory with applications to quantum adiabatic optimization

In this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.