Saturating stable matchings

I relate bipartite graph matchings to stable matchings. I prove a necessary and sufficient condition for the existence of a saturating stable matching, where every agent on one side is matched, for all possible preferences. I extend my analysis to perfect stable matchings, where every agent on both sides is matched.     

Estimation variances for estimators of product densities and pair correlation functions of planar point processes

Approximations of the estimation variances of kernel estimators of the pair correlation function and the product density of a planar Poisson process are given. Furthermore, a heuristic approximation of the estimation variance of an estimator of the pair correlation function of a general planar point process is suggested. All formulae have been tested by simulation experiments.     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

Log-fractional stable processes

The first problem attacked in this paper is answering the question whether all 1/-self-similar -stable processes with stationary increments are -stable motions. The answer is yes for = 2, no for 1<2 and unknown for 0<<1. We single out the log-fractional stable processes for 1<2, different from -stable motions for ≠2. They can be regarded as the limit of fractional stable processes as the exponent in the kernel tends to 0. The paper ends with a limit theorem for partial sum processes of moving averages of iid random variables in the domain of attraction of a strictly stable law, with log-fractional stable processes as limits in law. The conditions involve de Haan's class Π of slowly varying functions.     

Transversals and multicolored matchings

Ryser conjectured that the number of transversals of a latin square of order n is congruent to n modulo 2. Balasubramanian has shown that the number of transversals of a latin square of even order is even. A 1‐factor of a latin square of order n is a set of n cells no two from the same row or the same column. We prove that for any latin square of order n, the number of 1‐factors with exactly n ? 1 distinct symbols is even. Also we prove that if the complete graph K_2n, n ≥ 8, is edge colored such that each color appears on at most edges, then there exists a multicolored perfect matching. © 2004 Wiley Periodicals, Inc.     

The stable marriage problem with master preference lists

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.     

Self-similar fragmentations derived from the stable tree I

The basic object we consider is a certain model of continuum random tree, called the stable tree. We construct a fragmentation process (F ^– (t),t0) out of this tree by removing the vertices located under height t. Thanks to a self-similarity property of the stable tree, we show that the fragmentation process is also self-similar. The semigroup and other features of the fragmentation are given explicitly. Asymptotic results are given, as well as a couple of related results on continuous-state branching processes. Research supported in part by NSF Grant DMS-0071448. Mathematics Subject Classification (2000):60J25, 60G52, 60J80     

Weakly connected domination stable trees

A dominating set D ⊆ V(G) is a weakly connected dominating set in G if the subgraph G[D] _w = (N _G [D], E _w ) weakly induced by D is connected, where E _w is the set of all edges having at least one vertex in D. Weakly connected domination number _γw (_G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. A graph G is said to be weakly connected domination stable or just _γw -stable if _γw (G) = _{γ w} (G + e) for every edge e belonging to the complement Ḡ of G. We provide a constructive characterization of weakly connected domination stable trees.      

Maximum skew-symmetric flows and matchings

The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp [7] and the blocking flow method of Dinits [4], obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit node capacities our blocking skew-symmetric flow algorithm has time bounds similar to those established in [8, 21] for Dinits algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in time, which matches the time bound for the algorithm of Micali and Vazirani [25]. Finally, extending a clique compression technique of Feder and Motwani [9] to particular skew-symmetric graphs, we speed up the implied maximum matching algorithm to run in time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on skew-symmetric flows and their applications are presented.Mathematics Subject Classification (1991): 90C27, 90B10, 90C10, 05C85     

Symmetrization, symmetric stable processes, and Riesz capacities

Let be a symmetric -stable process killed on exiting an open subset of . We prove a theorem that describes the behavior of its transition probabilities under polarization. We show that this result implies that the probability of hitting a given set in the complement of in the first exit moment from increases when and are polarized. It can also lead to symmetrization theorems for hitting probabilities, Green functions, and Riesz capacities. One such theorem is the following: Among all compact sets in with given volume, the balls have the least -capacity ( ).

     

图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

Global Matching of Random Restriction Maps

Sequence alignment has been studied for some time and there is a developed theory of alignment statistics. DNA restriction maps are aligned by comparing locations of cut sites or restriction fragment lengths. The statistical theory of their alignments is less well developed than that of sequence alignment. In this paper we estimate the probability that two random restriction maps match under certain matching model.     

On cuts and matchings in planar graphs

We study the max cut problem in graphs not contractible toK ₅, and optimum perfect matchings in planar graphs. We prove that both problems can be formulated as polynomial size linear programs.Supported by the joint project Combinatorial Optimization of the Natural Sciences and Engineering Research Council of Canada and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

复合Poisson-geometric风险模型下第n次索赔时的破产概率研究

在复合Poisson-geometric风险模型下,通过构造一个特殊的Gerber-Shiu函数,推导出此风险模型下Gerber-Shiu函数满足的更新方程,破产时刻和直到破产时的索赔次数的联合密度函数,得到了第n次索赔时的破产概率的数学表达式．     

Two-term trace estimates for relativistic stable processes

We prove trace estimates for the relativistic α-stable process extending the result of Bañuelos and Kulczycki (2008) in the stable case.