A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Double adjunctions

We characterize double adjunctions in terms of presheaves and universal squares, and then apply these characterizations to free monads and Eilenberg-Moore objects in double categories. We improve upon an earlier result of Fiore-Gambino-Kock in [7] to conclude: if a double category with cofolding admits the construction of free monads in its horizontal 2-category, then it also admits the construction of free monads as a double category horizontally and vertically, and also in its vertical 2-category. We also prove that a double category admits Eilenberg-Moore objects if and only if a certain parameterized presheaf is representable. Along the way, we develop parameterized presheaves on double categories and prove a double Yoneda Lemma.

On the analysis of travelling waves to a nonlinear flux limited reaction-diffusion equation

In this paper we study the existence and qualitative properties of travelling waves associated to a nonlinear flux limited partial differential equation coupled to a Fisher-Kolmogorov-Petrovskii-Piskunov type reaction term. We prove the existence and uniqueness of finite speed moving fronts of C2 classical regularity, but also the existence of discontinuous entropy travelling wave solutions.

Moduli of smoothness and growth properties of Fourier transforms: two-sided estimates

We prove two-sided inequalities between the integral moduli of smoothness of a function on R d[superscript] / T d[superscript] and the weighted tail-type integrals of its Fourier transform/series. Sharpness of obtained results in particular is given by the equivalence results for functions satisfying certain regular conditions. Applications include a quantitative form of the Riemann-Lebesgue lemma as well as several other questions in approximation theory and the theory of function spaces.

El espacio como producto social: variables arqueológicas para un análisis de la organización social en prehistoria

El espacio social es un concepto ambiguo cuyo componente material está determinado por el carácter del componente social, puesto que la organización de los objetos en el espacio y el espacio mismo, responden a las normas sociales del comportamiento humano. Partimos de la premisa que los residuos generados durante el proceso de producción y del consumo tienden a tener una distribución relativamente regular en el espacio físico. La ausencia de la aleatoriedad en la dispersión de estos restos solo significa que habían sido acumulados y depositados como restos de acciones previamente planificadas no-aleatoriamente. En este trabajo planteamos estudiar la organización y la producción del espacio social de una sociedad cazadora-recolectora concreta – la sociedad yámana - a través del análisis de las actividades cotidianas que figuran en las fuentes etnográficas y en el registro arqueológico. Con este fin creamos una metodología de trabajo interdisciplinaria, basada en un enfoque etnoarqueológico, y a través del estudio de las fuentes etnográficas, los trabajos etnoarqueológicos previos y el registro arquelógico concreto, descubrimos cuáles son las posibilidades y limitaciones de este tipo de estudios. Pudimos reconocer la regularidad espacial de los procesos de producción y reproducción social y a resolver algunas preguntas acerca del estudio de la organización social en prehistoria trabajando con los datos etnoarqueológicos obtenidos en los yacimientos Lanashuaia y Túnel VII (Tierra del Fuego, Argentina), analizando el registro extraido y trabajado en varias campañas de excavaciones arqueológicas en ultimos 25 años. El presente trabajo al fondo es un experimento etnoarqueológico estándar: partiendo de la observación etnográfica registramos unas recurrencias específicas entre algunas variables (por ejemplo: mujer/lugar/tipo de trabajo), intentamos extraer las variables definitorias de esas recurrencias, y finalmente las buscamos en el espacio definido arqueológicamente.  

KAM theory for conformally symplectic systems

We present a KAM theory for some dissipative systems (geometrically, these are conformally symplectic systems, i.e. systems that transform a symplectic form into a multiple of itself). For systems with n degrees of freedom depending on n parameters we show that it is possible to find solutions with n-dimensional (Diophantine) frequencies by adjusting the parameters. We do not assume that the system is close to integrable, but we use an a-posteriori format. Our unknowns are a parameterization of the solution and a parameter. We show that if there is a sufficiently approximate solution of the invariance equation, which also satisfies some explicit non–degeneracy conditions, then there is a true solution nearby. We present results both in Sobolev norms and in analytic norms. The a–posteriori format has several consequences: A) smooth dependence on the parameters, including the singular limit of zero dissipation; B) estimates on the measure of parameters covered by quasi–periodic solutions; C) convergence of perturbative expansions in analytic systems; D) bootstrap of regularity (i.e., that all tori which are smooth enough are analytic if the map is analytic); E) a numerically efficient criterion for the break–down of the quasi–periodic solutions. The proof is based on an iterative quadratically convergent method and on suitable estimates on the (analytical and Sobolev) norms of the approximate solution. The iterative step takes advantage of some geometric identities, which give a very useful coordinate system in the neighborhood of invariant (or approximately invariant) tori. This system of coordinates has several other uses: A) it shows that for dissipative conformally symplectic systems the quasi–periodic solutions are attractors, B) it leads to efficient algorithms, which have been implemented elsewhere. Details of the proof are given mainly for maps, but we also explain the slight modifications needed for flows and we devote the appendix to present explicit algorithms for flows.

L2−estimates for the DG IIPG-0 scheme

We discuss the optimality in L2 of a variant of the Incomplete Discontinuous Galerkin Interior Penalty method (IIPG) for second order linear elliptic problems. We prove optimal estimate, in two and three dimensions, for the lowest order case under suitable regularity assumptions on the data and on the mesh. We also provide numerical evidence, in one dimension, of the necessity of the regularity assumptions.

Producción y Productividad Agrícolas en la Isla de Mallorca, 1590-1860

This paper proposes a detailed measurement of the agricultural development of the island of Majorca from the late sixteenth century to the midnineteenth century, with an emphasis on the products which made up the bulk of the island’s agricultural production. The authors have organized most of the existing databases in the island’s archives and have also incorporated quantitative and qualitative material from their own research and that of other colleagues. Due to their quality and regularity, the data are among the richest known for pre-industrial Europe. These sources lead to some conclusions which link with recent debates in European economic history concerning the calculation of economic growth in economies for periods before statistics were kept. The text presents a methodological analysis covering almost 80 per cent of agricultural production of the island of Majorca and leaves conclusions to be supplemented by further studies of the manufacturing and service sectors

First price auctions: Monotonicity and uniqueness

I study monotonicity and uniqueness of the equilibrium strategies in a two-person first price auction with affiliated signals. I show thatwhen the game is symmetric there is a unique Nash equilibrium thatsatisfies a regularity condition requiring that the equilibrium strategies be{\sl piecewise monotone}. Moreover, when the signals are discrete-valued, the equilibrium is unique. The central part of the proof consists of showing that at any regular equilibrium the bidders' strategies must be monotone increasing within the support of winning bids. The monotonicity result derived in this paper provides the missing link for the analysis of uniqueness in two-person first price auctions. Importantly, this result extends to asymmetric auctions.

Manifolds on the verge of a hyperbolicity breakdown

We study numerically the disappearance of normally hyperbolic invariant tori in quasiperiodic systems and identify a scenario for their breakdown. In this scenario, the breakdown happens because two invariant directions of the transversal dynamics come close to each other, losing their regularity. On the other hand, the Lyapunov multipliers associated with the invariant directions remain more or less constant. We identify notable quantitative regularities in this scenario, namely that the minimum angle between the two invariant directions and the Lyapunov multipliers have power law dependence with the parameters. The exponents of the power laws seem to be universal.

Experiments on anisotropic radial viscous fingering

We observe dendritic patterns in fluid flow in an anisotropic Hele-Shaw cell and measure the tip shapes and trajectories of individual dendritic branches under conditions where the pattern growth appears to be dominated by surface tension anisotropy and also under conditions where kinetic effects appear dominant. In each case, the tip position depends on a power law in the time, but the exponent of this power law can vary significantly among flow realizations. Averaging many growth exponents a yields a =0.640.09 in the surface tension dominated regime and a =0.660.09 in the kinetic regime. Restricting the analysis to realizations when a is very close to 0.6 shows great regularity across pattern regimes in the coefficient of the temporal dependence of the tip trajectory.

EsPal: One-stop shopping for Spanish word properties

This article introduces EsPal: a Web-accessible repository containing a comprehensive set of properties of Spanish words. EsPal is based on an extensible set of data sources, beginning with a 300 million token written database and a 460 million token subtitle database. Properties available include word frequency, orthographic structure and neighborhoods, phonological structure and neighborhoods, and subjective ratings such as imageability. Subword structure properties are also available in terms of bigrams and trigrams, bi-phones, and bi-syllables. Lemma and part-of-speech information and their corresponding frequencies are also indexed. The website enables users to either upload a set of words to receive their properties, or to receive a set of words matching constraints on the properties. The properties themselves are easily extensible and will be added over time as they become available. It is freely available from the following website: http://www.bcbl.eu/databases/espal

Redefining dropping out in online higher education: a case study from the UOC

In recent years, studies into the reasons for dropping out of higher education (including online education) have been undertaken with greater regularity, parallel to the rise in the relative weight of this type of education, compared with brick-and-mortar education. However, the work invested in characterising the students who drop out of education, compared with those who do not, appears not to have had the same relevance as that invested in the analysis of the causes. The definition of dropping out is very sensitive to the context. In this article, we reach a purely empirical definition of student dropping out, based on the probability of not continuing a specific academic programme following several consecutive semesters of "theoretical break". Dropping out should be properly defined before analysing its causes, as well as comparing the drop-out rates between the different online programmes, or between online and on-campus ones. Our results show that there are significant differences among programmes, depending on their theoretical extension, but not their domain of knowledge.

Via-configurable transistor array: a regular design technique to improve ICs yield

Process variations are a major bottleneck for digital CMOS integrated circuits manufacturability and yield. That iswhy regular techniques with different degrees of regularity are emerging as possible solutions. Our proposal is a new regular layout design technique called Via-Configurable Transistors Array (VCTA) that pushes to the limit circuit layout regularity for devices and interconnects in order to maximize regularity benefits. VCTA is predicted to perform worse than the Standard Cell approach designs for a certain technology node but it will allow the use of a future technology on an earlier time. Ourobjective is to optimize VCTA for it to be comparable to the Standard Cell design in an older technology. Simulations for the first unoptimized version of our VCTA of delay and energy consumption for a Full Adder circuit in the 90 nm technology node are presented and also the extrapolation for Carry-RippleAdders from 4 bits to 64 bits.

EsPal: One-stop shopping for Spanish word properties

This article introduces EsPal: a Web-accessible repository containing a comprehensive set of properties of Spanish words. EsPal is based on an extensible set of data sources, beginning with a 300 million token written database and a 460 million token subtitle database. Properties available include word frequency, orthographic structure and neighborhoods, phonological structure and neighborhoods, and subjective ratings such as imageability. Subword structure properties are also available in terms of bigrams and trigrams, bi-phones, and bi-syllables. Lemma and part-of-speech information and their corresponding frequencies are also indexed. The website enables users to either upload a set of words to receive their properties, or to receive a set of words matching constraints on the properties. The properties themselves are easily extensible and will be added over time as they become available. It is freely available from the following website: http://www.bcbl.eu/databases/espal