<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (Vaguery)</title>
    <link>https://pinboard.in/u:Vaguery/public/</link>
    <description>recent bookmarks from Vaguery</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2604.12392"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2403.04777"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1606.02982"/>
	<rdf:li rdf:resource="https://divisbyzero.com/2022/01/27/preorders-and-finite-topological-spaces/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1810.02241"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1805.03863"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2107.10897"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1802.03482"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1606.09596"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1902.10752"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1708.04773"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1904.04791"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1907.00272"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1905.13216"/>
	<rdf:li rdf:resource="https://dmtcs.episciences.org/2293"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/0810.5750"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/abstract/document/5763326"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1810.07800"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1805.04055"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1504.08259"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1611.01479"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1709.05314"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1708.05255"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1603.08269"/>
	<rdf:li rdf:resource="http://search.arxiv.org:8081/paper.jsp?r=1501.02502&amp;qid=1491475924245ler_nCnN_397128995&amp;qs=%22magic+square%22&amp;byDate=1"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1108.5574"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1109.4994"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1702.00146"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1606.02907"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1504.07883"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.4429"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1603.07737"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1511.00243"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.04538"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1603.07215"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1603.01382"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1602.08084"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1411.8002"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1510.01671"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02609"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1405.6893"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1204.5224"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1405.3146"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1504.04498"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1501.03549"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1402.2818"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1411.7355"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.0193"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1212.5951"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.6346"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1411.6672"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1009.5912"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1410.3096"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1212.1740"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.1364"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.1166"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1210.7320"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0812.4170"/>
	<rdf:li rdf:resource="http://en.wikipedia.org/wiki/Minterm"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1203.1900"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1203.1644"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1107.0056"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0911.3482"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1109.0807"/>
	<rdf:li rdf:resource="http://www.multimagie.com/English/Enigmas.htm"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1008.2555"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1005.0103"/>
	<rdf:li rdf:resource="http://mindsports.nl/index.php/side-dishes/50-china-labyrinth?5ddadc0c884344"/>
	<rdf:li rdf:resource="http://www.recmath.com/PolyPages/"/>
	<rdf:li rdf:resource="http://denseoutliers.blogspot.com/"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2604.12392">
    <title>[2604.12392] Enumerations and Bijections for Stanley Polyominoes</title>
    <dc:date>2026-05-24T16:19:14+00:00</dc:date>
    <link>https://arxiv.org/abs/2604.12392</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Stanley polyominoes are a subclass of parallelogram polyominoes in which each row begins strictly to the right of the beginning of the previous row and ends strictly to the right of the end of the previous row. In this paper, we derive generating functions for Stanley polyominoes based on the numbers of columns and rows, area, semiperimeter, and numbers of interior points and edges. We also establish combinatorial connections through bijections with other combinatorial structures such as Dyck paths, skew Ferrer diagrams, and peakless Motzkin paths. As a byproduct, we answer the open question of finding a bijection between parallelogram polyominoes of area n and coin fountains with n coins in the even-numbered rows and n−k coins in the odd-numbered rows.
]]></description>
<dc:subject>combinatorics enumeration polyominoes counting discrete-mathematics Catalan-numbers representation rather-interesting</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:e41074f25cbc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:polyominoes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:counting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Catalan-numbers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2403.04777">
    <title>[2403.04777] Specifying and Verifying the Convergence Stairs of the Collatz Program</title>
    <dc:date>2025-07-25T14:51:38+00:00</dc:date>
    <link>https://arxiv.org/abs/2403.04777</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper presents an algorithmic method that, given a positive integer j, generates the j-th convergence stair containing all natural numbers from where the Collatz conjecture holds by exactly j applications of the Collatz function. To this end, we present a novel formulation of the Collatz conjecture as a concurrent program, and provide the general case specification of the j-th convergence stair for any j>0. The proposed specifications provide a layered and linearized orientation of Collatz numbers organized in an infinite set of infinite binary trees. To the best of our knowledge, this is the first time that such a general specification is provided, which can have significant applications in analyzing and testing the behaviors of complex non-linear systems. We have implemented this method as a software tool that generates the Collatz numbers of individual stairs. We also show that starting from any value in any convergence stair the conjecture holds. However, to prove the conjecture, one has to show that every natural number will appear in some stair; i.e., the union of all stairs is equal to the set of natural numbers, which remains an open problem.
]]></description>
<dc:subject>Collatz-problem nonlinear-dynamics number-theory automata rather-interesting discrete-mathematics to-understand to-simulate consider:analgous-systems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:8bf9887d85ec/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Collatz-problem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nonlinear-dynamics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:analgous-systems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1606.02982">
    <title>[1606.02982] Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane</title>
    <dc:date>2022-07-24T12:30:43+00:00</dc:date>
    <link>https://arxiv.org/abs/1606.02982</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on ℤ2 defined by a fixed step set that is a subset of the non-zero vectors with coordinates 0, 1 or −1. We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane ℕ2, counted by their length and by the position of their ending point. Bousquet-Mélou and Mishna [Contemp. Math., pp. 1--39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201--215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their 19×4 combinatorially meaningful specializations only four are algebraic functions.
]]></description>
<dc:subject>random-walks enumeration combinatorics rather-interesting OEIS generating-functions discrete-mathematics to-understand to-write-about consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:cdecdeb4cb27/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-walks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:OEIS"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generating-functions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://divisbyzero.com/2022/01/27/preorders-and-finite-topological-spaces/">
    <title>Preorders and Finite Topological Spaces – David Richeson: Division by Zero</title>
    <dc:date>2022-05-22T12:59:16+00:00</dc:date>
    <link>https://divisbyzero.com/2022/01/27/preorders-and-finite-topological-spaces/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Today I tweeted that I had asked my topology students to find all of the different topologies of a two-point set and a three-point set. It turns out that there are three of the former and nine of the latter. (The sequence of the number of topologies for an n-point set begins 1 (for ), 3 (), 9 (), 33, 139, 718, 4535, 35979, 363083, 4717687, 79501654, 1744252509, 49872339897, 1856792610995, 89847422244493, 5637294117525695,… and is sequence A001930 in the OEIS.)
Akiva Weinberger (@akivaw) tweeted back to me saying that this is the same number of “preorders” on a set with n elements. I admitted that I’d never heard of a preorder. Then he and Joel David Hamkins (@jdhamkins) filled me in on what a preordered set is.
It found it to be pretty cool—especially the connection to topologies of finite sets. So I thought I’d share it here on my blog.
]]></description>
<dc:subject>set-theory combinatorics rather-interesting enumeration explanation discrete-mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:49ae06dc764a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:set-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:explanation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1810.02241">
    <title>[1810.02241] Recursion schemes, discrete differential equations and characterization of polynomial time computation</title>
    <dc:date>2022-01-26T13:44:39+00:00</dc:date>
    <link>https://arxiv.org/abs/1810.02241</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This papers studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and provides several implicit characterizations of complexity and computability classes. 
The proposed framework presents an original point of view on complexity and computability classes. It also unifies in an elegant settings various constructions that have been proposed for characterizing these classes. This includes Cobham's and, Bellantoni and Cook's definition of polynomial time and later extensions on the approach, as well as recent characterizations of computability and complexity by classes of ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory. 
At a more technical point of view, this paper points out the fundamental role of linear (discrete) ordinary differential equations and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming various algorithms.
]]></description>
<dc:subject>diffy-Qs discrete-mathematics nonlinear-dynamics representation rather-interesting computational-complexity models-and-modes to-understand to-write-about consider:genetic-programming consider:approximation ReQ</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b5692977ee6e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:diffy-Qs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nonlinear-dynamics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:models-and-modes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:ReQ"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1805.03863">
    <title>[1805.03863] Signature Catalan Combinatorics</title>
    <dc:date>2022-01-14T13:13:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1805.03863</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The Catalan numbers constitute one of the most important sequences in combinatorics. Catalan objects have been generalized in various directions, including the classical Fuss-Catalan objects and the rational Catalan generalization of Armstrong-Rhoades-Williams. We propose a wider generalization of these families indexed by a composition s which is motivated by the combinatorics of planar rooted trees; when s=(2,...,2) and s=(k+1,...,k+1) we recover the classical Catalan and Fuss-Catalan combinatorics, respectively. Furthermore, to each pair (a,b) of relatively prime numbers we can associate a signature that recovers the combinatorics of rational Catalan objects. We present explicit bijections between the resulting s-Catalan objects, and a fundamental recurrence that generalizes the fundamental recurrence of the classical Catalan numbers. Our framework allows us to define signature generalizations of parking functions which coincide with the generalized parking functions studied by Pitman-Stanley and Yan, as well as generalizations of permutations which coincide with the notion of Stirling multipermutations introduced by Gessel-Stanley. Some of our constructions differ from the ones of Armstrong-Rhoades-Williams, however as a byproduct of our extension, we obtain the additional notions of rational permutations and rational trees.
]]></description>
<dc:subject>combinatorics enumeration rather-interesting review discrete-mathematics feature-construction to-write-about consider:equivalences consider:group-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2c0d3c8e737c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:equivalences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:group-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2107.10897">
    <title>[2107.10897] Griddings of permutations and hardness of pattern matching</title>
    <dc:date>2021-10-01T20:42:20+00:00</dc:date>
    <link>https://arxiv.org/abs/2107.10897</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations τ (the `text') and π (the `pattern'), and the goal is to decide whether τ contains π as a subpermutation. On general inputs, PPM is known to be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern σ; this restriction is known as Av(σ)-PPM. It has been previously shown that Av(σ)-PPM is polynomial for any σ of size at most 3, while it is NP-hard for any σ containing a monotone subsequence of length four. 
In this paper, we present a new hardness reduction which allows us to show, in a uniform way, that Av(σ)-PPM is hard for every σ of size at least 6, for every σ of size 5 except the symmetry class of 41352, as well as for every σ symmetric to one of the three permutations 4321, 4312 and 4231. Moreover, assuming the exponential time hypothesis, none of these hard cases of Av(σ)-PPM can be solved in time 2o(n/logn). Previously, such conditional lower bound was not known even for the unconstrained PPM problem. 
On the tractability side, we combine the CSP approach of Guillemot and Marx with the structural results of Huczynska and Vatter to show that for any monotone-griddable permutation class C, PPM is polynomial when the text is restricted to a permutation from C.
]]></description>
<dc:subject>computational-complexity algorithms discrete-mathematics rather-interesting permutations to-understand to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2ea3990f786e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:permutations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1802.03482">
    <title>[1802.03482] A Continuation Method for Discrete Optimization and its Application to Nearest Neighbor Classification</title>
    <dc:date>2021-06-07T10:52:32+00:00</dc:date>
    <link>https://arxiv.org/abs/1802.03482</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The continuation method is a popular approach in non-convex optimization and computer vision. The main idea is to start from a simple function that can be minimized efficiently, and gradually transform it to the more complicated original objective function. The solution of the simpler problem is used as the starting point to solve the original problem. We show a continuation method for discrete optimization problems. Ideally, we would like the evolved function to be hill-climbing friendly and to have the same global minima as the original function. We show that the proposed continuation method is the best affine approximation of a transformation that is guaranteed to transform the function to a hill-climbing friendly function and to have the same global minima. 
We show the effectiveness of the proposed technique in the problem of nearest neighbor classification. Although nearest neighbor methods are often competitive in terms of sample efficiency, the computational complexity in the test phase has been a major obstacle in their applicability in big data problems. Using the proposed continuation method, we show an improved graph-based nearest neighbor algorithm. The method is readily understood and easy to implement. We show how the computational complexity of the method in the test phase scales gracefully with the size of the training set, a property that is particularly important in big data applications.
]]></description>
<dc:subject>machine-learning heuristics approximation proxy-problems rather-interesting discrete-mathematics to-write-about consider:visualization consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d91e1255bca1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:machine-learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proxy-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1606.09596">
    <title>[1606.09596] Minimizing the Total Movement for Movement to Independence Problem on a Line</title>
    <dc:date>2021-06-05T12:10:19+00:00</dc:date>
    <link>https://arxiv.org/abs/1606.09596</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a positive real value δ, a set P of points along a line and a distance function d, in the movement to independence problem, we wish to move the points to new positions on the line such that for every two points pi,pj∈P, we have d(pi,pj)≥δ while minimizing the sum of movements of all points. This measure of the cost for moving the points was previously unsolved in this setting. However for different cost measures there are algorithms of O(nlog(n)) or of O(n). We present an O(nlog(n)) algorithm for the points on a line and thus conclude the setting in one dimension.
]]></description>
<dc:subject>optimization multiobjective-optimization rather-interesting discrete-mathematics to-simulate to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2a73503a31ef/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:multiobjective-optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1902.10752">
    <title>[1902.10752] Formal structure of periodic system of elements</title>
    <dc:date>2021-05-28T17:36:01+00:00</dc:date>
    <link>https://arxiv.org/abs/1902.10752</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[For more than 150 years the structure of the periodic system of the chemical elements has intensively motivated research in different areas of chemistry and physics. However, there is still no unified picture of what a periodic system is. Herein, based on the relations of order and similarity, we report a formal mathematical structure for the periodic system, which corresponds to an ordered hypergraph. It is shown that the current periodic system of chemical elements is an instance of the general structure. The definition is used to devise a tailored periodic system of polarizability of single covalent bonds, where order relationships are quantified within subsets of similar bonds and among these classes. The generalised periodic system allows envisioning periodic systems in other disciplines of science and humanities.
]]></description>
<dc:subject>chemistry periodic-table discrete-mathematics rather-interesting looking-to-see formalization graph-theory hypergraphs order-relationships</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d75298a8d136/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:chemistry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:periodic-table"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:order-relationships"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1708.04773">
    <title>[1708.04773] Thickness and Antithickness of Graphs</title>
    <dc:date>2020-05-05T22:20:31+00:00</dc:date>
    <link>https://arxiv.org/abs/1708.04773</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper studies questions about duality between crossings and non-crossings in graph drawings via the notions of thickness and antithickness. The "thickness" of a graph G is the minimum integer k such that in some drawing of G, the edges can be partitioned into k noncrossing subgraphs. The "antithickness" of a graph G is the minimum integer k such that in some drawing of G, the edges can be partitioned into k thrackles, where a "thrackle" is a set of edges, each pair of which intersect exactly once. (Here edges with a common endvertex v are considered to intersect at v.) So thickness is a measure of how close a graph is to being planar, whereas antithickness is a measure of how close a graph is to being a thrackle. This paper explores the relationship between the thickness and antithickness of a graph, under various graph drawing models, with an emphasis on extremal questions.
]]></description>
<dc:subject>graph-layout graph-theory feature-construction rather-interesting combinatorics discrete-mathematics to-simulate to-write-about consider:classification</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d8065461d0a2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-layout"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:classification"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1904.04791">
    <title>[1904.04791] Planar graphs have bounded queue-number</title>
    <dc:date>2020-05-02T12:22:54+00:00</dc:date>
    <link>https://arxiv.org/abs/1904.04791</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. 
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. (2004) that graphs in a proper minor-closed class have low treewidth colourings.
]]></description>
<dc:subject>discrete-mathematics feature-construction rather-interesting proof to-simulate to-write-about consider:where-it-appears-in-GP</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:581de4ed373c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:where-it-appears-in-GP"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1907.00272">
    <title>[1907.00272] Intersection Graphs of Non-crossing Paths</title>
    <dc:date>2020-05-02T11:23:45+00:00</dc:date>
    <link>https://arxiv.org/abs/1907.00272</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree. Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). 
For intersection graphs of NC paths of a tree, the dominating set problem is shown to be solvable in linear time. Also, each such graph is shown to have a Hamiltonian cycle if and only if it is 2-connected, and to have a Hamiltonian path if and only if its block-cutpoint tree is a path.
]]></description>
<dc:subject>graph-theory graph-recognition classification algorithms rather-interesting discrete-mathematics to-simulate to-write-about consider:classification</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:328d3dc6eaf0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-recognition"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:classification"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1905.13216">
    <title>[1905.13216] A generalisation of the honeycomb dimer model to higher dimensions</title>
    <dc:date>2019-12-29T10:40:43+00:00</dc:date>
    <link>https://arxiv.org/abs/1905.13216</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper studies a generalisation of the honeycomb dimer model to higher dimensions. The generalisation was introduced by Linde, Moore, and Nordahl. Each sample of the model is both a tiling and a height function. First, we derive a surprising identity for the covariance structure of the model. Second, we prove that the surface tension associated with the model is strictly convex, in any dimension. This greatly streamlines the original proof for strict convexity by Sheffield. It implies a large deviations result with a unique minimiser for the rate function, and consequently a variational principle with a unique limit shape. Third, we demonstrate that the model is a perfect matching model on a hypergraph with a generalised Kasteleyn theory: the partition function is given by the Cayley hyperdeterminant of the appropriate hypermatrix. The formula so obtained is very challenging: the author does not expect a closed-form solution for the surface tension. The first two results rely on the development of the boundary swap, which is a versatile technique for understanding the model; it is inspired by the double dimer model, works in any dimension, and may be of independent interest.
]]></description>
<dc:subject>tiling domino-tiling discrete-mathematics combinatorics rather-interesting stochastic-systems to-simulate to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fa860d758083/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:domino-tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:stochastic-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://dmtcs.episciences.org/2293">
    <title>Discrete Mathematics &amp; Theoretical Computer Science - #2293 - An n-Dimensional Generalization of the Rhombus Tiling</title>
    <dc:date>2019-12-29T10:40:00+00:00</dc:date>
    <link>https://dmtcs.episciences.org/2293</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial mixing times for Markov chains based on local moves, 2) use coupling from the past to sample perfectly random tilings, 3) map the statistics of random tilings at large scales to physical models of random surfaces, and and 4) are related to the "arctic circle"' phenomenon.However, few examples are known for which this approach works in three or more dimensions.Here we show that the rhombus tiling can be generalized to n-dimensional tiles for any 𝑛≥3
n
≥
3
. For each 𝑛
n
, we show that a certain local move is ergodic, and conjecture that it has a mixing time of 𝑂(𝐿𝑛+2𝑙𝑜𝑔𝐿)
O
(
L
n
+
2
l
o
g
L
)
 on regions of size 𝐿
L
. For 𝑛=3
n
=
3
, the tiles are rhombohedra, and the local move consists of switching between two tilings of a rhombic dodecahedron.We use coupling from the past to sample random tilings of a large rhombic dodecahedron, and show that arctic regions exist in which the tiling is frozen into a fixed state.However, unlike the two-dimensional case in which the arctic region is an inscribed circle, here it seems to be octahedral.In addition, height fluctuations between the boundary of the region and the center appear to be constant rather than growing logarithmically.We conjecture that this is because the physics of the model is in a "smooth" phase where it is rigid at large scales, rather than a "rough" phase in which it is elastic.

]]></description>
<dc:subject>tiling hey-I-know-this-guy discrete-mathematics combinatorics generalization domino-tiling rather-interesting to-simulate to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:805a2c4985f6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hey-I-know-this-guy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:domino-tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/0810.5750">
    <title>[0810.5750] Can Kinematic Diffraction Distinguish Order from Disorder?</title>
    <dc:date>2019-09-07T22:25:16+00:00</dc:date>
    <link>https://arxiv.org/abs/0810.5750</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Diffraction methods are at the heart of structure determination of solids. While Bragg-like scattering (pure point diffraction) is a characteristic feature of crystals and quasicrystals, it is not straightforward to interpret continuous diffraction intensities, which are generally linked to the presence of disorder. However, based on simple model systems, we demonstrate that it may be impossible to draw conclusions on the degree of order in the system from its diffraction image. In particular, we construct a family of one-dimensional binary systems which cover the entire entropy range but still share the same purely diffuse diffraction spectrum.
]]></description>
<dc:subject>inverse-problems spectra tiling rather-interesting discrete-mathematics combinatorics feature-extraction to-understand to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:93a9ecae96a3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inverse-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:spectra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/abstract/document/5763326">
    <title>A global postsynthesis optimization method for combinational circuits - IEEE Conference Publication</title>
    <dc:date>2019-06-27T10:57:14+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/abstract/document/5763326</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A genetic programming-based circuit synthesis method is proposed that enables to globally optimize the number of gates in circuits that have already been synthesized using common methods such as ABC and SIS. The main contribution is a proposal for a new fitness function that enables to significantly reduce the fitness evaluation time in comparison to the state of the art. The fitness function performs optimized equivalence checking using a SAT solver. It is shown that the equivalence checking time can significantly be reduced when knowledge of the parent circuit and its mutated offspring is taken into account. For a cost of a runtime, results of conventional synthesis conducted using SIS and ABC were improved by 20-40% for the LGSynth93 benchmarks.
]]></description>
<dc:subject>genetic-programming Cartesian-GP boolean-networks boolean-matching discrete-mathematics rather-interesting algorithms to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:79ad77ac6b0a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Cartesian-GP"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:boolean-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:boolean-matching"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1810.07800">
    <title>[1810.07800] Alignments as Compositional Structures</title>
    <dc:date>2019-04-17T10:49:17+00:00</dc:date>
    <link>https://arxiv.org/abs/1810.07800</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Alignments, i.e., position-wise comparisons of two or more strings or ordered lists are of utmost practical importance in computational biology and a host of other fields, including historical linguistics and emerging areas of research in the Digital Humanities. The problem is well-known to be computationally hard as soon as the number of input strings is not bounded. Due to its prac- tical importance, a huge number of heuristics have been devised, which have proved very successful in a wide range of applications. Alignments nevertheless have received hardly any attention as formal, mathematical structures. Here, we focus on the compositional aspects of alignments, which underlie most algo- rithmic approaches to computing alignments. We also show that the concepts naturally generalize to finite partially ordered sets and partial maps between them that in some sense preserve the partial orders.
]]></description>
<dc:subject>discrete-mathematics optimization alignments combinatorics hey-I-know-this-guy bioinformatics rather-interesting formalization to-write-about consider:multiobjective-optimization consider:fitness-landscapes question:transitivity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:cdd8a5b8e59e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:alignments"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hey-I-know-this-guy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:bioinformatics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:multiobjective-optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:fitness-landscapes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:question:transitivity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1805.04055">
    <title>[1805.04055] Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect</title>
    <dc:date>2019-04-15T11:02:08+00:00</dc:date>
    <link>https://arxiv.org/abs/1805.04055</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: 
∙ Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable `flips' (assignment changes), preserving satisfiability at every step? 
∙ Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? 
∙ Given two points in {0,1}n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? 
These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.
]]></description>
<dc:subject>computational-complexity discrete-mathematics optimization rather-interesting meta-problems planning puzzles mathematical-recreations constraint-satisfaction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7ec3e0b501fe/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:meta-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:planning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:puzzles"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1504.08259">
    <title>[1504.08259] Edit Distance for Pushdown Automata</title>
    <dc:date>2017-11-17T13:21:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1504.08259</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The edit distance between two words w1,w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages 1,2, where the edit distance from 1 to 2 is the minimal number k such that for every word from 1 there exists a word in 2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1)~deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k, and (2)~deciding whether the edit distance from a pushdown automaton to a finite automaton is finite.]]></description>
<dc:subject>formal-languages edit-distance metrics define-your-terms rather-interesting open-questions discrete-mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:ac7e4fd03e37/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formal-languages"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:edit-distance"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:metrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:define-your-terms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1611.01479">
    <title>[1611.01479] Space-Efficient Re-Pair Compression</title>
    <dc:date>2017-09-28T00:22:18+00:00</dc:date>
    <link>https://arxiv.org/abs/1611.01479</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Re-Pair is an effective grammar-based compression scheme achieving strong compression rates in practice. Let n, σ, and d be the text length, alphabet size, and dictionary size of the final grammar, respectively. In their original paper, the authors show how to compute the Re-Pair grammar in expected linear time and 5n+4σ2+4d+n‾√ words of working space on top of the text. In this work, we propose two algorithms improving on the space of their original solution. Our model assumes a memory word of ⌈log2n⌉ bits and a re-writable input text composed by n such words. Our first algorithm runs in expected (n/ϵ) time and uses (1+ϵ)n+n‾√ words of space on top of the text for any parameter 0<ϵ≤1 chosen in advance. Our second algorithm runs in expected (nlogn) time and improves the space to n+n‾√ words.]]></description>
<dc:subject>strings compression algorithms rather-interesting to-write-about discrete-mathematics computational-complexity nudge-targets consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:8345d8e06667/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:strings"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:compression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1709.05314">
    <title>[1709.05314] String Attractors</title>
    <dc:date>2017-09-28T00:19:45+00:00</dc:date>
    <link>https://arxiv.org/abs/1709.05314</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Let S be a string of length n. In this paper we introduce the notion of \emph{string attractor}: a subset of the string's positions [1,n] such that every distinct substring of S has an occurrence crossing one of the attractor's elements. We first show that the minimum attractor's size yields upper-bounds to the string's repetitiveness as measured by its linguistic complexity and by the length of its longest repeated substring. We then prove that all known compressors for repetitive strings induce a string attractor whose size is bounded by their associated repetitiveness measure, and can therefore be considered as approximations of the smallest one. Using further reductions, we derive the approximation ratios of these compressors with respect to the smallest attractor and solve several open problems related to the asymptotic relations between repetitiveness measures (in particular, between the the sizes of the Lempel-Ziv factorization, the run-length Burrows-Wheeler transform, the smallest grammar, and the smallest macro scheme). These reductions directly provide approximation algorithms for the smallest string attractor. We then apply string attractors to solve efficiently a fundamental problem in the field of compressed computation: we present a universal compressed data structure for text extraction that improves existing strategies simultaneously for \emph{all} known dictionary compressors and that, by recent lower bounds, almost matches the optimal running time within the resulting space. To conclude, we consider generalizations of string attractors to labeled graphs, show that the attractor problem is NP-complete on trees, and provide a logarithmic approximation computable in polynomial time.]]></description>
<dc:subject>strings compression discrete-mathematics rather-interesting feature-construction to-write-about data-structures nudge-targets consider:looking-to-see combinatorics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:82fe4afe6e07/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:strings"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:compression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1708.05255">
    <title>[1708.05255] Category Theory for Genetics</title>
    <dc:date>2017-09-20T11:57:46+00:00</dc:date>
    <link>https://arxiv.org/abs/1708.05255</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We introduce a categorical language in which it is possible to talk about DNA sequencing, alignment methods, CRISPR, homologous recombination, haplotypes, and genetic linkage. This language takes the form of a class of limit-sketches whose categories of models can model different concepts of Biology depending on what their categories of values are. We discuss examples of models in the category of sets and in the category of modules over the Boolean semi-ring {0,1}. We identify a subclass of models in sets that models the genetic material of living beings and another subclass of models in modules that models haplotypes. We show how the two classes are related via a universal property.]]></description>
<dc:subject>category-theory theoretical-biology genetics representation to-read to-write-about discrete-mathematics philosophy-of-science via:absfac</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:733f80bddafa/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:category-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:theoretical-biology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:genetics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:philosophy-of-science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:via:absfac"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1603.08269">
    <title>[1603.08269] Equivalence of Deterministic walks on regular lattices on the plane</title>
    <dc:date>2017-04-22T12:24:04+00:00</dc:date>
    <link>https://arxiv.org/abs/1603.08269</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider deterministic walks on square, triangular and hexagonal two dimensional lattices. In each case, there is a scatterer at every site that can be in one of two states that force the walker to turn either to his/her immediate right or left. After the walker is scattered, the scatterer changes state. A lattice with an arrangement of scatterers is an environment. We show that there are only two environments for which the scattering rules are injective, mirrors or rotators, on the three lattices. On hexagonal lattices, B. Z. Webb and E. G. D. Cohen, proved that given an initial position and velocity of the walker and an environment of one type of scatterers, mirrrors or rotators, there is an environment of the other type such that the walks on both environments are equivalent, meaning they visit the same sites at the same time steps. We prove the equivalence of walks on square and triangular lattices and include a proof of the equivalence of walks on hexagonal lattices. The proofs are based both on the geometry of the lattice and the structure of the scattering rule.]]></description>
<dc:subject>cellular-automata artificial-life discrete-mathematics rather-interesting to-write-about computational-complexity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:312e3b2012a5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:artificial-life"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://search.arxiv.org:8081/paper.jsp?r=1501.02502&amp;qid=1491475924245ler_nCnN_397128995&amp;qs=%22magic+square%22&amp;byDate=1">
    <title>[1501.02502] On generalized Howell designs with block size three</title>
    <dc:date>2017-04-22T10:12:59+00:00</dc:date>
    <link>http://search.arxiv.org:8081/paper.jsp?r=1501.02502&amp;qid=1491475924245ler_nCnN_397128995&amp;qs=%22magic+square%22&amp;byDate=1</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we examine a class of doubly resolvable combinatorial objects. Let $t, k, \lambda, s$ and $v$ be nonnegative integers, and let $X$ be a set of $v$ symbols. A generalized Howell design, denoted $t$-$GHD_{k}(s,v;\lambda)$, is an $s\times s$ array, each cell of which is either empty or contains a $k$-set of symbols from $X$, called a block, such that: (i) each symbol appears exactly once in each row and in each column (i.e.\ each row and column is a resolution of $X$); (ii) no $t$-subset of elements from $X$ appears in more than $\lambda$ cells. Particular instances of the parameters correspond to Howell designs, doubly resolvable balanced incomplete block designs (including Kirkman squares), doubly resolvable nearly Kirkman triple systems, and simple orthogonal multi-arrays (which themselves generalize mutually orthogonal Latin squares). Generalized Howell designs also have connections with permutation arrays and multiply constant-weight codes. 
In this paper, we concentrate on the case that $t=2$, $k=3$ and $\lambda=1$, and write $GHD(s,v)$. In this case, the number of empty cells in each row and column falls between 0 and $(s-1)/3$. Previous work has considered the existence of GHDs on either end of the spectrum, with at most 1 or at least $(s-2)/3$ empty cells in each row or column. In the case of one empty cell, we correct some results of Wang and Du, and show that there exists a $GHD(n+1,3n)$ if and only if $n \geq 6$, except possibly for $n=6$. In the case of two empty cells, we show that there exists a $GHD(n+2,3n)$ if and only if $n \geq 6$. Noting that the proportion of cells in a given row or column of a $GHD(s,v)$ which are empty falls in the interval $[0,1/3)$, we prove that for any $\pi \in [0,5/18]$, there is a $GHD(s,v)$ whose proportion of empty cells in a row or column is arbitrarily close to $\pi$.
]]></description>
<dc:subject>combinatorics Latin-squares construction discrete-mathematics algorithms rather-interesting to-write nudge-targets consider:looking-to-see consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b6eda9f6b582/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Latin-squares"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1108.5574">
    <title>[1108.5574] Substitutive Arnoux-Rauzy sequences have pure discrete spectrum</title>
    <dc:date>2017-04-19T14:02:29+00:00</dc:date>
    <link>https://arxiv.org/abs/1108.5574</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We prove that the symbolic dynamical system generated by a purely substitutive Arnoux-Rauzy sequence is measurably conjugate to a toral translation. The proof is based on an explicit construction of a fundamental domain with fractal boundary (a Rauzy fractal) for this toral translation.
]]></description>
<dc:subject>dynamical-systems discrete-mathematics rewriting-systems to-understand strings representation to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:33f85a6f5cca/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:strings"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1109.4994">
    <title>[1109.4994] The finite-state character of physical dynamics</title>
    <dc:date>2017-03-24T23:32:00+00:00</dc:date>
    <link>https://arxiv.org/abs/1109.4994</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Finite physical systems have only a finite amount of distinct state. This finiteness is fundamental in statistical mechanics, where the maximum number of distinct states compatible with macroscopic constraints defines entropy. Here we show that finiteness of distinct state is similarly fundamental in ordinary mechanics: energy and momentum are defined by the maximum number of distinct states possible in a given time or distance. More generally, any moment of energy or momentum bounds distinct states in time or space. These results generalise both the Nyquist bandwidth-bound on distinct values in classical signals, and quantum uncertainty bounds. The new certainty bounds are achieved by finite-bandwidth evolutions in which time and space are effectively discrete, including quantum evolutions that are effectively classical. Since energy and momentum count distinct states, they are defined in classical finite-state dynamics, and they relate classical relativity to finite-state evolution.
]]></description>
<dc:subject>hey-I-know-this-guy physics automata theoretical-physics complexology quantum discrete-mathematics philosophy-of-science representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:ea2f914506cd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hey-I-know-this-guy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:physics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:theoretical-physics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complexology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:philosophy-of-science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1702.00146">
    <title>[1702.00146] Untangling Planar Curves</title>
    <dc:date>2017-02-26T20:47:02+00:00</dc:date>
    <link>https://arxiv.org/abs/1702.00146</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires Θ(n3/2) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. Our lower bound also implies that Ω(n3/2) facial electrical transformations are required to reduce any plane graph with treewidth Ω(n‾√) to a single vertex, matching known upper bounds for rectangular and cylindrical grid graphs. More generally, we prove that transforming one immersion of k circles with at most n self-crossings into another requires Θ(n3/2+nk+k2) homotopy moves in the worst case. Finally, we prove that transforming one noncontractible closed curve to another on any orientable surface requires Ω(n2) homotopy moves in the worst case; this lower bound is tight if the curve is homotopic to a simple closed curve.
]]></description>
<dc:subject>computational-geometry discrete-mathematics rather-interesting heuristics nudge-targets consider:looking-to-see to-write-about consider:representation topology</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9e80b852db93/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:topology"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1606.02907">
    <title>[1606.02907] Winding angles of long lattice walks</title>
    <dc:date>2016-10-03T09:47:57+00:00</dc:date>
    <link>https://arxiv.org/abs/1606.02907</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the winding angles of random and self-avoiding walks on square and cubic lattices with number of steps N ranging up to 107. We show that the mean square winding angle ⟨θ2⟩ of random walks converges to the theoretical form when N→∞. For self-avoiding walks on the square lattice, we show that the ratio ⟨θ4⟩/⟨θ2⟩2 converges slowly to the Gaussian value 3. For self avoiding walks on the cubic lattice we find that the ratio ⟨θ4⟩/⟨θ2⟩2 exhibits non-monotonic dependence on N and reaches a maximum of 3.73(1) for N≈104. We show that to a good approximation, the square winding angle of a self-avoiding walk on the cubic lattice can be obtained from the summation of the square change in the winding angles of lnN independent segments of the walk, where the i-th segment contains 2i steps. We find that the square winding angle of the i-th segment increases approximately as i0.5, which leads to an increase of the total square winding angle proportional to (lnN)1.5.]]></description>
<dc:subject>random-walks discrete-mathematics probability-theory rather-interesting physics! nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0be1e63430d7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-walks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:physics!"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1504.07883">
    <title>[1504.07883] An Optimal Algorithm for Tiling the Plane with a Translated Polyomino</title>
    <dc:date>2016-04-12T12:46:36+00:00</dc:date>
    <link>http://arxiv.org/abs/1504.07883</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[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.
]]></description>
<dc:subject>tiling discrete-mathematics classification proof algorithms nudge-targets consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0d31ebc8a86a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1312.4429">
    <title>[1312.4429] The Flip Diameter of Rectangulations and Convex Subdivisions</title>
    <dc:date>2016-04-09T11:25:10+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.4429</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the configuration space of rectangulations and convex subdivisions of n points in the plane. It is shown that a sequence of O(nlogn) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of n points. This bound is the best possible for some point sets, while Θ(n) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of n points in the plane.
]]></description>
<dc:subject>discrete-mathematics computational-geometry rewriting-systems rather-interesting nudge-targets consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7f2cd7a3ba09/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1603.07737">
    <title>[1603.07737] The Planar Tree Packing Theorem</title>
    <dc:date>2016-04-09T11:08:56+00:00</dc:date>
    <link>http://arxiv.org/abs/1603.07737</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garc\'ia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.
]]></description>
<dc:subject>graph-theory combinatorics discrete-mathematics algorithms nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:5988d50babae/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1511.00243">
    <title>[1511.00243] Shortest Reconfiguration of Sliding Tokens on a Caterpillar</title>
    <dc:date>2016-04-09T11:03:08+00:00</dc:date>
    <link>http://arxiv.org/abs/1511.00243</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in |I_b|. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I_b into I_r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. The reconfiguration problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. For the 3SAT problem, a trichotomy for the complexity of finding the shortest sequence has been shown, that is, it is in P, NP-complete, or PSPACE-complete in certain conditions. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. Namely, finding a shortest sequence between two independent sets can be more difficult than the decision problem of reconfigurability between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs. More precisely, we can find a shortest sequence between two independent sets on a graph G in polynomial time if either G is a proper interval graph, a trivially perfect graph, or a caterpillar. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours.
]]></description>
<dc:subject>mathematical-recreations discrete-mathematics planning optimization puzzles nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:160048c4c477/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:planning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:puzzles"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.04538">
    <title>[1507.04538] Comparing two statistical ensembles of quadrangulations: a continued fraction approach</title>
    <dc:date>2016-04-04T13:17:15+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.04538</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We use a continued fraction approach to compare two statistical ensembles of quadrangulations with a boundary, both controlled by two parameters. In the first ensemble, the quadrangulations are bicolored and the parameters control their numbers of vertices of both colors. In the second ensemble, the parameters control instead the number of vertices which are local maxima for the distance to a given vertex, and the number of those which are not. Both ensembles may be described either by their (bivariate) generating functions at fixed boundary length or, after some standard slice decomposition, by their (bivariate) slice generating functions. We first show that the fixed boundary length generating functions are in fact equal for the two ensembles. We then show that the slice generating functions, although different for the two ensembles, simply correspond to two different ways of encoding the same quantity as a continued fraction. This property is used to obtain explicit expressions for the slice generating functions in a constructive way.
]]></description>
<dc:subject>graph-theory discrete-mathematics algorithms representation rather-interesting nudge-targets consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:dc0652ff48ff/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1603.07215">
    <title>[1603.07215] Pre-Expansivity in Cellular Automata</title>
    <dc:date>2016-03-26T12:40:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1603.07215</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We introduce the property of pre-expansivity for cellular automata (CA): it is the property of being expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between expansivity and pre-injectivity, two important notions of CA theory. We show that there exist one-dimensional pre-expansive CAs which are not (positively) expansive and they can be chosen reversible. We show however that no bi-dimensional CA which is linear over an Abelian group can be pre-expansive. We also consider the finer notion of k-expansivity (expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.
]]></description>
<dc:subject>cellular-automata discrete-mathematics feature-construction classification nudge-targets consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f25b717fdd21/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1603.01382">
    <title>[1603.01382] Reptilings and space-filling curves for acute triangles</title>
    <dc:date>2016-03-15T12:11:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1603.01382</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[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.
]]></description>
<dc:subject>tiling discrete-mathematics combinatorics proof mathematical-recreations rather-interesting nudge-targets consider:checking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:68c00161a46d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:checking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1602.08084">
    <title>[1602.08084] Ribbonlength of folded ribbon unknots in the plane</title>
    <dc:date>2016-03-07T00:12:59+00:00</dc:date>
    <link>http://arxiv.org/abs/1602.08084</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study Kauffman's model of folded ribbon knots: knots made of a thin strip of paper folded flat in the plane. The ribbonlength is the length to width ratio of such a ribbon, and it turns out that the way the ribbon is folded influences the ribbonlength. We give an upper bound of ncot(π/n) for the ribbonlength of n-stick unknots. We prove that the minimum ribbonlength for a 3-stick unknot with the same type of fold at each vertex is 33‾√, and such a minimizer is an equilateral triangle. We end the paper with a discussion of projection stick number and ribbonlength.
]]></description>
<dc:subject>knot-theory visualization discrete-mathematics rather-interesting representation algorithms nudge-targets consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:5e8d9e8dd50c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:knot-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1411.8002">
    <title>[1411.8002] The Page-R{'e}nyi parking process</title>
    <dc:date>2015-11-11T12:10:10+00:00</dc:date>
    <link>http://arxiv.org/abs/1411.8002</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[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.
]]></description>
<dc:subject>discrete-mathematics simulation probability-theory proof rather-interesting simple-models nudge-targets consider:looking-to-see consider:policies</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3e5f9b17c721/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:simulation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:simple-models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:policies"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1510.01671">
    <title>[1510.01671] Cross-boundary Behavioural Reprogrammability of Cellular Automata from Emulation Networks</title>
    <dc:date>2015-11-09T00:09:18+00:00</dc:date>
    <link>http://arxiv.org/abs/1510.01671</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We explore the reprogramming capabilities of computer programs using cellular automata (CA). We show a series of boundary crossing results, including cases of Wolfram Class 1 Elementary Cellular Automata (ECA) emulating Class 2 ECA, Class 2 ECA emulating Class 3 ECA, and Class 3 ECA emulating Class 2 ECA, along with results of a similar type for general CA (neighbourhood r=3/2), including Class 1 CA emulating Class 3 CA, Classes 3 and 4 CAs emulating Class 4 CAs, and Class 4 emulating Class 3 CAs. The emulations occur with only a constant overhead and are therefore computationally efficient. By constructing emulation networks through an exhaustive search in the compiler space, we show that topological properties determining emulation direction, such as ingoing and outgoing hub degrees, suggest a topological classification of complexity based on computing capabilities. We provide a new Turing universality result in ECA space based on a composition of ECA rules emulating ECA rule 110. The results suggest that complexity is, or can be, completely driven by initial conditions, and these are therefore in this sense more fundamental than the computer program code/rules. The approach yields a novel perspective on complexity, controllability, causality, and reprogrammability of even the simplest computer programs providing strong evidence of ubiquitous computation universality.
]]></description>
<dc:subject>rather-interesting cellular-automata discrete-mathematics dynamical-systems nudge-targets consider:rediscovery consider:performance-measures what-does-a-program-do?</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:a708ee068f46/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:what-does-a-program-do?"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02609">
    <title>[1507.02609] Wreath product of matrices</title>
    <dc:date>2015-11-01T11:16:23+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02609</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We introduce a new matrix product, that we call the wreath product of matrices. The name is inspired by the analogous product for graphs, and the following important correspondence is proven: the wreath product of the adjacency matrices of two graphs provides the adjacency matrix of the wreath product of the graphs. This correspondence is exploited in order to study the spectral properties of the famous Lamplighter random walk: the spectrum is explicitly determined for the "Walk or switch" model on a complete graph of any size, with two lamp colors. The investigation of the spectrum of the matrix wreath product is actually developed for the more general case where the second factor is a circulant matrix. Finally, an application to the study of generalized Sylvester matrix equations is treated.
]]></description>
<dc:subject>graph-theory group-theory rather-interesting discrete-mathematics exploration mathematical-recreations nudge-targets consider:looking-to-see</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fc617c219712/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:group-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:exploration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1405.6893">
    <title>[1405.6893] Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs</title>
    <dc:date>2015-07-27T11:20:30+00:00</dc:date>
    <link>http://arxiv.org/abs/1405.6893</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A path in an edge-colored graph G is \textit{rainbow} if no two edges of it are colored the same. The graph G is \textit{rainbow colored} if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph G is \textit{strong rainbow colored}. The minimum number of colors needed to make G rainbow colored is known as the \textit{rainbow connection number}, and is denoted by $\rc(G)$. The minimum number of colors needed to make G strong rainbow colored is known as the \textit{strong rainbow connection number}, and is denoted by $\src(G)$. A graph is \textit{chordal} if it contains no induced cycle of length 4 or more. We show that for every k≥3, deciding whether a chordal graph can be strong rainbow colored using k colors is $\NP$-complete. We then consider the rainbow and strong rainbow connection numbers of \textit{block graphs}, which form a subclass of chordal graphs. We give an exact linear time algorithm for strong rainbow coloring block graphs exploiting a \textit{clique tree} representation each chordal graph has. We characterize the bridgeless block graphs having rainbow connection number 2, 3, or 4, and show that for every k≤4, it is in $\P$ to decide whether $\rc(G) = k$, where G is a bridgeless block graph. We also derive a tight upper bound of |S|+2 on $\rc(G)$, where G is a block graph, and S its set of minimal separators.
]]></description>
<dc:subject>graph-theory graph-coloring feature-construction rather-interesting discrete-mathematics nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f9eec20b07c7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-coloring"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1204.5224">
    <title>[1204.5224] A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs</title>
    <dc:date>2015-06-27T14:22:13+00:00</dc:date>
    <link>http://arxiv.org/abs/1204.5224</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of (1.79𝗋𝗎𝗇(T)⋅n⋅k), where 𝗋𝗎𝗇(T) denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since 𝗋𝗎𝗇(T)<n, this can be seen as a (1.79n⋅n⋅k) algorithm which is the first to beat the exponential 2n runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for 𝗋𝗎𝗇(P).
]]></description>
<dc:subject>discrete-mathematics permutations algorithms pattern-discovery computational-complexity nudge-targets consider:representation approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:cc7b834e00f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:permutations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1405.3146">
    <title>[1405.3146] Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints</title>
    <dc:date>2015-06-24T19:50:24+00:00</dc:date>
    <link>http://arxiv.org/abs/1405.3146</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this thesis, we consider the problem of characterizing and enumerating sets of polyominoes described in terms of some constraints, defined either by convexity or by pattern containment. We are interested in a well known subclass of convex polyominoes, the k-convex polyominoes for which the enumeration according to the semi-perimeter is known only for k=1,2. We obtain, from a recursive decomposition, the generating function of the class of k-convex parallelogram polyominoes, which turns out to be rational. Noting that this generating function can be expressed in terms of the Fibonacci polynomials, we describe a bijection between the class of k-parallelogram polyominoes and the class of planted planar trees having height less than k+3. In the second part of the thesis we examine the notion of pattern avoidance, which has been extensively studied for permutations. We introduce the concept of pattern avoidance in the context of matrices, more precisely permutation matrices and polyomino matrices. We present definitions analogous to those given for permutations and in particular we define polyomino classes, i.e. sets downward closed with respect to the containment relation. So, the study of the old and new properties of the redefined sets of objects has not only become interesting, but it has also suggested the study of the associated poset. In both approaches our results can be used to treat open problems related to polyominoes as well as other combinatorial objects.
]]></description>
<dc:subject>polyominoes combinatorics counting rather-interesting discrete-mathematics nudge-targets consider:rediscovery feature-extraction feature-construction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7097df150abd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:polyominoes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:counting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1504.04498">
    <title>[1504.04498] Simpler, faster and shorter labels for distances in graphs</title>
    <dc:date>2015-05-25T12:08:02+00:00</dc:date>
    <link>http://arxiv.org/abs/1504.04498</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label lenght and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different trade-offs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. 
More specifically, we present a distance labeling scheme with label size (log 3)/2 + o(n) (logarithms are in base 2) and O(1) decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n/log n) decoding time, and Gavoille et al. (SODA'01), which uses labels of size 11n + o(n) and O(loglog n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for label sizes. For r-additive approximation schemes, where distances can be off by an additive constant r, we give both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency scheme: n/2. We also give results for bipartite graphs and for exact and 1-additive distance oracles.
]]></description>
<dc:subject>graph-theory algorithms rather-interesting discrete-mathematics nudge-targets consider:multiobjective-search performance-measure Winkler-project data-structures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:6d877c09b763/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:multiobjective-search"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Winkler-project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-structures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1501.03549">
    <title>[1501.03549] Liftings and stresses for planar periodic frameworks</title>
    <dc:date>2015-04-15T11:15:32+00:00</dc:date>
    <link>http://arxiv.org/abs/1501.03549</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We formulate and prove a periodic analog of Maxwell's theorem relating stressed planar frameworks and their liftings to polyhedral surfaces with spherical topology. We use our lifting theorem to prove deformation and rigidity-theoretic properties for planar periodic pseudo-triangulations, generalizing features known for their finite counterparts. These properties are then applied to questions originating in mathematical crystallography and materials science, concerning planar periodic auxetic structures and ultrarigid periodic frameworks.
]]></description>
<dc:subject>tiling discrete-mathematics mechanics rather-interesting proofs computational-geometry nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:97706f07d52c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mechanics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proofs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1402.2818">
    <title>[1402.2818] Radial spacing distributions from planar points sets</title>
    <dc:date>2015-04-14T11:03:55+00:00</dc:date>
    <link>http://arxiv.org/abs/1402.2818</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we explore the radial projection method for locally finite point sets and provide numerical examples for different types of order. The main question is whether the method is suitable to analyse order in a quantitive way. Our findings indicate that the answer is affermative. In this context, we also study local visibility conditions for certain types of aperiodic point sets.
]]></description>
<dc:subject>tiling computational-geometry probability-theory rather-interesting discrete-mathematics statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4737318848c3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1411.7355">
    <title>[1411.7355] Spontaneous focusing as an emergent phenomenon</title>
    <dc:date>2015-01-19T11:28:50+00:00</dc:date>
    <link>http://arxiv.org/abs/1411.7355</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We analyze the emergence of diffractive focusing in the transition from discrete to continuous space-time variables. Three types of dynamical equations are studied in a top-to-bottom approach, starting with the most general system. First we solve a linear cellular automaton of two species, then a nearest neighbour tight-binding array and finally the time-dependent Schr\"odinger equation. All models are shown to produce diffractive solutions for square packet distributions. The main result of this paper is that in discrete variables, the nature of the solutions depends strongly on the size of wavepackets, whereas in continuous variables, diffraction due to discontinuities exists at every scale. A transition in the number of participants or cells is identified by means of a measure and the corresponding phenomenon is further analyzed by a generalization of Wigner functions to discrete variables and crystals.
]]></description>
<dc:subject>rather-interesting physics discrete-mathematics approximation representation philosophy-of-science modeling-is-not-mathematics nudge-targets consider:transitional-forms consider:tunable-forms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b6b4ff6d3a65/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:physics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:philosophy-of-science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:modeling-is-not-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:transitional-forms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:tunable-forms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.0193">
    <title>[1403.0193] Flexible Time and Ether in One-dimensional Cellular Automata</title>
    <dc:date>2015-01-11T20:11:59+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.0193</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Flexible Time is a new formalism for calculations about one-dimensional cellular automata. It unifies the states of a finite number of cells into a single object, even if they occur at different times. This gives greater flexibility to handle the structures that occur in the development of a cellular automaton. 
An ether is a periodic pattern of cells that arises in some cellular automata from almost all random initial configurations. In this thesis, the formalism is developed in detail and then applied to the problem of ether formation. For the elementary cellular automaton Rule 54, a partial result is proved: There is a fragment of the ether that arises with probability 1 from every random initial configuration and is propagated with probability 1 to any later time. This is a strong argument that the ether under Rule 54 indeed arises from almost all input configurations.
]]></description>
<dc:subject>cellular-automata Wolframism discrete-mathematics pattern-discovery define-your-terms not-quite-sure thesis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f8bb5ac3aafc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Wolframism"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:define-your-terms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:not-quite-sure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:thesis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1212.5951">
    <title>[1212.5951] Cellular automata between sofic tree shifts</title>
    <dc:date>2015-01-11T13:28:09+00:00</dc:date>
    <link>http://arxiv.org/abs/1212.5951</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the sofic tree shifts of AΣ∗, where Σ∗ is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if X⊂AΣ∗ is a sofic tree shift, then the configurations in X whose orbit under the shift action is finite are dense in X, and, as a consequence of this, we deduce that every injective cellular automata τ:X→X is surjective. Moreover, a characterization of sofic tree shifts in terms of general Rabin automata is given. 
We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.
]]></description>
<dc:subject>cellular-automata group-theory out-of-the-box rather-interesting wish-I-could-follow-it-better discrete-mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:10d004d34524/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:group-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:out-of-the-box"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:wish-I-could-follow-it-better"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1302.6346">
    <title>[1302.6346] Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks</title>
    <dc:date>2014-12-08T11:47:34+00:00</dc:date>
    <link>http://arxiv.org/abs/1302.6346</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We are interested in fixed points in Boolean networks, {\em i.e.} functions f from {0,1}n to itself. We define the subnetworks of f as the restrictions of f to the subcubes of {0,1}n, and we characterizes a class  of Boolean networks satisfying the following property: Every subnetwork of f has a unique fixed point if and only if f has no subnetwork in . This characterization generalizes the fixed point theorem of Shih and Dong, which asserts that if for every x in {0,1}n there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of f evaluated at point x, then f has a unique fixed point. Then, denoting by + (resp. −) the networks whose the interaction graph is a positive (resp. negative) cycle, we show that the non-expansive networks of  are exactly the networks of +∪−; and for the class of non-expansive networks we get a "dichotomization" of the previous forbidden subnetwork theorem: Every subnetwork of f has at most (resp. at least) one fixed point if and only if f has no subnetworks in + (resp. −) subnetwork. Finally, we prove that if f is a conjunctive network then every subnetwork of f has at most one fixed point if and only if f has no subnetwork in +.
]]></description>
<dc:subject>boolean-networks Kauffmania automata complexology discrete-mathematics coupled-oscillators dynamical-systems theoretical-biology nudge-targets graph-theory proof consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4c19be90e7f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:boolean-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Kauffmania"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complexology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:coupled-oscillators"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:theoretical-biology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1411.6672">
    <title>[1411.6672] Pattern overlap implies runaway growth in hierarchical tile systems</title>
    <dc:date>2014-12-03T09:30:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1411.6672</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly *and" avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.
]]></description>
<dc:subject>DNA-computing nanotechnology biological-engineering discrete-mathematics rather-interesting nudge-targets performance-measure side-effects the-mangle-in-practice</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fd7fbb095ed4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:DNA-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nanotechnology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:biological-engineering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:side-effects"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:the-mangle-in-practice"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1009.5912">
    <title>[1009.5912] Packing six T-joins in plane graphs</title>
    <dc:date>2014-11-27T01:23:05+00:00</dc:date>
    <link>http://arxiv.org/abs/1009.5912</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Let G be a plane graph and T an even subset of its vertices. It has been conjectured that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. The case k=3 is equivalent to the Four Color Theorem, and the cases k=4, which was conjectured by Seymour, and k=5 were proved by Guenin. We settle the next open case k=6.
]]></description>
<dc:subject>graph-theory discrete-mathematics proof conjecture nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:e1ba10025745/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:conjecture"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1410.3096">
    <title>[1410.3096] Complete Characterization of Structure of Rule 54</title>
    <dc:date>2014-11-07T11:36:58+00:00</dc:date>
    <link>http://arxiv.org/abs/1410.3096</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The dynamics of rule 54 one-dimensional two-state cellular automaton (CA) are a discrete analog of a space-time dynamics of excitations in nonlinear active medium with mutual inhibition. A cell switches its state 0 to state 1 if one of its two neighbors is in state 1 (propagation of a perturbation) and a cell remains in state 1 only if its two neighbors are in state 0. A lateral inhibition is because a 1-state neighbor causes a 1-state cell to switch to state 0. The rule produces a rich spectrum of space-time dynamics, including gliders and glider guns just from four primitive gliders. We construct a catalogue of gliders and describe them by tiles. We calculate a subset of regular expressions ΨR54 to encode gliders. The regular expressions are derived from de Bruijn diagrams, tile-based representation of gliders, and cycle diagrams sometimes. We construct an abstract machine that recognizes regular expressions of gliders in rule 54 and validate ΨR54. We also propose a way to code initial configurations of gliders to depict any type of collision between the gliders and explore self-organization of gliders, formation of larger tiles, and soliton-like interactions of gliders and computable devices.
]]></description>
<dc:subject>cellular-automata review wolframism discrete-mathematics consider:the-lilies-of-the-field consider:robustness consider:stepping-back-for-a-moment-please</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2b08a8f460f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:wolframism"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:the-lilies-of-the-field"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:stepping-back-for-a-moment-please"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1212.1740">
    <title>[1212.1740] A Graph Partitioning Approach to Predict Patterns in Lateral Inhibition Systems</title>
    <dc:date>2014-08-22T12:32:16+00:00</dc:date>
    <link>http://arxiv.org/abs/1212.1740</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We analyze pattern formation on a network of cells where each cell inhibits its neighbors through cell-to-cell contact signaling. The network is modeled as an interconnection of identical dynamical subsystems each of which represents the signaling reactions in a cell. We search for steady state patterns by partitioning the graph vertices into disjoint classes, where the cells in the same class have the same final fate. To prove the existence of steady states with this structure, we use results from monotone systems theory. Finally, we analyze the stability of these patterns with a block decomposition based on the graph partition.
]]></description>
<dc:subject>pattern-formation prediction models complex-systems emergent-design nudge-targets rather-interesting discrete-mathematics dynamical-systems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:882eaa11291b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-formation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complex-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:emergent-design"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dynamical-systems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.1364">
    <title>[1403.1364] A Suffix Tree Or Not A Suffix Tree?</title>
    <dc:date>2014-08-20T10:03:31+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.1364</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we study the structure of suffix trees. Given an unlabeled tree τ on n nodes and suffix links of its internal nodes, we ask the question "Is τ a suffix tree?", i.e., is there a string S whose suffix tree has the same topological structure as τ? We place no restrictions on S, in particular we do not require that S ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that τ is a suffix tree if and only if it is realized by a string S of length n−1, and we give a linear-time algorithm for inferring S when the first letter on each edge is known. This generalizes the work of I et al. [Discrete Appl. Math. 163, 2014].
]]></description>
<dc:subject>computer-science classification discrete-mathematics nudge-targets algorithms feature-extraction interesting</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c84099c752be/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computer-science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:interesting"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.1166">
    <title>[1310.1166] Flipping Edge-Labelled Triangulations</title>
    <dc:date>2013-11-03T12:29:05+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.1166</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The problem of computing the minimum number of flips to transform one triangulation of a convex polygon to another is not known to be in P or NP-complete. A flip sequence determines a one-to-one correspondence between the edges of the two triangulations. As a step towards understanding the source of difficulty, we investigate the case when this edge correspondence is given, i.e., we want the flip distance between two edge-labelled triangulations of a convex polygon. 
We give tight worst case bounds of {\Theta}(nlogn) on the flip distance between edge-labelled triangulations of a convex polygon, and edge-labelled combinatorial triangulations, in contrast to the {\Theta}(n) bounds for the unlabelled case. Our method is to reduce to sorting with restric- ted operations, similar to the length-weighted reversals relevant in comparative genomics. Our bounds imply a lower bound on a very general model of sorting that subsumes a previously known lower bound. Using our upper bound we give an O(logn)-factor approximation algorithm for computing the flip distance between edge-labelled triangulations of a convex polygon. We also consider simultaneous flips on edge-labelled triangulations. We prove an O(log2 n) upper bound and an {\Omega}(logn) lower bound on the worst case number of simultaneous flips, in contrast with the tight bound of {\Theta}(log n) for the unlabelled case proved in SODA '06.
]]></description>
<dc:subject>combinatorics graph-theory planning nudge-targets algorithms discrete-mathematics computational-geometry computational-complexity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:41591329f9c9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:planning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1210.7320">
    <title>[1210.7320] Some open problems on permutation patterns</title>
    <dc:date>2013-02-03T14:11:12+00:00</dc:date>
    <link>http://arxiv.org/abs/1210.7320</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This is a brief survey of some open problems on permutation patterns, with an emphasis on subjects not covered in the recent book by Kitaev, emph{Patterns in Permutations and words}. I first survey recent developments on the enumeration and asymptotics of the pattern 1324, the last pattern of length 4 whose asymptotic growth is unknown, and related issues such as upper bounds for the number of avoiders of any pattern of length $k$ for any given $k$. Other subjects treated are the M"obius function, topological properties and other algebraic aspects of the poset of permutations, ordered by containment, and also the study of growth rates of permutation classes, which are containment closed subsets of this poset.]]></description>
<dc:subject>combinatorics open-problems discrete-mathematics nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b8861b4ebd1c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0812.4170">
    <title>[0812.4170] Finding Still Lifes with Memetic/Exact Hybrid Algorithms</title>
    <dc:date>2012-04-30T20:58:49+00:00</dc:date>
    <link>http://arxiv.org/abs/0812.4170</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["The maximum density still life problem (MDSLP) is a hard constraint optimization problem based on Conway's game of life. It is a prime example of weighted constrained optimization problem that has been recently tackled in the constraint-programming community. Bucket elimination (BE) is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply BE is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques unpractical for large size problems. In response to this situation, we present a memetic algorithm for the MDSLP in which BE is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. Extensive experimental results analyze the performance of these models and multi-parent recombination. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances."]]></description>
<dc:subject>pragmaticGP game-of-life cellular-automata optimization discrete-mathematics via:jj</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:029014ee4923/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pragmaticGP"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:game-of-life"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:via:jj"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://en.wikipedia.org/wiki/Minterm">
    <title>Canonical form (Boolean algebra) - Wikipedia, the free encyclopedia</title>
    <dc:date>2012-03-24T10:47:42+00:00</dc:date>
    <link>http://en.wikipedia.org/wiki/Minterm</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[things I never learned]]></description>
<dc:subject>boolean-algebra discrete-mathematics algorithms canonical-form</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fca611155b1e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:boolean-algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:canonical-form"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1203.1900">
    <title>[1203.1900] Consensus on Moving Neighborhood Model of Peterson Graph</title>
    <dc:date>2012-03-15T01:23:52+00:00</dc:date>
    <link>http://arxiv.org/abs/1203.1900</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["In this paper, we study the consensus problem of multiple agents on a kind of famous graph, Peterson graph. It is an undirected graph with 10 vertices and 15 edges. Each agent randomly walks on this graph and communicates with each other if and only if they coincide on a node at the same time. We conduct numerical study on the consensus problem in this framework and show that global consensus can be achieved."]]></description>
<dc:subject>discrete-mathematics graph-theory network-theory agent-based nudge-targets probably-not-the-same-hannah-arendt</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0a2d326d23d8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:agent-based"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probably-not-the-same-hannah-arendt"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1203.1644">
    <title>[1203.1644] The B36/S125 &quot;2x2&quot; Life-Like Cellular Automaton</title>
    <dc:date>2012-03-13T11:53:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1203.1644</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["The B36/S125 (or "2x2") cellular automaton is one that takes place on a 2D square lattice much like Conway's Game of Life. Although it exhibits high-level behaviour that is similar to Life, such as chaotic but eventually stable evolution and the existence of a natural diagonal glider, the individual objects that the rule contains generally look very different from their Life counterparts. In this article, a history of notable discoveries in the 2x2 rule is provided, and the fundamental patterns of the automaton are described. Some theoretical results are derived along the way, including a proof that the speed limits for diagonal and orthogonal spaceships in this rule are c/3 and c/2, respectively. A Margolus block cellular automaton that 2x2 emulates is investigated, and in particular a family of oscillators made up entirely of 2 x 2 blocks are analyzed and used to show that there exist oscillators with period 2^m(2^k - 1) for any integers m,k geq 1."]]></description>
<dc:subject>cellular-automata artificial-life discrete-mathematics emergence mathematical-recreations nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2b2c2144f6f2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:artificial-life"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:emergence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1107.0056">
    <title>[1107.0056] Fixed parameter algorithms for restricted coloring problems</title>
    <dc:date>2012-01-05T13:51:17+00:00</dc:date>
    <link>http://arxiv.org/abs/1107.0056</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$-tidy graphs and $(q,q-4)$-graphs, for every fixed $q$. These classes include cographs, $P_4$-sparse and $P_4$-lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$, which is the minimum $q$ such that $G$ is a $(q,q-4)$-graph. We also prove that every connected $(q,q-4)$-graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.
]]></description>
<dc:subject>algorithms graph-theory discrete-mathematics nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:16b74dec9207/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0911.3482">
    <title>[0911.3482] Complexity of Networks (reprise)</title>
    <dc:date>2011-10-10T12:02:25+00:00</dc:date>
    <link>http://arxiv.org/abs/0911.3482</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction. 

In a previous paper, a complexity measure of networks was proposed based on the {em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object. 

The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical. 
In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure."]]></description>
<dc:subject>network-theory complexology complex-systems measurement perform structure-function-relations discrete-mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0d5869bb40fc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complexology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complex-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:measurement"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:perform"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:structure-function-relations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1109.0807">
    <title>[1109.0807] Harmonic Analysis of Boolean Networks: Determinative Power and Perturbations</title>
    <dc:date>2011-10-04T13:38:45+00:00</dc:date>
    <link>http://arxiv.org/abs/1109.0807</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network?…"]]></description>
<dc:subject>Boolean-networks Kauffmania complexology discrete-mathematics mathematical-recreations nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d893c0c5de18/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Boolean-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Kauffmania"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complexology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.multimagie.com/English/Enigmas.htm">
    <title>MULTIMAGIE.COM - Enigmas on Magic Squares</title>
    <dc:date>2011-06-08T11:33:41+00:00</dc:date>
    <link>http://www.multimagie.com/English/Enigmas.htm</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["While magic squares have been known and studied for many centuries, it is surprising that for certain types of magic squares we still do not know today which are the smallest possible! In an effort to make progress on these unsolved problems, twelve prizes totaling €8,000 and 12 bottles of champagne are offered for the solutions to twelve enigmas (six main at €1,000 each, six small from €100 to €500 each):…"]]></description>
<dc:subject>mathematical-recreations puzzles discrete-mathematics contests nudge-targets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:75fb4f28deb4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:puzzles"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:contests"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1008.2555">
    <title>[1008.2555] Succinct Data Structures for Assembling Large Genomes</title>
    <dc:date>2010-08-17T12:33:37+00:00</dc:date>
    <link>http://arxiv.org/abs/1008.2555</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["Motivation: Second generation sequencing technology makes it feasible for many researches to obtain enough sequence reads to attempt the de novo assembly of higher eukaryotes (including mammals). De novo assembly not only provides a tool for understanding wide scale biological variation, but within human bio-medicine, it offers a direct way of observing both large scale structural variation and fine scale sequence variation. Unfortunately, improvements in the computational feasibility for de novo assembly have not matched the improvements in the gathering of sequence data. This is for two reasons: the inherent computational complexity of the problem, and the in-practice memory requirements of tools."
]]></description>
<dc:subject>genomics bioinformatics discrete-mathematics algorithms nudge-targets inference data-driven</dc:subject>
<dc:identifier>https://pinboard.in/u:Vaguery/b:dcbad7d6488f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:genomics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:bioinformatics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-driven"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1005.0103">
    <title>[1005.0103] An introduction to spectral distances in networks (extended version)</title>
    <dc:date>2010-06-02T12:22:46+00:00</dc:date>
    <link>http://arxiv.org/abs/1005.0103</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["Many functions have been recently defined to assess the similarity among networks as tools for quantitative comparison. They stem from very different frameworks - and they are tuned for dealing with different situations. Here we show an overview of the spectral distances, highlighting their behavior in some basic cases of static and dynamic synthetic and real networks."
]]></description>
<dc:subject>network-theory networks discrete-mathematics algorithms complexology metrics</dc:subject>
<dc:identifier>https://pinboard.in/u:Vaguery/b:414bb22c2823/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:complexology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:metrics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://mindsports.nl/index.php/side-dishes/50-china-labyrinth?5ddadc0c884344">
    <title>China Labyrinth</title>
    <dc:date>2009-08-12T11:02:10+00:00</dc:date>
    <link>http://mindsports.nl/index.php/side-dishes/50-china-labyrinth?5ddadc0c884344</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["The China Labyrinth was conceived in the early eighties by Martin Medema who was first to imagine 64 hexagons in a configuration wherein each would differ from all others in terms of the configuration of neighbours around it. That was brilliant."
]]></description>
<dc:subject>mathematical games discrete-mathematics optimization Nudge</dc:subject>
<dc:identifier>https://pinboard.in/u:Vaguery/b:984cbef913dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Nudge"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.recmath.com/PolyPages/">
    <title>The Poly Pages</title>
    <dc:date>2009-08-12T11:00:49+00:00</dc:date>
    <link>http://www.recmath.com/PolyPages/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["The purpose of this site is to try to provide information on the various polyforms: poly-ominoes, -iamonds, -hexes, -cubes etc.  There is a great deal of information already on the internet and these pages will try to provide links to all (well hopefully most!) relevant sites. Where no information seems available elsewhere as much information as possible will be posted here."
]]></description>
<dc:subject>tiling pattern pattern-discovery mathematics games puzzles combinatorics discrete-mathematics Nudge</dc:subject>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2906b80d5ed6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:pattern-discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:puzzles"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:Nudge"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://denseoutliers.blogspot.com/">
    <title>dense outliers</title>
    <dc:date>2009-03-15T22:59:54+00:00</dc:date>
    <link>http://denseoutliers.blogspot.com/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA["After a bit of work we believe we have solved most of the practical problems that have to be taken care of before starting a free journal. This is probably the easy part. Now we have to decide if it is a good idea or not.

The aim is to have a high quality journal for the CG community that is run by the CG community and free to everyone (really free, no cost to publish and no cost to access). Obviously such a journal needs the support of the CG community to be successful. The work should be shared among the community, i.e., the editorial board and editorial manager(s) should be replaced regularly. "
]]></description>
<dc:subject>mathematics academia journals publishing open-access disintermediation discrete-mathematics</dc:subject>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4915b507a0bb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:academia"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:journals"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:publishing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-access"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:disintermediation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>