Matching Points with Squares

Given a class of geometric objects and a point set P, a -matching of P is a set of elements of such that each C _i contains exactly two elements of P and each element of P lies in at most one C _i . If all of the elements of P belong to some C _i , M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of -matchings for point sets in the plane when is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for the L _∞ metric and the L ₁ metric always admit a Hamiltonian path.     

Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of disjoint copies of K_d,d. This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.     

Bounds relating the weakly connected domination number to the total domination number and the matching number

Let G=(V,E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V,E∩(S×V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted . A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. In this paper, we show that . Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α^′(G). We also establish that , and show that for every tree T.     

Structural analysis of a fractional matching problem

Mixed Software Programming refers to a novel software development paradigm resulting from efforts to combine two different programming approaches: Solo Programming and Pair Programming. Solo Programming refers to the traditional practice of assigning a single developer to develop a software module and Pair Programming refers to a relatively new approach where two developers work simultaneously on developing a module. In Mixed Programming, given a set of modules to be developed, a chosen subset of modules may be developed using Solo Programming and the remaining modules using Pair Programming.Motivated by applications in Mixed Software Programming, we consider the following generalization of classical fractional 1-matching problem: Given an undirected simple graph G=(V;E), and a positive number F, find values for x_e,e∈E, satisfying the following:

1.

.

2.

, where δ(i)={e∈E:e=(i,j)},i∈V.

3.

Maximize {2∑_e∈Ex_e−F|{i∈V:∑_e∈δ(i)x_e=1}|}.

We show that this problem is solvable in strongly polynomial time. Our primary focus in this paper is on obtaining the structure of the optimal solution for an arbitrary instance of the problem.     

The early exercise region for Bermudan options on two underlyings

This paper investigates the early exercise region for Bermudan options on two underlying assets. We present a set of analytical validation results for the early exercise region which can be used as a means of validating pricing techniques. When all strike prices are identical we show the existence of an intersection point such that for any asset price pair below this point early exercise is always optimal. We develop an approximation to this point in the two asset put case. When the strike prices are not all equal, we show that three separate cases exist for the early exercise region. For a Bermudan put on two assets we present these cases and show that there exists a critical point in which the boundaries of the two asset early exercise region bifurcate. Comparisons are drawn between the Bermudan results presented and the corresponding American option results.     

Five-torsion in the homology of the matching complex on 14 vertices

J.L. Andersen proved that there is 5-torsion in the bottom nonvanishing homology group of the simplicial complex of graphs of degree at most two on seven vertices. We use this result to demonstrate that there is 5-torsion also in the bottom nonvanishing homology group of the matching complex on 14 vertices. Combining our observation with results due to Bouc and to Shareshian and Wachs, we conclude that the case n=14 is exceptional; for all other n, the torsion subgroup of the bottom nonvanishing homology group has exponent three or is zero. The possibility remains that there is other torsion than 3-torsion in higher-degree homology groups of when n≥13 and n≠14. Research of J. Jonsson was supported by European Graduate Program “Combinatorics, Geometry, and Computation”, DFG-GRK 588/2.     

Model reduction using the Vorobyev moment problem

Given a nonsingular complex matrix and complex vectors v and w of length N, one may wish to estimate the quadratic form w ^* A ^− 1 v, where w ^* denotes the conjugate transpose of w. This problem appears in many applications, and Gene Golub was the key figure in its investigations for decades. He focused mainly on the case A Hermitian positive definite (HPD) and emphasized the relationship of the algebraically formulated problems with classical topics in analysis - moments, orthogonal polynomials and quadrature. The essence of his view can be found in his contribution Matrix Computations and the Theory of Moments, given at the International Congress of Mathematicians in Zürich in 1994. As in many other areas, Gene Golub has inspired a long list of coauthors for work on the problem, and our contribution can also be seen as a consequence of his lasting inspiration. In this paper we will consider a general mathematical concept of matching moments model reduction, which as well as its use in many other applications, is the basis for the development of various approaches for estimation of the quadratic form above. The idea of model reduction via matching moments is well known and widely used in approximation of dynamical systems, but it goes back to Stieltjes, with some preceding work done by Chebyshev and Heine. The algebraic moment matching problem can for A HPD be formulated as a variant of the Stieltjes moment problem, and can be solved using Gauss-Christoffel quadrature. Using the operator moment problem suggested by Vorobyev, we will generalize model reduction based on matching moments to the non-Hermitian case in a straightforward way. Unlike in the model reduction literature, the presented proofs follow directly from the construction of the Vorobyev moment problem. The work was supported by the GAAS grant IAA100300802 and by the Institutional Research Plan AV0Z10300504.     

柱前衍生-超高效液相色谱-单重四极杆质谱法分析不同产地烤烟的20种游离氨基酸

为了分析烤烟中游离氨基酸含量与烤烟香型、产地的关系,以国内14个烟草种植省份的138个调制后的烤烟中部叶片为材料,采用柱前衍生-超高效液相色谱-单重四极杆质谱法对烤烟中的20种游离氨基酸进行分析。方法表征结果显示该方法满足分析要求,适合烤烟中游离氨基酸的检测。对调制后烤烟中部叶片的游离氨基酸分析结果显示,烤烟的游离氨基酸含量在产地间差异很大（28.50%~94.20%）,其中天冬酰胺、谷氨酰胺含量的相对标准偏差（RSD）超过80%;在3种典型香型（浓香型、清香型和中间香型）烤烟中,浓香型烤烟游离氨基酸含量的RSD大于其他两种香型。对同一香型的不同种植省份和同一省份不同香型的烤烟游离氨基酸分析结果显示,其含量呈现一定的规律。     

Complex dynamics of an archetypal self-excited SD oscillator driven by moving belt friction

We propose an archetypal self-excited system driven by moving belt friction, which is constructed with the smooth and discontinuous(SD) oscillator proposed by the Cao et al. and the classical moving belt. The moving belt friction is modeled as the Coulomb friction to formulate the mathematical model of the proposed self-excited SD oscillator. The equilibrium states of the unperturbed system are obtained to show the complex equilibrium bifurcations. Phase portraits are depicted to present the hyperbolic structure transition, the multiple stick regions, and the friction-induced asymmetry phenomena. The numerical simulations are carried out to demonstrate the friction-induced vibration of multiple stick-slip phenomena and the stick-slip chaos in the perturbed self-excited system. The results presented here provide an opportunity for us to get insight into the mechanism of the complex friction-induced nonlinear dynamics in mechanical engineering and geography.