Some geometric applications of Dilworth's theorem (Q1330876): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Jenö Töröcsik / rank | |||
Property / reviewed by | |||
Property / reviewed by: László A. Székely / rank | |||
Property / author | |||
Property / author: Jenö Töröcsik / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: László A. Székely / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized exponents of a free arrangement of hyperplanes and Shepherd- Todd-Brieskorn formula / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjoint edges in geometric graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Three-Fold Branched Coverings of S 3 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3619797 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounding the vertex cover number of a hypergraph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Sets of Distances of n Points / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Knoten mit zwei Brücken / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Forcing disjoint segments in the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3040142 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Covering and coloring problems for relatives of intervals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3048864 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Knots / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4052427 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:15, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some geometric applications of Dilworth's theorem |
scientific article |
Statements
Some geometric applications of Dilworth's theorem (English)
0 references
10 August 1994
0 references
The authors apply Dilworth's theorem on partially ordered sets to two geometric problems. Answering an old problem of Avital, Hanani, Erdős, Kupitz, and Perles, they show that a graph drawn in the plane with straight line segments, such that the graph has \(n\) vertices, \(m> k^ 4 n\) edges, and no 3 vertices are collinear, must contain \(k+1\) pairwise disjoint edges. The other theorem says that given a set of points \(V\) and a set of axis- parallel rectangles in the plane, then either there are \(k+1\) rectangles such that no point of \(V\) belongs to more than one of them, or there are at most \(2\cdot 10^ 5 k^ 8\) points of \(V\) meeting all rectangles.
0 references
transversal
0 references
geometric graph
0 references
Dilworth's theorem
0 references
partially ordered sets
0 references
plane
0 references
rectangles
0 references
0 references