Artículos con la etiqueta ‘matemáticas discretas’

Transfinite Recursion in Higher Reverse Mathematics

Por • 27 oct, 2013 • Category: Educacion

In this paper we investigate the reverse mathematics of higher-order analogues of the theory \ATRz{} within the framework of higher order reverse mathematics developed by Kohlenbach \cite{Koh01}. We define a theory \RCAzthr, a close higher-type analogue of the classical base theory \RCAz, and show that it is essentially a conservative subtheory of Kohlenbach’s base theory \RCAzo. Working over \RCAzthr, we study higher-type analogues of statements classically equivalent to \ATRz, including open and clopen determinacy, as well as two choice principles, and prove several equivalences and separations. Our main result is the separation of open and clopen determinacy for reals, using a variant of Steel forcing; in the presentation of this result, we develop a new, more flexible framework for Steel-type forcing.

Generalised probabilistic theories and conic extensions of polytopes

Por • 18 oct, 2013 • Category: Crítica

Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone C and its dual C ∗ . We show that the question whether some one way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorisation of the corresponding communication matrix M . Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone C with an affine subspace whose projection onto the original space yields the desired polytope.

A Domain-Specific Language for Discrete Mathematics

Por • 16 oct, 2013 • Category: Educacion

This paper discusses a Domain Specific Language (DSL) that has been developed to enable implementation of concepts of discrete mathematics. A library of data types and functions provides functionality which is frequently required by users. Covering the areas of Mathematical Logic, Set Theory, Functions, Graph Theory, Number Theory, Linear Algebra and Combinatorics, the language’s syntax is close to the actual notation used in the specific fields.
arXiv:1310.3473v1 [cs.PL]

When periodicities enforce aperiodicity

Por • 25 sep, 2013 • Category: Ciencia y tecnología

Aperiodic tilings are non-periodic tilings defined by local rules. They are widely used to model quasicrystals, and a central question is to understand which of the non-periodic tilings are actually aperiodic. Among tilings, those by rhombi can be easily seen as approximations of surfaces in higher dimensional spaces. In particular, those which approximate irrational planes are non-periodic. But which ones are also aperiodic? This paper introduces the notion of subperiod, which links algebraic properties of a plane with geometric properties of the tilings that approximate it. A necessary and sufficient condition is obtained for tilings that can be seen in the four dimensional Euclidean space. This result is then applied to some examples in higher codimensions, notably tilings with n-fold rotational symmetry

X- problem of value three

Por • 14 ago, 2013 • Category: Opinion

The X-problem of number 3 for one dimension and related observations are discussed

Alcuin’s Propositiones de Civitatibus: the Earliest Packing Problems

Por • 9 ago, 2013 • Category: Opinion

We consider three problems about cities from Alcuin’s_Propositiones ad acuendos juvenes_. These problems can be considered as the earliest packing problems difficult also for modern state-of-the-art packing algorithms. We discuss the Alcuin’s solutions and give the known (to the author) best solutions to these problems.

Solvability of Cubic Graphs and the Four Color Theorem

Por • 20 jul, 2013 • Category: Crítica

The aim of this paper is to assert that the minimum number of colors required to color a geographical map and the angle-sum of a triangle are twin invariants of the two-dimensional plane. Peter Tait proved, in an 1880 paper, that a bridgeless cubic plane graph G has a 4-face coloring if and only if G has a 3-edge coloring. In this paper, we explore the edge coloring problem of cubic graphs by using the newly proposed complex coloring approach. The concept of variable edges is introduced in the complex coloring method; a proper coloring is achieved by completely eliminating all variables in a color configuration of a cubic graph. The specification of solvable conditions is based on the decomposition of the configuration into maximal two-colored sub-graphs. The class of cubic graphs that does not have 3-edge coloring, called snarks, can be naturally identified by the proposed unsolvability condition.

The hard-core model on random graphs revisited

Por • 27 jun, 2013 • Category: Crítica

We revisit the classical hard-core model, also known as independent set and dual to vertex cover problem, where one puts particles with a first-neighbor hard-core repulsion on the vertices of a random graph. Although the case of random graphs with small and very large average degrees respectively are quite well understood, they yield qualitatively different results and our aim here is to reconciliate these two cases. We revisit results that can be obtained using the (heuristic) cavity method and show that it provides a closed-form conjecture for the exact density of the densest packing on random regular graphs with degree K>=20, and that for K>16 the nature of the phase transition is the same as for large K. This also shows that the hard-code model is the simplest mean-field lattice model for structural glasses and jamming.

Planar 4-critical graphs with four triangles

Por • 12 jun, 2013 • Category: Opinion

By the Grunbaum-Aksenov Theorem (extending Grotzsch’s Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.

An Erdős–Ko–Rado theorem for matchings in the complete graph

Por • 21 abr, 2013 • Category: Opinion

We consider the following higher-order analog of the Erd\H{o}s–Ko–Rado theorem. For positive integers r and n with r<= n, let M^r_n be the family of all matchings of size r in the complete graph K_{2n}. For any edge e in E(K_{2n}), the family M^r_n(e), which consists of all sets in M^r_n containing e, is called the star centered at e. We prove that if r