24,394 research outputs found
Pach’s Animal Problem Within the Bounding Box
Full text linkA collection of unit cubes with integer coordinates in ℝ³ is an animal if its union is homeomorphic to the 3-ball. Pach’s animal problem asks whether any animal can be transformed to a single cube by adding or removing cubes one by one in such a way that any intermediate step is an animal as well. Here we provide an example of an animal that cannot be transformed to a single cube this way within its bounding box
Topologická a geometrická kombinatorika
No full text1 Topological and Geometrical Combinatorics Martin Tancer Abstract The task of the thesis is to present several new results on topological methods in combinatorics. The results can be split into two main streams. The first stream regards intersection patterns of convex sets. It is shown in the thesis that finite projective planes cannot be intersection patterns of convex sets of fixed dimension which answers a question of Alon, Kalai, Matoušek and Meshulam. Another result shows that d-collapsibility (a necessary condition on properties of in- tersection patterns of convex sets in dimension d) is NP-complete for recognition if d ≥ 4. In addition it is shown that d-collapsibility is not a necessary condition on properties of intersection patterns of good covers, which disproves a conjecture of G. Wegner from 1975. The second stream considers algorithmic hardness of recognition of simplicial com- plexes embeddable into Rd . The following results are proved: It is algorithmically un- decidable whether a k-dimensional simplicial complex piecewise-linearly embeds into Rd for d ≥ 5 and k ∈ {d−1, d}; and this problem is NP-hard if d ≥ 4 and d ≥ k ≥ 2d−2 3 .1 Topological and Geometrical Combinatorics Martin Tancer Český abstrakt práce Cílem práce je prezentovat několik nových výsledků v oblasti topologických metod v kombinatorice. Výsledky lze zařadit do dvou hlavních oblastí. První oblast pokrývá průsečíkové struktury konvexních množin. V práci je ukázáno, že konečné projektivní roviny nemůžou být průsečíkovými strukturami konvexních množin pevné dimenze, což odpovídá na otázku Alona, Kalaie, Matouška a Meshu- lama. Dále je ukázáno, že d-kolabovatelnost (nutná podmínka na vlastnosti průsečíkových struktur konvexních množin v dimenzi d) je NP-těžká k rozpoznání pro d ≥ 4. A také je ukázáno, že d-kolabovatelnost není nutnou podmínkou na vlastnosti průsečíkových vzorů dobrých pokrytí, což vyvrací domněnku G. Wegnera z roku 1975. Do druhé oblasti spadá několik výsledků ohledně algoritmické obtížnosti rozpoz- návání simpliciálních komplexů vnořitelných do Rd . Konkrétněji, je algortmicky ne- rozhodnutelné, zda lze k-rozměrný simpliciální komplex po částech lineárně vnořit do Rd , pokud d ≥ 5 a k ∈ {d − 1, d}. Dále je tento problém NP-těžký, pokud d ≥ 4 a d ≥ k ≥ 2d−2 3 .Katedra aplikované matematikyDepartment of Applied MathematicsFaculty of Mathematics and PhysicsMatematicko-fyzikální fakult
Parameterized Complexity of Untangling Knots
Full text linkDeciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves.
We show that the II^- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set
Topological and geometrical combinatorics
No full text1 Topological and Geometrical Combinatorics Martin Tancer Abstract The task of the thesis is to present several new results on topological methods in combinatorics. The results can be split into two main streams. The first stream regards intersection patterns of convex sets. It is shown in the thesis that finite projective planes cannot be intersection patterns of convex sets of fixed dimension which answers a question of Alon, Kalai, Matoušek and Meshulam. Another result shows that d-collapsibility (a necessary condition on properties of in- tersection patterns of convex sets in dimension d) is NP-complete for recognition if d ≥ 4. In addition it is shown that d-collapsibility is not a necessary condition on properties of intersection patterns of good covers, which disproves a conjecture of G. Wegner from 1975. The second stream considers algorithmic hardness of recognition of simplicial com- plexes embeddable into Rd . The following results are proved: It is algorithmically un- decidable whether a k-dimensional simplicial complex piecewise-linearly embeds into Rd for d ≥ 5 and k ∈ {d−1, d}; and this problem is NP-hard if d ≥ 4 and d ≥ k ≥ 2d−2 3
Optimal Bounds for the Colorful Fractional Helly Theorem
Full text linkThe well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: for every α ∈ (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ∈ (0, 1] with the following property. Let ℱ₁, … , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n₁, … , n_{d+1}, respectively. If at least α n₁ n₂ ⋯ n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ∈ [d+1] such that ℱ_i contains a subfamily of size at least β_{col} n_i with a nonempty intersection. (A colorful (d+1)-tuple is a (d+1)-tuple (F₁, … , F_{d+1}) such that F_i belongs to ℱ_i for every i.)
The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with β_{col} = α/(d+1). In 2017 Kim proved the theorem with better function β_{col}, which in particular tends to 1 when α tends to 1. Kim also conjectured what is the optimal bound for β_{col}(α, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984.
We verify Kim’s conjecture by extending Kalai’s approach to the colorful scenario. Moreover, we obtain optimal bounds also in a more general setting when we allow several sets of the same color
Barycentric Cuts Through a Convex Body
Full text linkLet K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question.
It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3
Jack Alive / Martin Dead : The Location of the "Author" in Jack London\u27s Martin Eden
No full textThis essay is an attempt to read Martin Eden, Jack Londonʼs autobiographical novel, in terms of the inextricable relationship between the author and the protagonist. Critics have often taken the unbalanced plot and the lack of ironic distance between narrator and character in Martin Eden as the technical weakness of London, but this paper argues that the achievement of this novel owes a great deal to the attachment of London to Martin. The unbalanced structure is a necessary product of the severe struggle of the author to kill his romantic alter ego. // Martin, who aspires to win Ruth Morse, tries to cross class boundaries by making a career of a writer. Even after realizing the emptiness of Ruth, who turns out to be nothing but a typical figure of the bourgeoisie, he somehow persists in loving her. The notion underlying here is that, for Martin, love, career and art are fundamentally inseparable. He objects to the aestheteʼs view of Brissenden on account of his separation of art from career. Martinʼs identity and life consist only in the triunity of love/career/art; the alternative is the repudiation of life. Thus, the unnatural delay of his disappointment in love can be regarded as Londonʼs strategy to set the suicide of Martin as the necessary consequence of the story. // By finishing the story and killing Martin, London finally detaches himself from Martin, reconstructs his self, and, unlike Martin, survives as a professional writer. In this sense, Martin Eden is a story about “writerʼs self-reconstruction.
Recommended from our members
Letter from Martin Chizzick
No full textCongratulations to Duane Pearsall for receiving the Enterpreneur of the Year award; note on the letter was written by Pearsall and it mentions that Martin, the author of the letter, died in a airplane accident
On the interplay of combinatorics, geometry, topology and computational complexity
Full text linkMatematicko-fyzikální fakult
Robert Martin Tiffin's Mystery Man Newspaper Articles
No full textAdvertiser-Tribune newspaper clippings featuring a story about Robert Martin (written by Nancy Kleinhenz), a local author from Tiffin (Ohio) who wrote under the pseudonym of Lee Roberts, and two of his short stories. Martin wrote mystery novels in his spare time, creating more than 22 mystery novels. For more information about Robert Martin and a list of books go to http://www.mysteryfile.com/RMartin/JBennett.html
- …
