[1712.08373] Notes on complexity of packing coloring

9 weeks ago by Vaguery

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
φ: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.

9 weeks ago by Vaguery

[1709.06217] Deterministic meeting of sniffing agents in the plane

10 weeks ago by Vaguery

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

february 2018 by Vaguery

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

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[1710.02741] A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[1605.06848] Nonnegative Matrix Factorization Requires Irrationality

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[1710.00386] Orthogonal Terrain Guarding is NP-complete

october 2017 by Vaguery

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

october 2017 by Vaguery

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
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.

october 2017 by Vaguery

[1502.04644] Beyond the Runs Theorem

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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

may 2017 by Vaguery

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

april 2017 by Vaguery

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
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").

april 2017 by Vaguery

[1701.05475] Irrational Guards are Sometimes Needed

april 2017 by Vaguery

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
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.

april 2017 by Vaguery

[1605.03546] ARRIVAL: A zero-player graph game in NP $cap$ coNP

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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

april 2017 by Vaguery

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
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.

april 2017 by Vaguery

[1507.02355] The Shadows of a Cycle Cannot All Be Paths

april 2017 by Vaguery

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
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).

april 2017 by Vaguery

[1307.5666] ErdH{o}s - Szekeres Theorem for Lines

april 2017 by Vaguery

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

april 2017 by Vaguery

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
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.

april 2017 by Vaguery

[1503.00566] $N$-Division Points of Hypocycloids

april 2017 by Vaguery

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"

march 2017 by Vaguery

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

march 2017 by Vaguery

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

march 2017 by Vaguery

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

march 2017 by Vaguery

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

march 2017 by Vaguery

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

february 2017 by Vaguery

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

february 2017 by Vaguery

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

february 2017 by Vaguery

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

january 2017 by Vaguery

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

january 2017 by Vaguery

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
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.

january 2017 by Vaguery

[1606.01107] Packing Coloring of Undirected and Oriented Generalized Theta Graphs

december 2016 by Vaguery

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?

november 2016 by Vaguery

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

october 2016 by Vaguery

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

august 2016 by Vaguery

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

may 2016 by Vaguery

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

may 2016 by Vaguery

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

may 2016 by Vaguery

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

may 2016 by Vaguery

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}$

may 2016 by Vaguery

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

may 2016 by Vaguery

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
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.

may 2016 by Vaguery

[1604.08459] Noisy Optimization: Fast Convergence Rates with Comparison-Based Algorithms

may 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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
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.

april 2016 by Vaguery

[1402.5303] Diffuse Reflection Radius in a Simple Polygon

april 2016 by Vaguery

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

march 2016 by Vaguery

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

march 2016 by Vaguery

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

february 2016 by Vaguery

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

february 2016 by Vaguery

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

february 2016 by Vaguery

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
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.

february 2016 by Vaguery

[1508.03476] A Proof of the Erd"os - Faber - Lov'asz Conjecture

december 2015 by Vaguery

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
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.

december 2015 by Vaguery

[1412.1184] $G$-strongly positive scripts and critical configurations of chip firing games on digraphs

november 2015 by Vaguery

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{et.al} 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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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
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.

november 2015 by Vaguery

[1310.3510] Fission of Halving Edges Graphs

november 2015 by Vaguery

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

november 2015 by Vaguery

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
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.

november 2015 by Vaguery

[1507.06070] The Cerny conjecture and 1-contracting automata

october 2015 by Vaguery

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

september 2015 by Vaguery

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

**related tags**

Copy this bookmark: