搜索结果: 1-15 共查到“数学 Matchings”相关记录19条 . 查询时间(0.102 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：Perfect Matchings in hypergraphs
超图 完美匹配 图论
2023/4/27
Matchings are fundamental objects in the study of graph theory. Unlike in graphs, finding maximum matchings in general hypergraphs is NP-hard -- its decision problem is actually one of the Karp’s 21 N...
Matchings and phylogenetic trees。
Random Walks on Trees and Matchings
Markov Chain Matchings Phylogenetic Tree Fourier analysis Zonal polynomials Coagulation-Fragmentation
2015/7/8
We give sharp rates of convergence for a natural Markov chain on the space of phylogenetic trees and dually for the natural random walk on the set of perfect matchings in the complete graph on 2n vert...
Cycles and sorting index for matchings and restricted permutations
Cycles and sorting index matchings and restricted permutations Combinatorics
2012/6/25
We prove that the Mahonian-Stirling pairs of permutation statistics $(\sor, \cyc)$ and $(\inv, \mathrm{rlmin})$ are equidistributed on the set of permutations that correspond to arrangements of $n$ no...
Partitions and Partial Matchings Avoiding Neighbor Patterns
set partition partial matching neighbor alignment left nesting right nesting.
2014/6/3
We obtain the generating functions for partial matchings avoiding neighbor alignments and for partial matchings avoiding neighbor alignments and left nestings. We show that there is a bijection betwee...
Oscillating Rim Hook Tableaux and Colored Matchings
Oscillating m-rim hook tableau m-colored matching lattice path bijection Dyck path packing
2014/6/3
Motivated by the question of finding a type B analogue of the bijection between oscillating tableaux and matchings, we find a correspondence between oscillating m-rim hook tableaux and m-colored match...
Abstract: We show how to construct homology bases for certain CW complexes in terms of discrete Morse theory and cellular homology. We apply this technique to study certain subcomplexes of the half cu...
Edge-Removal and Non-Crossing Perfect Matchings
Edge-Removal Non-Crossing Matchings Combinatorics Probability
2011/9/5
Abstract: We study the following problem - How many arbitrary edges can be removed from a complete geometric graph with 2n vertices such that the resulting graph always contains a perfect non-crossing...
Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels
Large matchings uniform hypergraphs conjectures of Erdos and Samuels Combinatorics Probability
2011/8/26
Abstract: In this paper we study conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by E...
Exponentially many perfect matchings in cubic graphs
Exponentially many perfect matchings cubic graphs
2011/1/21
We show that every cubic bridgeless graph G has at least 2|V (G)|/3656 perfect matchings.
This confirms an old conjecture of Lov´asz and Plummer.
Lattice Polynomials, 12312-Avoiding Partial Matchings and Even Trees
Lattice Polynomials Partial Matchings Even Trees
2010/11/22
The lattice polynomials $L_{i,j}(x)$ are introduced by Hough and Shapiro as a weighted count of certain lattice paths from the origin to the point $(i,j)$. In particular, $L_{2n, n}(x)$ reduces to th...
Computing the partition function for perfect matchings in a hypergraph
hypergraph perfect matching partition function permanent
2010/12/6
Given non-negative weights wS on the k-subsets S of a km-element set V , we consider the sum of the products wS1 · · ·wSm over all partitions V =S1 [ . . . [ Sm into pairwise disjoint k-subsets Si.
Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers)
Edge-Colouring Hypergraphs Properly Polychromatically
2010/12/15
Let the chromatic index of a hypergraph be the smallest number of colours needed to colour the
edges such that similarly-coloured edges are disjoint. Likewise, let the cover index be the maximum numb...
The covering radius problem for sets of perfect matchings
Perfect matchings Lovasz local lemma
2010/11/30
Consider the family of all perfect matchings of the complete graph K2n with 2n vertices.Given any collection M of perfect matchings of size s, there exists a maximum number f(n; x) such that if s f(...
Matchings, coverings, and Castelnuovo-Mumford regularity
Matchings coverings Castelnuovo-Mumford regularity
2010/12/6
We show how co-chordal covers of the edges of a graph give upper bounds on the Castelnuovo-Mumford regularity of its edge ideal. The proof is by an easy application of a deep result of
Kalai and Mesh...