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:
An extremal problem for Graham-Rothschild parameter words
Combinatorica - - 1989
This paper exposes connections between the theory of Möbius functions and extremal problems, extending ideas of Frankl and Pach [8]. Extremal results concerning the trace of objects in geometric lattices and Graham—Rothschild parameter posets are proved, covering previous results due to Sauer [16] and Perles and Shelah [17].
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......
On low-dimensional faces that high-dimensional polytopes must have
Combinatorica - Tập 10 - Trang 271-280 - 1990
We prove that every five-dimensional polytope has a two-dimensional face which is a triangle or a quadrilateral. We state and discuss the following conjecture: For every integerk≥1 there is an integer f(k) such that everyd-polytope,d≥f(k), has ak-dimensional face which is either a simplex or combinatorially isomorphic to thek-dimensional cube. We give some related results concerning facet-forming ......
On Ramsey—Turán type theorems for hypergraphs
Combinatorica - Tập 2 - Trang 289-295 - 1982
LetH
r
be anr-uniform hypergraph. Letg=g(n;H
r
) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH
r
. Lete =f(n;H
......
Matchings of cycles and paths in directed graphs
Combinatorica - Tập 27 - Trang 383-398 - 2008
In this paper we present a Berge-Tutte-type theorem for a matching problem in directed graphs. This extends the maximum matching problem in undirected graphs, the maximum even factor problem in weakly symmetric directed graphs proposed by W. H. Cunningham and J. F. Geelen in [6], and a packing problem for cycles and edges in undirected graphs. We show an Edmonds-Gallai-type structural description ......
How to find groups? (and how to use them in Erdős geometry?)
Combinatorica - Tập 32 - Trang 537-571 - 2012
Geometric questions which involve Euclidean distances often lead to polynomial relations of type F(x, y, z)=0 for some F ∈ ℝ[x, y, z]. Several problems of Combinatorial Geometry can be reduced to studying such polynomials which have many zeroes on n×n×n Cartesian products. The special case when the relation F = 0 can be re-written as z = f(x, y), for a polynomial or rational function f ∈ ℝ(x, y), ......
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......
An algorithm for finding hamilton paths and cycles in random graphs
Combinatorica - Tập 7 - Trang 327-341 - 1987
This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solv......
On the stochastic independence properties of hard-core distributions
Combinatorica - Tập 17 - Trang 369-391 - 1997
A probability measurep on the set μ of matchings in a graph (or, more generally 2-bounded hypergraph) Γ ishard-core if for some λ: Γ→[0,∞), the probabilityp(M) ofM∈μ is proportional to
$$\prod\nolimits_{A_ \in M} {\lambda (A)}$$
. We show that such distributions enjoy substantial approximate stochastic ......
Tổng số: 1,194
- 1
- 2
- 3
- 4
- 5
- 6
- 10