Vaguery + proof   198

[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery 
9 weeks ago by Vaguery
[1709.06217] Deterministic meeting of sniffing agents in the plane
Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are integers from the set of 0 to L-1. Each agent knows L and knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1 was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than \r{ho} or at distance at least \r{ho} from the other agent, for some real \r{ho} > 1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance.
agent-based  rather-interesting  random-processes  sensors  emergent-design  proof  to-write-about  consider:looking-to-see 
10 weeks ago by Vaguery
Magic: The Gathering is Turing complete / Boing Boing
Alex Churchill has posted a way to implement a Turing complete computer within a game of Magic: The Gathering ("Turing complete" is a way of classifying a calculating engine that is capable of general-purpose computation). The profound and interesting thing about the recurrence of Turing completeness in many unexpected places -- such as page-layout descriptive engines -- is that it suggests that there's something foundational about the ability to do general computation. It also suggests that attempts to limit general computation will be complicated by the continued discovery of new potential computing engines. That is, even if you lock down all the PCs so that they only play restricted music formats and not Ogg, if you allow a sufficiently speedy and scriptable Magic: The Gathering program to exist, someone may implement the Ogg player using collectible card games.
computational-complexity  computer-science  amusing  proof  unconventional-representation-schemes 
february 2018 by Vaguery
Proofs are not only often beautiful but also necessary | Dan McQuillan
I hope you get the idea. When mathematicians seem obsessed with rigor, it is at least in part due to our history of making mistakes, seemingly every time we tried to jump to a conclusion. But perhaps there’s something more. So for that, we end with a quote from William Thurston:

what we are doing is finding ways for people to understand and think about mathematics… what they really want is usually not some collection of of ‘answers’-what they want is understanding.
mathematics  proof  philosophy  to-write-about  consider:representation 
november 2017 by Vaguery
[1710.02741] A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
Given a triangulation of a point set in the plane, a \emph{flip} deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge.
It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips. We characterize when this is possible by proving the \emph{Orbit Conjecture} of Bose, Lubiw, Pathak and Verdonschot which states that \emph{all} labels can be simultaneously mapped to their destination if and only if \emph{each} label individually can be mapped to its destination.
Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the \emph{flip complex}, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
computational-geometry  proof  rather-interesting  to-write-about  to-simulate  plane-geometry 
november 2017 by Vaguery
[1605.06848] Nonnegative Matrix Factorization Requires Irrationality
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n×m matrix M into a product of a nonnegative n×d matrix W and a nonnegative d×m matrix H. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries.
matrices  computational-geometry  rather-interesting  to-write-about  to-understand  representation  proof  consider:classification 
november 2017 by Vaguery
[1707.00219] Angle-monotone Paths in Non-obtuse Triangulations
We reprove a result of Dehkordi, Frati, and Gudmundsson: every two vertices in a non-obtuse triangulation of a point set are connected by an angle-monotone path--an xy-monotone path in an appropriately rotated coordinate system. We show that this result cannot be extended to angle-monotone spanning trees, but can be extended to boundary-rooted spanning forests. The latter leads to a conjectural edge-unfolding of sufficiently shallow polyhedral convex caps.
computational-geometry  plane-geometry  rather-interesting  proof  nudge-targets  consider:looking-to-see  consider:algorithms 
november 2017 by Vaguery
[0904.2115] Colorful Strips
Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k−1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete.
We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k−1)+1.
Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges.
computational-geometry  proof  rather-interesting  to-write-about  hypergraphs  coloring  consider:algorithms 
november 2017 by Vaguery
[1710.00386] Orthogonal Terrain Guarding is NP-complete
A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery problem where one has to place at most k guards on a terrain made of n vertices in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NP-complete [SODA '10, SIAM J. Comput. '11] thereby solving a long-standing open question. They observe that their proof does not settle the complexity of Orthogonal Terrain Guarding where the terrain only consists of horizontal or vertical segments; those terrains are called rectilinear or orthogonal. Recently, Ashok et al. [SoCG'17] presented an FPT algorithm running in time kO(k)nO(1) for Dominating Set in the visibility graphs of rectilinear terrains without 180-degree vertices. They ask if Orthogonal Terrain Guarding is in P or NP-hard. In the same paper, they give a subexponential-time algorithm running in nO(n√) (actually even nO(k√)) for the general Terrain Guarding and notice that the hardness proof of King and Krohn only disproves a running time 2o(n1/4) under the ETH. Hence, there is a significant gap between their 2O(n1/2logn)-algorithm and the no 2o(n1/4) ETH-hardness implied by King and Krohn's result. In this paper, we answer those two remaining questions. We adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NP-complete. Then, we show how their reduction from Planar 3-SAT (as well as our adaptation for rectilinear terrains) can actually be made linear (instead of quadratic).
computational-complexity  computational-geometry  proof  consider:stress-testing  nudge-targets  consider:hardest-problems  to-write-about 
october 2017 by Vaguery
[1706.10206] Sums of Palindromes: an Approach via Automata
Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. However, the cases b = 2, 3, 4 were left unresolved.
We prove, using a decision procedure based on automata, that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem.
We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.
number-theory  rather-interesting  lovely  algorithms  proof  nudge-targets  consider:rediscovery  consider:representation  consider:looking-to-see 
october 2017 by Vaguery
[1502.04644] Beyond the Runs Theorem
Recently, a short and elegant proof was presented showing that a binary word of length n contains at most n−3 runs. Here we show, using the same technique and a computer search, that the number of runs in a binary word of length n is at most 2223n<0.957n.
strings  proof  permutations  looking-to-see  to-write-about  nudge-targets 
october 2017 by Vaguery
[math/0204106] The Second Hull of a Knotted Curve
The convex hull of a set K in space consists of points which are, in a certain sense, "surrounded" by K. When K is a closed curve, we define its higher hulls, consisting of points which are "multiply surrounded" by the curve. Our main theorem shows that if a curve is knotted then it has a nonempty second hull. This provides a new proof of the Fary/Milnor theorem that every knotted curve has total curvature at least 4pi.
knot-theory  geometry  topology  rather-interesting  feature-construction  proof  nudge-targets  consider:representation  consider:looking-to-see 
october 2017 by Vaguery
[1710.04247] Lagrange's Theorem for Binary Squares
We prove, using a decision procedure based on finite automata, that every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x.
via:twitter  rather-interesting  number-theory  proof  representation  to-write-about  formal-languages  nudge-targets  consider:looking-to-see  consider:open-questions 
october 2017 by Vaguery
[1405.0247] Spanning rigid subgraph packing and sparse subgraph covering
Rigidity, arising in discrete geometry, is the property of a structure that does not flex. Laman provides a combinatorial characterization of rigid graphs in the Euclidean plane, and thus rigid graphs in the Euclidean plane have applications in graph theory. We discover a sufficient partition condition of packing spanning rigid subgraphs and spanning trees.As a corollary, we show that a simple graph G contains a packing of k spanning rigid subgraphs and l spanning trees if G is (4k+2l)-edge-connected, and G−Z is essentially (6k+2l−2k|Z|)-edge-connected for every Z⊂V(G). Thus every (4k+2l)-connected and essentially (6k+2l)-connected graph G contains a packing of k spanning rigid subgraphs and l spanning trees. Utilizing it, we show that every 6-connected and essentially 8-connected graph G contains a spanning tree T such that G−E(T) is 2-connected. These improve some previous results. Sparse subgraph covering problems are also studied.
graph-theory  rigidity  classification  proof  feature-construction  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:rediscovery 
september 2017 by Vaguery
[1708.03228] Lower bounds for several online variants of bin packing
We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75.
bin-packing  operations-research  benchmarking  proof  algorithms  nudge-targets  consider:looking-to-see 
september 2017 by Vaguery
[math/9201305] Alternating sign matrices and domino tilings
We introduce a family of planar regions, called Aztec diamonds, and study the ways in which these regions can be tiled by dominoes. Our main result is a generating function that not only gives the number of domino tilings of the Aztec diamond of order n but also provides information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Several proofs of the formula are given. The problem turns out to have connections with the alternating sign matrices of Mills, Robbins, and Rumsey, as well as the square ice model studied by Lieb.
have-written-about  mathematical-recreations  tiling  combinatorics  representation  rather-interesting  proof  random-matrices 
september 2017 by Vaguery
[1608.03256v1] When Sets Can and Cannot Have MSTD Subsets
A finite set of integers A is a More Sums Than Differences (MSTD) set if |A+A|>|A−A|. While almost all subsets of {0,…,n} are not MSTD, interestingly a small positive percentage are. We explore sufficient conditions on infinite sets of positive integers such that there are either no MSTD subsets, at most finitely many MSTD subsets, or infinitely many MSTD subsets. In particular, we prove no subset of the Fibonacci numbers is an MSTD set, establish conditions such that solutions to a recurrence relation have only finitely many MSTD subsets, and show there are infinitely many MSTD subsets of the primes.
number-theory  proof  to-write-about  open-questions  nudge-targets 
may 2017 by Vaguery
[1201.2097v4] Partial Searchlight Scheduling is Strongly PSPACE-Complete
The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Scheduling Problem. Determining the computational complexity of deciding if the polygon can be searched by a given set of guards is a long-standing open problem.
Here we propose a generalization called the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, as opposed to the entire area. We prove that the corresponding decision problem is strongly PSPACE-complete, both in general and restricted to orthogonal polygons where the region to be searched is a rectangle.
Our technique is to reduce from the "edge-to-edge" problem for nondeterministic constraint logic machines, after showing that the computational power of such machines does not change if we allow "asynchronous" edge reversals (as opposed to "sequential").
computational-geometry  computational-complexity  planning  art-gallery-problems  proof  nudge-targets 
april 2017 by Vaguery
[1701.05475] Irrational Guards are Sometimes Needed
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon such that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is fully contained in the polygon.
Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is polygon which can be guarded by 3n guards with irrational coordinates but need 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.
computational-complexity  computational-geometry  planning  art-gallery-problems  algorithms  proof  rather-interesting  nudge-targets  to-write-about 
april 2017 by Vaguery
[1605.03546] ARRIVAL: A zero-player graph game in NP $cap$ coNP
Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination? It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this short paper, we prove that the problem is in NP ∩ coNP. This raises the question whether we have just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games.
graph-theory  dynamical-systems  proof  mathematical-recreations  feature-construction  nudge-targets 
april 2017 by Vaguery
[1104.0122] A Doubly Exponentially Crumbled Cake
We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjoint interiors, each of them having a point of P as the lower left corner; Alice keeps the rest. It has been conjectured that Bob can always secure at least half of the cake. This remains unsettled, and it is not even known whether Bob can get any positive fraction independent of n. We prove that if Alice can force Bob's share to tend to zero, then she must use very many points; namely, to prevent Bob from gaining more than 1/r of the cake, she needs at least 2^{2^{\Omega(r)}} points.
cake-cutting  open-questions  computational-geometry  proof  nudge-targets  consider:looking-to-see  to-write-about 
april 2017 by Vaguery
[0803.0726] A quadratic algorithm for road coloring
The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtman's proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
graph-theory  automata  combinatorics  rather-interesting  proof  nudge-targets  consider:looking-to-see 
april 2017 by Vaguery
[1611.04245] Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs
In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph G=(V,E), the number of totally cyclic orientations of G is equal to the value of |P(H,−1)|, where P(H,λ) is the chromatic polynomial of a hypergraph H which is constructed from G. Finally we show that the multiplicity of root "0" of P(H,λ) may be at least 2 for some connected hypergraphs H, and the multiplicity of root "1" of P(H,λ) may be 1 for some connected and separable hypergraphs H and may be 2 for some connected and non-separable hypergraphs H.
hypergraphs  not-the-same-thing  graph-theory  proof  nudge-targets  consider:rediscovery 
april 2017 by Vaguery
[1306.2741] Convex Equipartitions: The Spicy Chicken Theorem
We show that, for any prime power n and any convex body K (i.e., a compact convex set with interior) in Rd, there exists a partition of K into n convex sets with equal volumes and equal surface areas. Similar results regarding equipartitions with respect to continuous functionals and absolutely continuous measures on convex bodies are also proven. These include a generalization of the ham-sandwich theorem to arbitrary number of convex pieces confirming a conjecture of Kaneko and Kano, a similar generalization of perfect partitions of a cake and its icing, and a generalization of the Gromov-Borsuk-Ulam theorem for convex sets in the model spaces of constant curvature.
Most of the results in this paper appear in arxiv:1011.4762 and in arxiv:1010.4611. Since the main results and techniques there are essentially the same, we have merged the papers for journal publication. In this version we also provide a technical alternative to a part of the proof of the main topological result that avoids the use of compactly supported homology.
geometry  multiobjective-optimization  rather-interesting  proof  consider:looking-to-see  nudge-targets 
april 2017 by Vaguery
[1507.02355] The Shadows of a Cycle Cannot All Be Paths
A "shadow" of a subset S of Euclidean space is an orthogonal projection of S into one of the coordinate hyperplanes. In this paper we show that it is not possible for all three shadows of a cycle (i.e., a simple closed curve) in ℝ3 to be paths (i.e., simple open curves).
We also show two contrasting results: the three shadows of a path in ℝ3 can all be cycles (although not all convex) and, for every d≥1, there exists a d-sphere embedded in ℝd+2 whose d+2 shadows have no holes (i.e., they deformation-retract onto a point).
computational-geometry  rather-interesting  proof  nudge-targets  consider:looking-to-see 
april 2017 by Vaguery
[1307.5666] ErdH{o}s - Szekeres Theorem for Lines
According to the Erd\H{o}s-Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd\H os-Szekeres theorem.
geometry  Erdös  proof  to-write-about  consider:looking-to-see 
april 2017 by Vaguery
[1702.08328] A Universal Ordinary Differential Equation
An astonishing fact was established by Lee A. Rubel in 81: there exists a fixed non-trivial fourth-order polynomial differential algebraic equation (DAE) such that for any continuous function ϕ on the reals, and for any positive continuous function ϵ(t), it has a ∞ solution with |y(t)−ϕ(t)|<ϵ(t) for all t. Rubel provided an explicit example of such a polynomial DAE. More examples have later been proposed by other authors.
However, while these results may seem very surprising, their proofs are quite frustrating for a computability theorist. First, the constructed DAE have no unique solutions for a given initial data. This is very different from usual notions of universality since there is no unambiguous notion of evolution for a given initial data. Second, the proofs usually rely on solutions that are piecewise defined and sometimes non-constructive. Third, the proofs of these results can be interpreted more as the fact that polynomial algebraic differential equations is a too loose a model compared to classical ordinary differential equations. In particular, one may challenge whether the result is really a universality result.
The question whether one can require the solution that approximates ϕ to be the unique solution for a given initial data is a well known open problem [Rub81] (page 2), [boshernitzan1986universal] (Conjecture 6.2). In this article, we solve it and show that Rubel's statement holds for polynomial ordinary differential equations (ODEs), and since polynomial ODEs have a unique solution given an initial data, this positively answers Rubel's open problem. More precisely, we show that there exists a \textbf{fixed} polynomial ODE such that for any ϕ and ϵ there exists some initial condition that yields a solution that is ϵ-close to ϕ at all times.
diffyQ  nonlinear-dynamics  approximation  representation  rather-interesting  analytical-expressions  proof 
april 2017 by Vaguery
[1503.00566] $N$-Division Points of Hypocycloids
We show that the $n$-division points of all rational hypocycloids are constructible with an unmarked straightedge and compass for all integers $n$, given a pre-drawn hypocycloid. We also consider the question of constructibility of $n$-division points of hypocycloids without a pre-drawn hypocycloid in the case of a tricuspoid, concluding that only the $1$, $2$, $3$, and $6$-division points of a tricuspoid are constructible in this manner.
compass-and-straightedge  construction  proof  computational-geometry  nudge-targets  consider:looking-to-see 
april 2017 by Vaguery
[1408.3696] On A Generalization of "Eight Blocks to Madness"
We consider a puzzle such that a set of colored cubes is given as an instance. Each cube has unit length on each edge and its surface is colored so that what we call the Surface Color Condition is satisfied. Given a palette of six colors, the condition requires that each face should have exactly one color and all faces should have different colors from each other. The puzzle asks to compose a 2x2x2 cube that satisfies the Surface Color Condition from eight suitable cubes in the instance. Note that cubes and solutions have 30 varieties respectively. In this paper, we give answers to three problems on the puzzle: (i) For every subset of the 30 solutions, is there an instance that has the subset exactly as its solution set? (ii) Create a maximum sized infeasible instance (i.e., one having no solution). (iii) Create a minimum sized universal instance (i.e., one having all 30 solutions). We solve the problems with the help of a computer search. We show that the answer to (i) is no. For (ii) and (iii), we show examples of the required instances, where their sizes are 23 and 12, respectively. The answer to (ii) solves one of the open problems that were raised in [E.Berkove et al., "An Analysis of the (Colored Cubes)^3 Puzzle," Discrete Mathematics, 308 (2008) pp. 1033-1045].
puzzles  combinatorics  constraint-satisfaction  proof  mathematical-recreations  rather-interesting  to-write-about 
march 2017 by Vaguery
[1007.3181] On Folding a Polygon to a Polyhedron
We show that the open problem presented in "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" [DO07] is solved by a theorem of Burago and Zalgaller [BZ96] from more than a decade earlier.
computational-geometry  rather-interesting  polygons  polyhedra  proof  to-write-about 
march 2017 by Vaguery
[1302.2898] Mathematics in the Age of the Turing Machine
The article gives a survey of mathematical proofs that rely on computer calculations and formal proofs.
history  history-of-science  computational-methods  proof  mathematics  review  rather-interesting  to-write-about 
march 2017 by Vaguery
[1408.6474] Developments in Formal Proofs
This report describes three particular technological advances in formal proofs. The HOL Light proof assistant will be used to illustrate the design of a highly reliable system. Today, proof assistants can verify large bodies of advanced mathematics; and as an example, we turn to the formal proof in Coq of the Feit-Thompson Odd Order theorem in group theory. Finally, we discuss advances in the automation of formal proofs, as implemented in proof assistants such as Mizar, Coq, Isabelle, and HOL Light.
proof  mathematics  logic-programming  programming-language  representation  rather-interesting  nudge-targets  consider:representation 
march 2017 by Vaguery
[1602.07220] Packings of Regular Pentagons in the Plane
We show that every packing of congruent regular pentagons in the Euclidean plane has density at most (5−5‾√)/3, which is about 0.92. More specifically, this article proves the pentagonal ice-ray conjecture of Henley (1986), and Kuperberg and Kuperberg (1990), which asserts that an optimal packing of congruent regular pentagons in the plane is a double lattice, formed by aligned vertical columns of upward pointing pentagons alternating with aligned vertical columns of downward pointing pentagons. The strategy is based on estimates of the areas of Delaunay triangles. Our strategy reduces the pentagonal ice-ray conjecture to area minimization problems that involve at most four Delaunay triangles. These minimization problems are solved by computer. The computer-assisted portions of the proof use techniques such as interval arithmetic, automatic differentiation, and a meet-in-the-middle algorithm.
packing  plane-geometry  proof  granular-materials  limits  rather-interesting  to-write-about  consider:simulation  consider:looking-to-see 
march 2017 by Vaguery
[1701.00419] The tilings of deficient squares by ribbon L-tetrominoes are diagonally cracked
We consider tilings of deficient rectangles by the set 4 of ribbon L-tetrominoes. A tiling exists iff the rectangle is a square of odd side. The missing cell is on the main NW--SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position for (4m+3)×(4m+3). The majority of the tiles in a tiling are paired and each pair tiles a 2×4 rectangle. The tiles in an irregular position and the missing cell form a NW--SE diagonal crack, located in a thin region symmetric about the diagonal, made out of 3×3 squares that overlap over one of the corner cells. The crack divides the square in two equal area parts. The number of tilings of a (4m+1)×(4m+1) deficient square is equal to the number of tilings by dominoes of a 2m×2m square. The number of tilings of a (4m+3)×(4m+3) deficient square is twice the number of tilings by dominoes of a (2m+1)×(2m+1) deficient square, with missing cell placed on the main diagonal. If an extra 2×2 tile is added to 4, we call the new tile set +4. A tiling of a deficient rectangle by +4 exists iff the rectangle is a square of odd side. The missing cell is on the main NW--SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position for (4m+3)×(4m+3). The majority of the tiles in a tiling are either paired tetrominoes and each pair tiles a 2×4 rectangle, or are 2×2 squares. The tiles in an irregular position and the missing cell form a NW--SE diagonal crack, located in a thin region symmetric about the diagonal, made out of 3×3 squares that overlap over one of the corner cells.
tiling  proof  rather-interesting  nudge-targets  consider:looking-to-see  consider:how-far-can-it-go  consider:feature-discovery  mathematical-recreations 
february 2017 by Vaguery
[1701.08982] Leaf-reconstructibility of phylogenetic networks
An important problem in evolutionary biology is to reconstruct the evolutionary history of a set X of species. This history is often represented as a phylogenetic network, that is, a connected graph with leaves labelled by elements in X (for example, an evolutionary tree), which is usually also binary, i.e. all vertices have degree 1 or 3. A common approach used in phylogenetics to build a phylogenetic network on X involves constructing it from networks on subsets of X. Here we consider the question of which (unrooted) phylogenetic networks are leaf-reconstructible, i.e. which networks can be uniquely reconstructed from the set of networks obtained from it by deleting a single leaf (its X-deck). This problem is closely related to the (in)famous reconstruction conjecture in graph theory but, as we shall show, presents distinct challenges. We show that some large classes of phylogenetic networks are reconstructible from their X-deck. This includes phylogenetic trees, binary networks containing at least one non-trivial cut-edge, and binary level-4 networks (the level of a network measures how far it is from being a tree). We also show that for fixed k, almost all binary level-k phylogenetic networks are leaf-reconstructible. As an application of our results, we show that a level-3 network N can be reconstructed from its quarnets, that is, 4-leaved networks that are induced by N in a certain recursive fashion. Our results lead to several interesting open problems which we discuss, including the conjecture that all phylogenetic networks with at least five leaves are leaf-reconstructible.
cladistics  phylogenetics  combinatorics  algorithms  rather-interesting  constructibility  proof  nudge-targets  consider:looking-to-see  consider:representation 
february 2017 by Vaguery
[1612.02542] Minimum Rates of Approximate Sufficient Statistics
Given a sufficient statistic for a parametric family of distributions, one can estimate the parameter without access to the data itself. However, the memory or code size for storing the sufficient statistic may nonetheless still be prohibitive. Indeed, for n independent data samples drawn from a k-nomial distribution with d=k−1 degrees of freedom, the length of the code scales as dlogn+O(1). In many applications though, we may not have a useful notion of sufficient statistics (e.g., when the parametric family is not an exponential family) and also may not need to reconstruct the generating distribution exactly. By adopting a Shannon-theoretic approach in which we consider allow a small error in estimating the generating distribution, we construct various notions of {\em approximate sufficient statistics} and show that the code length can be reduced to d2logn+O(1). We also note that the locality assumption that is used to describe the notion of local approximate sufficient statistics when the parametric family is not an exponential family can be dispensed of. We consider errors measured according to the relative entropy and variational distance criteria. For the code construction parts, we leverage Rissanen's minimum description length principle, which yields a non-vanishing error measured using the relative entropy. For the converse parts, we use Clarke and Barron's asymptotic expansion for the relative entropy of a parametrized distribution and the corresponding mixture distribution. The limitation of this method is that only a weak converse for the variational distance can be shown. We develop new techniques to achieve vanishing errors and we also prove strong converses for all our statements. The latter means that even if the code is allowed to have a non-vanishing error, its length must still be at least d2logn.
statistics  information-theory  learning-from-data  proof  nudge-targets  consider:performance-measures 
february 2017 by Vaguery
[1701.00928] Counting Lyndon factors
In this paper, we determine the maximum number of distinct Lyndon factors that a word of length n can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length n on an alphabet of size σ, as well as the expected number of distinct Lyndon factors in such a word. The minimum number of distinct Lyndon factors in a word of length n is 1 and the minimum total number is n, with both bounds being achieved by xn where x is a letter. A more interesting question to ask is what is the minimum number of distinct Lyndon factors in a Lyndon word of length n? In this direction, it is known (Saari, 2014) that an optimal lower bound for the number of distinct Lyndon factors in a Lyndon word of length n is ⌈logϕ(n)+1⌉, where ϕ denotes the golden ratio (1+5‾√)/2. Moreover, this lower bound is attained by the so-called finite "Fibonacci Lyndon words", which are precisely the Lyndon factors of the well-known "infinite Fibonacci word" -- a special example of a "infinite Sturmian word". Saari (2014) conjectured that if w is Lyndon word of length n, n≠6, containing the least number of distinct Lyndon factors over all Lyndon words of the same length, then w is a Christoffel word (i.e., a Lyndon factor of an infinite Sturmian word). We give a counterexample to this conjecture. Furthermore, we generalise Saari's result on the number of distinct Lyndon factors of a Fibonacci Lyndon word by determining the number of distinct Lyndon factors of a given Christoffel word. We end with two open problems.
combinatorics  formal-languages  strings  proof  algorithms  rather-interesting  nudge-targets 
january 2017 by Vaguery
[1612.02717] Neighborhood reconstruction and cancellation of graphs
We connect two seemingly unrelated problems in graph theory.
Any graph G has an associated neighborhood multiset 𝒩(G)={N(x)∣x∈V(G)} whose elements are precisely the open vertex-neighborhoods of G. In general there exist non-isomorphic graphs G and H for which 𝒩(G)=𝒩(H). The neighborhood reconstruction problem asks the conditions under which G is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which 𝒩(G)=𝒩(H) implies G≅H. Such a graph is said to be neighborhood-reconstructible.
The cancellation problem for the direct product of graphs seeks the conditions under which G×K≅H×K implies G≅H. Lovasz proved that this is indeed the case if K is not bipartite. A second instance of the cancellation problem asks for conditions on G that assure G×K≅H×K implies G≅H for any bipartite graph K with E(K)≠∅. A graph G for which this is true is called a cancellation graph.
We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction.
graph-theory  proof  rather-interesting  inverse-problems  nudge-targets  consider:looking-to-see  consider:neighborhood-reconstruction 
january 2017 by Vaguery
[1606.01107] Packing Coloring of Undirected and Oriented Generalized Theta Graphs
The packing chromatic number χ ρ (G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1,..., V k, in such a way that every two distinct vertices in V i are at distance (resp. directed distance) greater than i in G for every i, 1 ≤ i ≤ k. The generalized theta graph Θ {\ell} 1,...,{\ell}p consists in two end-vertices joined by p ≥ 2 internally vertex-disjoint paths with respective lengths 1 ≤ {\ell} 1 ≤ . . . ≤ {\ell} p. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n 3 + 2}, where n 3 = |{i / 1 ≤ i ≤ p, {\ell} i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k ≥ 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.
graph-theory  combinatorics  feature-construction  proof  rather-interesting  nudge-targets  consider:representation  to-write-about 
december 2016 by Vaguery
[1605.07575] How can a clairvoyant particle escape the exclusion process?
We study a detection problem in the following setting: on the integer lattice, at time zero, place nodes on each site independently with probability ρ∈[0,1) and let them evolve as an exclusion process. At time zero, place a target at the origin. The target moves only at integer times, and can move to any site that is within distance R from its current position. Assume also that the target can predict the future movement of all nodes. We prove that, for R large enough (depending on the value of ρ) it is possible for the target to avoid detection forever with positive probability. The proof of this result uses two ingredients of independent interest. First we establish a renormalisation scheme that can be used to prove percolation for dependent oriented models under a certain decoupling condition. The second step of the proof is a space-time decoupling for the exclusion process.
planning  collective-intelligence  probability-theory  proof  consider:looking-to-see  nudge-targets  mathematical-recreations  to-write-about 
november 2016 by Vaguery
[1610.07908] A pumping lemma for non-cooperative self-assembly
We prove a result which strongly hints at the computational weakness of a model of tile assembly that has so far resisted many attempts of formal analysis or positive constructions. Specifically, we prove that, in Winfree's abstract Tile Assembly Model, when restricted to use only noncooperative bindings, any long enough path starting from the seed that can grow in all terminal assemblies is pumpable, meaning that this path can be extended into an infinite, ultimately periodic path. This result can be seen as a geometric generalization of the pumping lemma of finite state automata, and closes the question of what can be computed deterministically in this model. Moreover, this question has motivated the development of a new method called visible glues. We believe that this method can also be used to tackle other long-standing problems in computational geometry, in relation for instance with self-avoiding paths. Tile assembly (including non-cooperative tile assembly) was originally introduced by Winfree and Rothemund in STOC 2000 to understand how to program shapes. The non-cooperative variant, also known as temperature 1 tile assembly, is the model where tiles are allowed to bind as soon as they match on one side, whereas in cooperative tile assembly, some tiles need to match on several sides in order to bind. Previously, exactly one known result (SODA 2014) showed a restriction on the assemblies general non-cooperative self-assembly could achieve, without any implication on its computational expressiveness. With non-square tiles (like polyominos, SODA 2015), other recent works have shown that the model quickly becomes computationally powerful.
self-assembly  simulation  to-understand  very-long-papers  proof 
october 2016 by Vaguery
[1409.4545] A Note on Rectangle Covering with Congruent Disks
In this note we prove that, if Sn is the greatest area of a rectangle which can be covered with n unit disks, then 2≤Sn/n<33‾√/2, and these are the best constants; moreover, for Δ(n):=(33‾√/2)n−Sn, we have 0.727384<liminfΔ(n)/n‾√<2.121321 and 0.727384<limsupΔ(n)/n‾√<4.165064.
computational-geometry  optimization  plane-geometry  proof  nudge-targets  consider:looking-to-see  consider:heuristics 
august 2016 by Vaguery
[1605.06581] On the Rate of Convergence of the Power-of-Two-Choices to its Mean-Field Limit
This paper studies the rate of convergence of the power-of-two-choices, a celebrated randomized load balancing algorithm for many-server queueing systems, to its mean field limit. The convergence to the mean-field limit has been proved in the literature, but the rate of convergence remained to be an open problem. This paper establishes that the sequence of stationary distributions, indexed by M, the number of servers in the system, converges in mean-square to its mean-field limit with rate O((logM)3(loglogM)2M).
queueing-theory  proof  limits  something-familiar-about-the-result  nudge-targets  consider:looking-to-see 
may 2016 by Vaguery
[1504.07682] Shotgun assembly of labeled graphs
We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius r. Special instances of this problem include DNA shotgun assembly, neural network reconstruction, and assembling random jigsaw puzzles. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including random labelings of lattices, Erdos-Renyi random graphs, and the random jigsaw puzzle model. Many open problems and conjectures are provided.
probability-theory  combinatorics  graph-theory  algorithms  proof  nudge-targets  consider:rediscovery  consider:looking-to-see 
may 2016 by Vaguery
[1605.03043] Unique reconstruction threshold for random jigsaw puzzles
A random jigsaw puzzle is constructed by arranging n2 square pieces into an n×n grid and assigning to each edge of a piece one of q available colours uniformly at random, with the restriction that touching edges receive the same colour. We show that if q=o(n) then with high probability such a puzzle does not have a unique solution, while if q≥n1+ε for any constant ε>0 then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).
probability-theory  proof  combinatorics  graph-theory  bioinformatics  rather-interesting  nudge-targets  consider:looking-to-see 
may 2016 by Vaguery
[1605.01750] Some results on the spectral radii of uniform hypergraphs
Let A(G) be the adjacency tensor (hypermatrix) of uniform hypergraph G. The maximum modulus of the eigenvalues of A(G) is called the spectral radius of G. In this paper, the conjecture of Fan et al. in [5] related to compare the spectral radii of some three uniform hypergraphs is solved. Moreover, some eigenvalues properties of a kind of uniform hypergraphs are obtained.
hypergraphs  tensors  representation  algebra  graph-theory  nudge-targets  proof  combinatorics 
may 2016 by Vaguery
[1604.08439] A proof of the bunkbed conjecture for the complete graph at $p=frac{1}{2}$
The bunkbed of a graph G is the graph G×K2. It has been conjectured that in the independent bond percolation model, the probability for (u,0) to be connected with (v,0) is greater than the probability for (u,0) to be connected with (v,1), for any vertex u, v of G. In this article, we prove this conjecture for the complete graph in the case of the independent bond percolation of parameter p=1/2.
graph-theory  combinatorics  proof  algorithms  nudge-targets  consider:looking-to-see  consider:simulation  percolation 
may 2016 by Vaguery
[1504.07674] Matrix positivity preservers in fixed dimension. I
A classical theorem proved in 1942 by I.J. Schoenberg describes all real-valued functions that preserve positivity when applied entrywise to positive semidefinite matrices of arbitrary size; such functions are necessarily analytic with non-negative Taylor coefficients. Despite the great deal of interest generated by this theorem, a characterization of functions preserving positivity for matrices of fixed dimension is not known.
In this paper, we provide a complete description of polynomials of degree N that preserve positivity when applied entrywise to matrices of dimension N. This is the key step for us then to obtain negative lower bounds on the coefficients of analytic functions so that these functions preserve positivity in a prescribed dimension. The proof of the main technical inequality is representation theoretic, and employs the theory of Schur polynomials. Interpreted in the context of linear pencils of matrices, our main results provide a closed-form expression for the lowest critical value, revealing at the same time an unexpected spectral discontinuity phenomenon.
Tight linear matrix inequalities for Hadamard powers of matrices and a sharp asymptotic bound for the matrix-cube problem involving Hadamard powers are obtained as applications. Positivity preservers are also naturally interpreted as solutions of a variational inequality involving generalized Rayleigh quotients. This optimization approach leads to a novel description of the simultaneous kernels of Hadamard powers, and a family of stratifications of the cone of positive semidefinite matrices.
matrices  number-theory  constraint-satisfaction  algorithms  proof  nudge-targets  consider:looking-to-see 
may 2016 by Vaguery
[1604.08459] Noisy Optimization: Fast Convergence Rates with Comparison-Based Algorithms
Derivative Free Optimization is known to be an efficient and robust method to tackle the black-box optimization problem. When it comes to noisy functions, classical comparison-based algorithms are slower than gradient-based algorithms. For quadratic functions, Evolutionary Algorithms without large mutations have a simple regret at best O(1/N‾‾√) when N is the number of function evaluations, whereas stochastic gradient descent can reach (tightly) a simple regret in O(1/N). It has been conjectured that gradient approximation by finite differences (hence, not a comparison-based method) is necessary for reaching such a O(1/N). We answer this conjecture in the negative, providing a comparison-based algorithm as good as gradient methods, i.e. reaching O(1/N) - under the condition, however, that the noise is Gaussian. Experimental results confirm the O(1/N) simple regret, i.e., squared rate compared to many published results at O(1/N‾‾√).
optimization  error  statistics  bounds  proof  approximation  computational-complexity  nudge-targets  consider:selection 
may 2016 by Vaguery
[1602.05870] Applications of graph containers in the Boolean lattice
We apply the graph container method to prove a number of counting results for the Boolean lattice (n). In particular, we give a partial answer to a question of Sapozhenko estimating the number of t error correcting codes in (n), and we also give an upper bound on the number of transportation codes; then we provide an alternative proof of Kleitman's theorem on the number of antichains in (n) and give a two-coloured analogue; next we give an asymptotic formula for the number of (p,q)-tilted Sperner families in (n), and finally we prove a random version of Katona's t-intersection theorem. In each case, to apply the container method, we first prove corresponding supersaturation results. A number of open questions are also given.
hypergraphs  graph-theory  proof  nudge-targets  consider:representation  consider:rediscovery 
april 2016 by Vaguery
[1511.02334] A weak reduction of the Erd"os-Szekeres conjecture into a constraint unsatisfiability problem regarding certain multisets
We introduce the theory of div point sets, which aims to provide a framework to study the combinatoric nature of any set of points in general position on an Euclidean plane. We then show that proving the unsatisfiability of some first-order logic formulae concerning some sets of multisets of uniform cardinality over boolean variables would prove the Erd\"os-Szekeres conjecture, which states that for any set of 2^(n-2)+1 points in general position, there exists n points forming a convex polygon, where n is greater than or equal to 3.
computational-geometry  combinatorics  proof  rather-interesting  Erdos-again  nudge-targets  consider:looking-to-see 
april 2016 by Vaguery
[1311.3323] The opaque square
The problem of finding small sets that block every line passing through a unit square was first considered by Mazurkiewicz in 1916. We call such a set {\em opaque} or a {\em barrier} for the square. The shortest known barrier has length 2‾√+6√2=2.6389…. The current best lower bound for the length of a (not necessarily connected) barrier is 2, as established by Jones about 50 years ago. No better lower bound is known even if the barrier is restricted to lie in the square or in its close vicinity. Under a suitable locality assumption, we replace this lower bound by 2+10−12, which represents the first, albeit small, step in a long time toward finding the length of the shortest barrier. A sharper bound is obtained for interior barriers: the length of any interior barrier for the unit square is at least 2+10−5. Two of the key elements in our proofs are: (i) formulas established by Sylvester for the measure of all lines that meet two disjoint planar convex bodies, and (ii) a procedure for detecting lines that are witness to the invalidity of a short bogus barrier for the square.
computational-geometry  open-questions  proof  rather-interesting  nudge-targets  consider:looking-to-see  consider:rediscovery 
april 2016 by Vaguery
[1107.5102] Packing anchored rectangles
Let S be a set of n points in the unit square [0,1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.
computational-geometry  Winklerism  open-questions  optimization  proof  nudge-targets  consider:looking-to-see 
april 2016 by Vaguery
[1504.07883] An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
We give a O(n)-time algorithm for determining whether translations of a polyomino with n edges can tile the plane. The algorithm is also a O(n)-time algorithm for enumerating all such tilings that are also regular, and we prove that at most Θ(n) such tilings exist.
tiling  discrete-mathematics  classification  proof  algorithms  nudge-targets  consider:rediscovery 
april 2016 by Vaguery
[1507.02762] A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(nlog2n)-time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n18)-time algorithm of Keating and Vince and generalizes recent work by Brlek, Proven\c{c}al, F\'{e}dou, and the second author.
tiling  group-theory  symmetry  rather-interesting  proof  computational-geometry  nudge-targets  consider:rediscovery 
april 2016 by Vaguery
[1206.1803] Hidden Mobile Guards in Simple Polygons
We consider guarding classes of simple polygons using mobile guards (polygon edges and diagonals) under the constraint that no two guards may see each other. In contrast to most other art gallery problems, existence is the primary question: does a specific type of polygon admit some guard set? Types include simple polygons and the subclasses of orthogonal, monotone, and starshaped polygons. Additionally, guards may either exclude or include the endpoints (so-called open and closed guards). We provide a nearly complete set of answers to existence questions of open and closed edge, diagonal, and mobile guards in simple, orthogonal, monotone, and starshaped polygons, with some surprising results. For instance, every monotone or starshaped polygon can be guarded using hidden open mobile (edge or diagonal) guards, but not necessarily with hidden open edge or hidden open diagonal guards.
computational-geometry  constraint-satisfaction  hard-problems  proof  nudge-targets  consider:looking-to-see 
april 2016 by Vaguery
[1210.3877] Inapproximability of the Smallest Superpolyomino Problem
We consider the \emph{smallest superpolyomino problem}: given a set of colored polyominoes, find the smallest polyomino containing each input polyomino as a subshape. This problem is shown to be NP-hard, even when restricted to a set of polyominoes using a single common color. Moreover, for sets of polyominoes using two or more colors, the problem is shown to be NP-hard to approximate within a O(n1/3−ε)-factor for any ε>0.
computational-complexity  proof  algorithms  strings  decomposition-problems  inverse-problems  rather-interesting  nudge-targets  out-of-the-box 
april 2016 by Vaguery
[1512.06488] From Discrepancy to Majority
We show how to select an item with the majority color from n two-colored items, given access to the items only through an oracle that returns the discrepancy of subsets of k items. We use n/⌊k2⌋+O(k) queries, improving a previous method by De Marco and Kranakis that used n−k+k2/2 queries. We also prove a lower bound of n/(k−1)−O(n1/3) on the number of queries needed, improving a lower bound of ⌊n/k⌋ by De Marco and Kranakis.
algorithms  probability-theory  sampling  approximation  rather-interesting  nudge-targets  proof  consider:feature-discovery 
april 2016 by Vaguery
[0712.2094] Hinged Dissections Exist
We prove that any finite collection of polygons of equal area has a common hinged dissection. That is, for any such collection of polygons there exists a chain of polygons hinged at vertices that can be folded in the plane continuously without self-intersection to form any polygon in the collection. This result settles the open problem about the existence of hinged dissections between pairs of polygons that goes back implicitly to 1864 and has been studied extensively in the past ten years. Our result generalizes and indeed builds upon the result from 1814 that polygons have common dissections (without hinges). We also extend our common dissection result to edge-hinged dissections of solid 3D polyhedra that have a common (unhinged) dissection, as determined by Dehn's 1900 solution to Hilbert's Third Problem. Our proofs are constructive, giving explicit algorithms in all cases. For a constant number of planar polygons, both the number of pieces and running time required by our construction are pseudopolynomial. This bound is the best possible, even for unhinged dissections. Hinged dissections have possible applications to reconfigurable robotics, programmable matter, and nanomanufacturing.
dissections  mathematical-recreations  engineering-design  proof  existence-proof  nudge-targets  consider:looking-to-see 
april 2016 by Vaguery
[1603.00060] Anchored Rectangle and Square Packings
For points p1,…,pn in the unit square [0,1]2, an \emph{anchored rectangle packing} consists of interior-disjoint axis-aligned empty rectangles r1,…,rn⊆[0,1]2 such that point pi is a corner of the rectangle ri (that is, ri is \emph{anchored} at pi) for i=1,…,n. We show that for every set of n points in [0,1]2, there is an anchored rectangle packing of area at least 7/12−O(1/n), and for every n∈N, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored \emph{square} packing is always at least 5/32 and sometimes at most 7/27.
The above constructive lower bounds immediately yield constant-factor approximations, of 7/12−ε for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(nlogn) time. We prove that a simple greedy strategy achieves a 9/47-approximation for anchored square packings, and 1/3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in nO(1/ε) and exp(poly(log(n/ε))) time, respectively.
computational-geometry  packing-problems  algorithms  proof  existence-proof  consider:algorithm  nudge-targets 
april 2016 by Vaguery
[1402.5303] Diffuse Reflection Radius in a Simple Polygon
It is shown that every simple polygon in general position with n walls can be illuminated from a single point light source s after at most ⌊(n−2)/4⌋ diffuse reflections, and this bound is the best possible. A point s with this property can be computed in O(nlogn) time. It is also shown that the minimum number of diffuse reflections needed to illuminate a given simple polygon from a single point can be approximated up to an additive constant in polynomial time.
computational-geometry  plane-geometry  open-questions  proof  rather-interesting  planning  optimization  nudge-targets 
april 2016 by Vaguery
Sphere Packing Solved in Higher Dimensions | Quanta Magazine
The new results don’t have practical implications for error-correcting codes, since knowing that E8 and the Leech lattice were close to perfect had already been sufficient for all real-world applications. But the two proofs offer mathematicians both a sense of closure and a powerful new tool. A natural next question, Cohn said, is whether these methods can be adapted to show that E8 and the Leech lattice have “universal optimality.” This would mean that they provide not just the best sphere packings but also the lowest-energy ones, if, for example, the centers of the spheres are regarded as electrons repelling one another.
proof  mathematics  geometry  information-theory  Golay-codes  nudge-targets  consider:modular-forms 
march 2016 by Vaguery
[1603.01382] Reptilings and space-filling curves for acute triangles
An r-gentiling is a dissection of a shape into r≥2 parts which are all similar to the original shape. An r-reptiling is an r-gentiling of which all parts are mutually congruent. By applying gentilings recursively, together with a rule that defines an order on the parts, one may obtain an order in which to traverse all points within the original shape. We say such a traversal is a face-continuous space-filling curve if, at any level of recursion, the interior of the union of any set of consecutive parts is connected---that is, consecutive parts must always meet along an edge. Most famously, the isosceles right triangle admits a 2-reptiling, which forms the basis of the face-continuous Sierpinski space-filling curve; many other right triangles admit reptilings and gentilings that yield face-continuous space-filling curves as well. In this study we investigate what acute triangles admit non-trivial reptilings and gentilings, and whether these can form the basis for face-continuous space-filling curves. We derive several properties of reptilings and gentilings of acute (sometimes also obtuse) triangles, leading to the following conclusion: no face-continuous space-filling curve can be constructed on the basis of reptilings of acute triangles.
tiling  discrete-mathematics  combinatorics  proof  mathematical-recreations  rather-interesting  nudge-targets  consider:checking-to-see 
march 2016 by Vaguery
[1602.06372] Convex Polygons for Aperiodic Tiling
If all tiles in a tiling are congruent, the tiling is called monohedral. Tiling by convex polygons is called edge-to-edge if any two convex polygons are either disjoint or share one vertex or one entire edge in common. We find that a convex polygon that can generate an edge-to-edge monohedral tiling must be able to generate a periodic tiling.
tiling  proof  plane-geometry  rather-interesting  group-theory  nudge-targets  consider:exploring 
february 2016 by Vaguery
[1505.01005] Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture
Coffman and Sethi proposed a heuristic algorithm, called LD, for multi-processor scheduling, to minimize makespan over flowtime-optimal schedules. LD algorithm is a natural extension of a very well-known list scheduling algorithm, Longest Processing Time (LPT) list scheduling, to our bicriteria scheduling problem. Moreover, in 1976, Coffman and Sethi conjectured that LD algorithm has precisely the following worst-case performance bound: 54−34(4m−1), where m is the number of machines. In this paper, utilizing some recent work by the authors and Huang, from 2013, which exposed some very strong combinatorial properties of various presumed minimal counterexamples to the conjecture, we provide a proof of this conjecture. The problem and the LD algorithm have connections to other fundamental problems (such as the assembly line-balancing problem) and to other algorithms.
scheduling  planning  operations-research  heuristics  proof  nudge-targets  consider:looking-to-see 
february 2016 by Vaguery
[1312.2575] A Galois connection between classical and intuitionistic logics. I: Syntax
In a 1985 commentary to his collected works, Kolmogorov remarked that his 1932 paper "was written in hope that with time, the logic of solution of problems [i.e., intuitionistic logic] will become a permanent part of a [standard] course of logic. Creation of a unified logical apparatus dealing with objects of two types - propositions and problems - was intended." We construct such a formal system QHC, which is a conservative extension of both the intuitionistic predicate calculus QH and the classical predicate calculus QC.
The only new connectives ? and ! of QHC induce a Galois connection (i.e., a pair of adjoint functors) between the Lindenbaum algebras of QH and QC. Kolmogorov's double negation translation of propositions into problems extends to a retraction of QHC onto QH; whereas Goedel's provability translation of problems into modal propositions extends to a retraction of QHC onto its QC+(?!) fragment, identified with the modal logic QS4. The QH+(!?) fragment is an intuitionistic modal logic whose modality !? is a strict lax modality in the sense of Aczel - and thus resembles the squash/bracket operation in intuitionistic type theories.
logic  philosophy-of-science  mathematics  rather-interesting  proof  problem-solving  define-your-terms 
february 2016 by Vaguery
[1508.03476] A Proof of the Erd"os - Faber - Lov'asz Conjecture
In 1972, Erd\"{o}s - Faber - Lov\'{a}sz (EFL) conjectured that, if H is a linear hypergraph consisting of n edges of cardinality n, then it is possible to color the vertices with n colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erd\"{o}s and Frankl had given an equivalent version of the same for graphs: Let G=⋃ni=1Ai denote a graph with n complete graphs A1,A2, …,An, each having exactly n vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of G is n.
The clique degree dK(v) of a vertex v in G is given by dK(v)=|{Ai:v∈V(Ai),1≤i≤n}|. In this paper we give an algorithmic proof of the conjecture using the symmetric latin squares and clique degrees of the vertices of G.
hypergraphs  graph-theory  combinatorics  proof  nudge-targets  consider:rediscovery  consider:representation 
december 2015 by Vaguery
[1412.1184] $G$-strongly positive scripts and critical configurations of chip firing games on digraphs
We show a collection of scripts, called G-strongly positive scripts, which is used to recognize critical configurations of a chip firing game (CFG) on a multi-digraph with a global sink. To decrease the time of the process of recognition caused by the stabilization we present an algorithm to find the minimum G-strongly positive script. From that we prove the non-stability of configurations obtained from a critical configuration by firing inversely any non-empty multi-subset of vertices. This result is a generalization of a very recent one by Aval \emph{} which is applied for CFG on undirected graphs. Last, we give a combinatorial proof for the duality between critical and super-stable configurations.
graph-theory  feature-construction  rather-interesting  algorithms  combinatorics  proof  nudge-targets  consider:looking-to-see 
november 2015 by Vaguery
[1402.5643] Packing k-partite k-uniform hypergraphs
Let G and H be k-graphs (k-uniform hypergraphs); then a perfect H-packing in G is a collection of vertex-disjoint copies of H in G which together cover every vertex of G. For any fixed H let δ(H,n) be the minimum δ such that any k-graph G on n vertices with minimum codegree δ(G)≥δ contains a perfect H-packing. The problem of determining δ(H,n) has been widely studied for graphs (i.e. 2-graphs), but little is known for k≥3. Here we determine the asymptotic value of δ(H,n) for all complete k-partite k-graphs H, as well as a wide class of other k-partite k-graphs. In particular, these results provide an asymptotic solution to a question of R\"odl and Ruci\'nski on the value of δ(H,n) when H is a loose cycle. We also determine asymptotically the codegree threshold needed to guarantee an H-packing covering all but a constant number of vertices of G for any complete k-partite k-graph H.
hypergraphs  graph-theory  combinatorics  proof  nudge-targets  consider:algorithms  consider:representation 
november 2015 by Vaguery
[1411.8002] The Page-R{'e}nyi parking process
In the Page parking (or packing) model on a discrete interval (also known as the discrete R{\'e}nyi packing problem or the unfriendly seating problem), cars of length two successively park uniformly at random on pairs of adjacent places, until only isolated places remain. We give a probabilistic proof of the (known) fact that the proportion of the interval covered by cars goes to 1-exp(-2) , when the length of the interval goes to infinity. We obtain some new consequences, and also study a version of this process defined on the infinite line.
discrete-mathematics  simulation  probability-theory  proof  rather-interesting  simple-models  nudge-targets  consider:looking-to-see  consider:policies 
november 2015 by Vaguery
[1511.00422] Abelian logic gates
An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a "toppler", which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from N^k to N^l that is the sum of a linear function and a periodic function can be expressed in terms of floors of quotients by integers, and addition.
computer-science  rather-interesting  visualization  wow-that-got-odd-real-quick  Peter-Winkler  nudge-targets  consider:looking-to-see  group-theory  proof 
november 2015 by Vaguery
[1509.02090] Fair partitioning by straight lines
A pizza is a pair of planar convex bodies A⊆B,where B represents the dough and A the topping of the pizza. A partition of a pizza by straight lines is a succession of double operations:a cut by a full straight line, followed by a Euclidean move of one of theresulting pieces; then the procedure is repeated.The final partition is said to be fair if each resulting slice has the same amount of A and the same amount of B.This note proves that, given an integer n≥2, there exists a fair partition by straight lines of any pizza (A,B) into n parts if and onlyif n is even.The proof uses the following result:For any planar convex bodies A,B with A⊆B, and anyα∈]0,12[, there exists an α-section of A which is aβ-section of B for some β≥α. (An α-section of A is a straight line cutting A into two parts, one of which has area α|A|.)The question remains open if the word "planar" is dropped.
partitioning  pizza-cutting  proof  game-theory  geometry  nudge-targets  mechanism-design 
november 2015 by Vaguery
[1505.00343] A first-order logic for string diagrams
Equational reasoning with string diagrams provides an intuitive means of proving equations between morphisms in a symmetric monoidal category. This can be extended to proofs of infinite families of equations using a simple graphical syntax called !-box notation. While this does greatly increase the proving power of string diagrams, previous attempts to go beyond equational reasoning have been largely ad hoc, owing to the lack of a suitable logical framework for diagrammatic proofs involving !-boxes. In this paper, we extend equational reasoning with !-boxes to a fully-fledged first order logic called with conjunction, implication, and universal quantification over !-boxes. This logic, called !L, is then rich enough to properly formalise an induction principle for !-boxes. We then build a standard model for !L and give an example proof of a theorem for non-commutative bialgebras using !L, which is unobtainable by equational reasoning alone.
formalization  visualization  representation  mathematics  proof  rather-interesting  category-theory  nudge-targets  logic-programming  consider:representation 
november 2015 by Vaguery
[1507.06165] Fast Almost-Surely Terminating Byzantine Agreement
We present a new asynchronous Byzantine agreement protocol with almost-sure termination, i.e. all correct processes terminate with probability one. In a system with n=3t+1 processes, where t is the tolerated number of faulty ones, our protocol has linear expected running time, improving on the time complexity of the state-of-the-art protocol of Abraham, Dolev, and Halpern {\cite{abraham2008almost}} by a factor of O(n). When n>(3+ε)t with any ε>0, our protocol completes with expected running time O(1/ε), improving the state-of-the-art result of Feldman and Micali {\cite{feldman1988optimal}} (with constant expected running time when n>4t).
distributed-processing  computer-science  proof  rather-interesting  mechanism-design  algorithms  collective-behavior  nudge-targets  consider:looking-to-see  consider:performance-measures 
november 2015 by Vaguery
[1409.0250] Coins of Three Different Weights
We discuss several coin-weighing problems in which coins are known to be of three different weights and only a balance scale can be used. We start with the task of sorting coins when the pans of the scale can fit only one coin. We prove that the optimal number of weighings for n coins is ⌈3n/2⌉−2. When the pans have an unlimited capacity, we can sort the coins in n+1 weighings. We also discuss variations of this problem, when there is exactly one coin of the middle weight.
mathematical-recreations  algorithms  proof  logic-programming  nudge-targets  optimization  consider:looking-to-see 
november 2015 by Vaguery
[1305.4305] Cookie Monster Devours Naccis
In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars.
The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars.
We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.
combinatorics  proof  mathematical-recreations  delightful  planning  optimization  algorithms  nudge-targets  consider:rediscovery 
november 2015 by Vaguery
[1310.3510] Fission of Halving Edges Graphs
In this paper we discuss an operation on halving edges graph that we call fission. Fission replaces each point in a given configuration with a small cluster of k points. The operation interacts nicely with halving edges, so we examine its properties in detail.
mathematical-recreations  computational-geometry  proof  nudge-targets  consider:looking-to-see  plane-geometry 
november 2015 by Vaguery
[1504.06480] Wide enough Latin rectangles are perfects
Given two integers m and n with m≤n, a Latin rectangle of size m×n is a bi-dimensional array with m rows and n columns filled with symbols from an alphabet with n symbols, such that each row contains a permutation of the alphabet and each column contains no repeated symbols.
Two rows a and b of a Latin rectangle R define a permutation Ra,b assigning the symbol y to the symbol x if they are in the same column, x is in row a and y is in row b. A Latin rectangle R is perfect is the permutation Ra,b is cyclic, for each pair of rows a and b.
We prove that for each integer m and each large enough odd integer n there is a perfect Latin rectangle R of size m×n. It is a partial (asymptotic) answer to a well-known conjecture which says that the same property holds for each odd integer m≤n.
combinatorics  enumeration  proof  number-theory  permutations  nudge-targets  consider:looking-to-see 
november 2015 by Vaguery
[1507.06070] The Cerny conjecture and 1-contracting automata
A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. \v{C}ern\'y conjectured in 1964 that a synchronizing automaton with n states has a synchronizing word of length at most (n−1)2. We introduce the notion of aperiodically 1−contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the \v{C}ern\'y conjecture holds for aperiodically 1−contracting automata. As a special case, we prove some results for circular automata.
automata  combinatorics  classification  feature-construction  proof  nudge-targets  consider:feature-discovery 
october 2015 by Vaguery
[1503.03743] A result similar to Lagrange's theorem
Generalized octagonal numbers are those p8(x)=x(3x−2) with x∈ℤ. In this paper we mainly show that every positive integer can be written as the sum of four generalized octagonal numbers one of which is odd. This result is similar to Lagrange's theorem on sums of four squares. Moreover, for 35 triples (b,c,d) with 1≤b≤c≤d (including (2,3,4) and (2,4,8)), we prove that any nonnegative integer can be exprssed as p8(w)+bp8(x)+cp8(y)+dp8(z) with w,x,y,z∈ℤ. We also pose several conjectures for further research.
number-theory  pattern-discovery  proof  open-questions  nudge-targets 
september 2015 by Vaguery
« earlier      
per page:    204080120160

related tags

3d  a-wee-bit-esoteric-as-presented  abstraction  agent-based  algebra  algorithms  amusing  an-example-or-two-would-be-nice  analytical-expressions  approximation  arguments  art-gallery-problems  artificial-intelligence  automata  benchmarking  bin-packing  bioinformatics  boolean-networks  Booleanism  bounds  bounds-problems  cake-cutting  can't-wait-to-understand-it  category-theory  cellular-automata  chip-firing  cladistics  classification  coevolution  collaboration  Collatz  collective-behavior  collective-intelligence  coloring  combinatorics  communication  communities-of-practice  compass-and-straightedge  complexology  compressed-sensing  computational-complexity  computational-geometry  computational-methods  computer-science  concurrency  conjecture  consider:algorithm  consider:algorithms  consider:approximation  consider:checking-to-see  consider:classification  consider:classifiers  consider:classifiers-of-sets  consider:doing-not-thinking  consider:duh  consider:engineering-design  consider:exemplar-search  consider:exploring  consider:feature-discovery  consider:find-the-flows  consider:hardest-problems  consider:heuristics  consider:how-far-can-it-go  consider:how-to-handle-constraint  consider:identifier  consider:irregular-lattices  consider:just-I-don't-even-know  consider:looking-to-see  consider:modular-forms  consider:neighborhood-reconstruction  consider:open-questions  consider:other-shapes  consider:performance-measures  consider:policies  consider:reaction-diffusion  consider:rederivation  consider:rediscovery  consider:representation  consider:robustness  consider:rule-extraction  consider:rule-mining  consider:selection  consider:simulation  consider:Spector-proof-approach  consider:strategies  consider:strategies-for-finding  consider:strategy  consider:stress-testing  consider:Winkler-move  constraint-handling  constraint-satisfaction  constructibility  construction  continuous-systems  convex-hull  counting  counting-problems  coupled-oscillators  crowdsourcing  cryptography  databases  decidability  decomposition-problems  define-your-terms  delightful  derived-features  design  design-automation  design-problems  design-theory  development  diffyQ  discovery  discrete-mathematics  dissections  distributed-processing  DNA-computing  dynamic-coloring  dynamical-systems  edit-distance  emergent-design  engineering-design  engineering-philosophy  enumeration  enumeration-proof  Erdos-again  Erdös  error  existence-proof  existence-proofs  experimental-design  feature-construction  feature-extraction  for-nic  formal-languages  formalization  fractals  frontiers-of-summary-statistics  game-theory  generalization  genetic-programming-target  genetic-programming-would-be-good-about-now  geometry  Golay-codes  granular-materials  graph-coloring  graph-layout  graph-minors  graph-theory  group-theory  Gödel  hard-problems  have-written-about  heuristics  history  history-of-science  horse-races  hunting-for-examples  hypergraphs  image-processing  impossibility-proof  incompleteness  inference  information-architecture  information-theory  interesting  inverse-problems  is-it-me-or-do-people-writing-about-hypergraphs-not-understand-what-they-actually-represent?  Kauffmania  kinematics  knot-theory  knowledge-management  learning-by-doing  learning-from-data  limits  logic  logic-programming  looking-to-see  lovely  low-hanging-fruit  matchings  mathematical-recreations  mathematics  matrices  mechanism-design  membrane-computing  model-discovery  models  multiobjective-optimization  nanotechnology  network-theory  nice-little-system  No-Free-Lunch  nonlinear-dynamics  not-the-same-thing  now-make-an-algorithm  Nudge  nudge-targets  number-theory  numerical-methods  ontology  open-questions  operations-research  optimization  origami  out-of-the-box  packing  packing-problems  partitioning  pattern-avoidance  pattern-discovery  percolation  permutations  Peter-Winkler  philosophy  philosophy-of-engineering  philosophy-of-science  phylogenetics  pizza-cutting  planar-mechanisms  plane-geometry  planning  polygons  polyhedra  primality  privacy  probability-theory  problem-solving  programming-language  proof  prove-they-exist-but-don't-show-any?  purdy-pitchers  puzzles  query-construction  queueing-theory  random-matrices  random-processes  random-walks  rather-interesting  refactoring  reformulation  repository  representation  ReQ  research  review  rewriting-systems  rigidity  robotics  routing  sampling  satisfiability  scheduling  search  self-assembly  self-organization  sensors  set-theory  sign-patterns  simple-models  simulation  small-bites  something-familiar-about-the-result  something-paradigmatic-goes-here  something-to-think-about  special-cases  stamp-collecting  state-machines  statistics  strategy  strings  Sudoku  symbolic-regression-target  symmetry  systems-theory  tensors  testing  the-metaphor-breaks  theoretical-biology  thermodynamics  tiling  to-read  to-simulate  to-understand  to-write-about  topology  toy-problems  traveling-salesman  unconventional-representation-schemes  undecidability  universality  user-generated-content  verification  very-long-papers  via:twitter  visualization  well-then  winkler-project  Winklerism  would-be-interesting  wow-that-got-odd-real-quick  π-calculus 

Copy this bookmark: