[1410.0592] Inductive Rotation Tilings
A new method for constructing aperiodic tilings is presented. The method is illustrated by constructing a particular tiling and its hull. The properties of this tiling and the hull are studied. In particular it is shown that these tilings have a substitution rule, that they are nonperiodic, aperiodic, limitperiodic and pure point diffractive.
tiling  aperiodic-tiling  rather-interesting  to-simulate  to-write-about  consider:rewriting-systems
11 hours ago by Vaguery
[0704.2521] Substitution tilings with statistical circular symmetry
Two new series of substitution tilings are introduced in which the tiles appear in infinitely many orientations. It is shown that several properties of the well-known pinwheel tiling do also hold for these new examples, and, in fact, for all substitution tilings showing tiles in infinitely many orientations.
tiling  aperiodic-tiling  rather-interesting  rewriting-systems  to-simulate  to-write-about  consider:robustness  consider:approximation
12 hours ago by Vaguery
[1903.05005] $D$-Magic and Antimagic Labelings of Hypercubes
For a set of distances D, a graph G of order n is said to be D−magic if there exists a bijection f:V→{1,2,…,n} and a constant k such that for any vertex x, ∑y∈ND(x)f(y)=k, where ND(x)={y|d(y,x)=j,j∈D}.
In this paper we shall find sets of distances Ds, such that the hypercube is D−magic. We shall utilise well-known properties of (bipartite) distance-regular graphs to construct the D−magic labelings.
combinatorics  magic-squares  generalization  rather-interesting  to-write-about  to-simulate  to-visualize  graph-theory  number-theory  consider:planar-graphs  consider:hypergraphs
2 days ago by Vaguery
[1710.02196] Porcupine Neural Networks: (Almost) All Local Optima are Global
Neural networks have been used prominently in several machine learning and statistics applications. In general, the underlying optimization of neural networks is non-convex which makes their performance analysis challenging. In this paper, we take a novel approach to this problem by asking whether one can constrain neural network weights to make its optimization landscape have good theoretical properties while at the same time, be a good approximation for the unconstrained one. For two-layer neural networks, we provide affirmative answers to these questions by introducing Porcupine Neural Networks (PNNs) whose weight vectors are constrained to lie over a finite set of lines. We show that most local optima of PNN optimizations are global while we have a characterization of regions where bad local optimizers may exist. Moreover, our theoretical and empirical results suggest that an unconstrained neural network can be approximated using a polynomially-large PNN.
neural-networks  machine-learning  constraint-satisfaction  multiobjective-optimization  rather-interesting  diversity  to-write-about  to-simulate  consider:feature-discovery  consider:packing-order
3 days ago by Vaguery
3 days ago by Vaguery
[1603.04210] The Runaway Rectangle Escape Problem
Motivated by the applications of routing in PCB buses, the Rectangle Escape Problem was recently introduced and studied. In this problem, we are given a set of rectangles  in a rectangular region R, and we would like to extend these rectangles to one of the four sides of R. Define the density of a point p in R as the number of extended rectangles that contain p. The question is then to find an extension with the smallest maximum density.
We consider the problem of maximizing the number of rectangles that can be extended when the maximum density allowed is at most d. It is known that this problem is polynomially solvable for d=1, and NP-hard for any d≥2. We consider approximation and exact algorithms for fixed values of d. We also show that a very special case of this problem, when all the rectangles are unit squares from a grid, continues to be NP-hard for d=2.
computational-geometry  operations-research  planning  rather-interesting  constraint-satisfaction  optimization  to-understand  to-simulate  to-write-about
5 days ago by Vaguery
[1401.3668] The existence and abundance of ghost ancestors in biparental populations
In a randomly-mating biparental population of size N there are, with high probability, individuals who are genealogical ancestors of every extant individual within approximately log2(N) generations into the past. We use this result of J. Chang to prove a curious corollary under standard models of recombination: there exist, with high probability, individuals within a constant multiple of log2(N) generations into the past who are simultaneously (i) genealogical ancestors of {\em each} of the individuals at the present, and (ii) genetic ancestors to {\em none} of the individuals at the present. Such ancestral individuals - ancestors of everyone today that left no genetic trace -- represent `ghost' ancestors in a strong sense. In this short note, we use simple analytical argument and simulations to estimate how many such individuals exist in finite Wright-Fisher populations.
theoretical-biology  genetics  rather-interesting  probability-theory  to-write-about  to-simulate  consider:genetic-programming  consider:lee's-lab
7 days ago by Vaguery
[math/0402212] Criticality for the Gehring link problem
In 1974, Gehring posed the problem of minimizing the length of two linked curves separated by unit distance. This constraint can be viewed as a measure of thickness for links, and the ratio of length over thickness as the ropelength. In this paper we refine Gehring's problem to deal with links in a fixed link-homotopy class: we prove ropelength minimizers exist and introduce a theory of ropelength criticality.
Our balance criterion is a set of necessary and sufficient conditions for criticality, based on a strengthened, infinite-dimensional version of the Kuhn--Tucker theorem. We use this to prove that every critical link is C^1 with finite total curvature. The balance criterion also allows us to explicitly describe critical configurations (and presumed minimizers) for many links including the Borromean rings. We also exhibit a surprising critical configuration for two clasped ropes: near their tips the curvature is unbounded and a small gap appears between the two components. These examples reveal the depth and richness hidden in Gehring's problem and our natural extension.
rather-interesting  knot-theory  optimization  numerical-methods  engineering-design  performance-measure  to-write-about  to-simulate  consider:constraint-satisfaction  consider:feature-discovery
7 days ago by Vaguery
[math/0609360] Minimal Polynomials for the Coordinates of the Harborth Graph
The Harborth graph is the smallest known example of a 4-regular planar unit-distance graph. In this paper we give an analytical description of the coordinates of its vertices for a particular embedding in the Euclidean plane. More precisely, we show, how to calculate the minimal polynomials of the coordinates of its vertices (with the help of a computer algebra system), and list those. Furthermore some algebraic properties of these polynomials, and consequences to the structure of the Harborth graph are determined.
graph-theory  numerical-methods  rather-interesting  showing-your-work  symbolic-math  looking-to-see  to-write-about  to-simulate  matchstick-graphs
8 days ago by Vaguery
[1401.4375] Fast regocnition of planar non unit distance graphs
We study criteria attesting that a given graph can not be embedded in the plane so that neighboring vertices are at unit distance apart and the straight line edges do not cross.
graph-theory  matchstick-graphs  rather-interesting  algorithms  heuristics  computational-complexity  to-understand  to-write-about  to-simulate
8 days ago by Vaguery
[1902.00966] 4-regular planar unit triangle graphs without additional triangles
In this article we proof the existence of 4-regular planar unit-distance graphs consisting only of unit triangles without additional triangles. It is shown that the smallest number of unit triangles is ≤6422.
graph-theory  matchstick-graphs  plane-geometry  constraint-satisfaction  rather-interesting  butterfly-collecting  to-simulate  to-write-about  consider:performance-measures  consider:looking-to-see
8 days ago by Vaguery
Home - mikematics
On this website I present some of my work, thoughts and ideas on selected topics in mathematics. These range from conjectures over abstract ideas to rigorous proofs. My main fields of research are number theory and graph theory. If a problem has grabbed me, I worked on it over many years. My favorite topics are the 3x + 1 problem and regular matchstick graphs.

In the hope to enrich the mathematical world a little bit, enjoy reading and exploring.
graph-theory  mathematical-recreations  matchstick-graphs  constraint-satisfaction  rather-interesting  to-write-about  see-preprints  see-software
8 days ago by Vaguery
Cytoscape.js
Graph theory (network) library for visualisation and analysis
graph-theory  graph-layout  visualization  javascript  library  via:arthegall  to-use  to-write-about
9 days ago by Vaguery
[1903.04304] A 3-regular matchstick graph of girth 5 consisting of 54 vertices
In 2010 it was proved that a 3-regular matchstick graph of girth 5 must consist at least of 30 vertices. The smallest known example consisted of 180 vertices. In this article we construct an example consisting of 54 vertices and prove its geometrical correctness.
combinatorics  constraint-satisfaction  butterfly-collecting  rather-interesting  graph-theory  plane-geometry  to-write-about  to-simulate  consider:looking-to-see  consider:random-sampling  consider:generators
9 days ago by Vaguery
[1809.08490] On 3-Inflatable Permutations
Call a permutation k-inflatable if it can be "blown up" into a convergent sequence of permutations by a uniform inflation construction, such that this sequence is symmetric with respect to densities of induced subpermutations of length k. We study properties of 3-inflatable permutations, finding a general formula for limit densities of pattern permutations in the uniform inflation of a given permutation. We also characterize and find examples of 3-inflatable permutations of various lengths, including the shortest examples with length 17.
permutations  strings  rather-interesting  mathematical-recreations  dynamical-systems  formal-languages  constraint-satisfaction  to-write-about  to-simulate
9 days ago by Vaguery
[1708.01559] Spherical Geometry and the Least Symmetric Triangle
We study the problem of determining the least symmetric triangle, which arises both from pure geometry and from the study of molecular chirality in chemistry. Using the correspondence between planar n-gons and points in the Grassmannian of 2-planes in real n-space introduced by Hausmann and Knutson, this corresponds to finding the point in the fundamental domain of the hyperoctahedral group action on the Grassmannian which is furthest from the boundary, which we compute exactly. We also determine the least symmetric obtuse and acute triangles. These calculations provide prototypes for computations on polygon and shape spaces.
symmetry  optimization  rather-interesting  define-your-terms  performance-measure  to-write-about  to-emulate  to-simulate  consider:looking-to-see  consider:robustness  consider:stamp-collecting  geometry  plane-geometry
9 days ago by Vaguery
[1301.6807] Modified Stern-Brocot Sequences
We present the classical Stern-Brocot tree and provide a new proof of the fact that every rational number between 0 and 1 appears in the tree. We then generalize theStern-Brocot tree to allow for arbitrary choice of starting terms, and prove that in all cases the tree maintains the property that every rational number between the two starting terms appears exactly once.
number-theory  continued-fractions  dynamical-systems  rather-interesting  visualization  to-write-about
10 days ago by Vaguery
[1706.04939] Online Strip Packing with Polynomial Migration
We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1+(ϵ) for any ϵ>0 and amortized migration factor polynomial in 1/ϵ. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.
operations-research  bin-packing  strip-packing  optimization  algorithms  heuristics  to-simulate  to-write-about  horse-races  computational-complexity  consider:genetic-programming
10 days ago by Vaguery
[1701.07396] LAREX - A semi-automatic open-source Tool for Layout Analysis and Region Extraction on Early Printed Books
A semi-automatic open-source tool for layout analysis on early printed books is presented. LAREX uses a rule based connected components approach which is very fast, easily comprehensible for the user and allows an intuitive manual correction if necessary. The PageXML format is used to support integration into existing OCR workflows. Evaluations showed that LAREX provides an efficient and flexible way to segment pages of early printed books.
OCR  digitization  machine-learning  algorithms  image-processing  image-segmentation  digital-humanities  to-understand  to-write-about  to-simulate
10 days ago by Vaguery
[0810.3179] The Enlightened Game of Life
We investigate a special class of cellular automata (CA) evolving in a environment filled by an electromagnetic wave. The rules of the Conway's Game of Life are modified to account for the ability to retrieve life-sustenance from the field energy. Light-induced self-structuring and self-healing abilities and various dynamic phases are displayed by the CA. Photo-driven genetic selection and the nonlinear feedback of the CA on the electromagnetic field are included in the model, and there are evidences of self-organized light-localization processes. The evolution of the electromagnetic field is based on the Finite Difference Time Domain (FDTD) approach. Applications are envisaged in evolutionary biology, artificial life, DNA replication, swarming, optical tweezing and field-driven soft-matter.
cellular-automata  mathematical-diffraction  rather-odd  rather-interesting  artificial-life  to-understand  to-write-about  to-amplify
10 days ago by Vaguery

Copy this bookmark:

description:

tags: