Combinatorica
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
On Gardner’s Conjecture
Combinatorica - Tập 42 - Trang 553-558 - 2021
Gardner conjectured that if two bounded measurable sets A, B ⊂ ℝn are equidecomposable by a set of isometries Γ generating an amenable group then A and B admit a measurable equidecomposition by all isometries. Cieśla and Sabok asked if there is a measurable equidecomposition using isometries only in the group generated by Γ. We answer this question negatively.
Improved Bounds for Rota's Basis Conjecture
Combinatorica - Tập 39 - Trang 265-272 - 2018
We prove that, if B1,...,Bn are disjoint bases of a rank-n matroid, then there are at least
$$\frac{n}{{7\log n}}$$
disjoint transversals of (B1,...,Bn) that are also bases.
Linear algebra methods for forbidden configurations
Combinatorica - Tập 31 - Trang 1-19 - 2011
We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given m and a k×l (0,1)-matrix F we define forb(m,F) as the maximum number of columns in a simple m-rowed matrix A for which no k×l submatrix of A is a row and column permutation of F. In set theory notation, F is a forbidden trace. For all k-rowed F (simple or non-simple) Füredi has shown that forb(m,F) is O(m
...... hiện toàn bộ
An extension of the Erdős-Szekeres theorem on large angles
Combinatorica - Tập 7 Số 2 - Trang 161-169 - 1987
Isomorphic factorizations VIII: Bisectable trees
Combinatorica - Tập 4 - Trang 169-179 - 1984
A tree is called even if its line set can be partitioned into two isomorphic subforests; it is bisectable if these forests are trees. The problem of deciding whether a given tree is even is known (Graham and Robinson) to be NP-hard. That for bisectability is now shown to have a polynomial time algorithm. This result is contained in the proof of a theorem which shows that if a treeS is bisectable t...... hiện toàn bộ
Cycle Traversability for Claw-Free Graphs and Polyhedral Maps
Combinatorica - Tập 40 - Trang 405-433 - 2020
Let G be a graph, and
$$v \in V(G)$$
and
$$S \subseteq V(G)\setminus{v}$$
of size at least k. An important result on graph connectivity due to Perfect states that, if v and S are k-linked, then a (k−1)-link between a vertex v and S can be extended to a k-link between v and S such that the endvertices of the (k−1)-link are also the endvertices of the k-link. We begin by proving a generalization...... hiện toàn bộ
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents
Combinatorica - Tập 20 - Trang 545-568 - 2000
matrix to within a multiplicative factor of
. To this end we develop the first strongly polynomial-time algorithm for matrix scaling –– an important nonlinear optimization problem with many applications. Our work suggests a simple new (slow) polynomial time decision algorithm for bipartite perfect matching, conceptually different from classical approaches.
Polynomial Lym Inequalities
Combinatorica - Tập 25 - Trang 19-38 - 2004
For a Sperner family A
⊂ 2[n] let A
i
denote the family of all i-element sets in A. We sharpen the LYM inequality
$$
{\sum\nolimits_i {{\left| {{\user1{\mathcal{A}}}_{i} } \right|}/{\left( {{}^{n}_{i} } \right)} \leqslant 1} }
$$
by add...... hiện toàn bộ
Tổng số: 1,195
- 1
- 2
- 3
- 4
- 5
- 6
- 10