搜索结果: 91-105 共查到“知识库 组合数学”相关记录451条 . 查询时间(6.291 秒)
Heuristic and exact solutions to the inverse power index problem for small voting bodies
electoral systems simple games weighted voting games square root rule Penrose limit theorem
2012/2/29
Power indices are mappings that quantify the influence of the members of a voting body on collective decisions a priori. Their nonlinearity and discontinuity makes it difficult to compute inverse imag...
Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux
Computational Theoretical Challenges Counting Solid Standard Young Tableaux
2012/2/29
In how many ways can you place n chocolate pieces all of different sizes in an n by n chocolate box, in such a way that when you go from left to right and from top to bottom, there are no gaps AND the...
Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments
Hamilton decompositions regular expanders Kelly's conjecture large tournaments
2012/2/29
A long-standing conjecture of Kelly states that every regular tournament on n vertices can be decomposed into (n-1)/2 edge-disjoint Hamilton cycles. We prove this conjecture for large n. In fact, we p...
The geometry of elation groups of a finite projective space
geometry elation groups finite projective space
2012/2/29
We study the geometry of point-orbits of elation groups with a given center and axis of a finite projective space. We show that there exists a 1-1 correspondence from conjugacy classes of such groups ...
A proper edge coloring of a graph $G$ is called acyclic if there is no bichromatic cycle in $G$. The acyclic chromatic index of $G$, denoted by $\chi'_a(G)$, is the least number of colors $k$ such tha...
Given positive integers $d$ and $n$ with $n \geq d+1$, the existence of a normal integral cyclic polytope of dimension $d$ with $n$ vertices is proved. In addition, we show that, for any integers $d \...
Anatomy of the giant component: The strictly supercritical regime
Anatomy giant component strictly supercritical regime
2012/2/29
In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as it emerges from the critical window, i.e. for $p =...
Strongly Regular Cayley Graphs, Skew Hadamard Difference Sets, and Rationality of Relative Gauss Sums
strongly regular graph skew Hadamard difference set relative Gauss sum
2012/3/1
In this paper, we give constructions of strongly regular Cayley graphs and skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes in finite fields, and our results ...
The poset of the nilpotent commutator of a nilpotent matrix
Jordan type nilpotent matrix commutator poset
2012/2/29
Fix an n by n nilpotent matrix B with entries in an infinite field k. Assume that B is in Jordan canonical form with associated Jordan block partition P. It is well known that the nilpotent commutator...
For a graph G, its rth power G^r has the same vertex set as G, and has an edge between any two vertices within distance r of each other in G. We give a lower bound for the number of edges in the rth p...
Abstract: The existence question for tiling of the $n$-dimensional Euclidian space by crosses is well known. A few existence and nonexistence results are known in the literature. Of special interest a...
Abstract: Let M be a subset of {0, .., n} and F be a family of subsets of an n element set such that the size of A intersection B is in M for every A, B in F. Suppose that l is the maximum number of c...
The 1/3-2/3 conjecture for $N$-free ordered sets
Ordered set Linear extension N-free Balanced pair 1/3-2/3 Conjecture
2011/9/22
Abstract: A balanced pair in a finite ordered set $P=(V,\leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the real interval...
The solution space geometry of random linear equations
solution space geometry random linear equations Data Structures and Algorithms
2011/10/9
Abstract: We consider random systems of linear equations over GF(2) in which every equation binds k variables. We obtain a precise description of the clustering of solutions in such systems. In partic...
Edge-coloring series-parallel multigraphs
Edge-coloring series-parallel multigraphs Data Structures and Algorithms Combinatorics
2011/10/9
Abstract: We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colore...