New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D^-_k and D⁺_k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.

Broadcast anti-jamming systems

In a traditional anti-jamming system a transmitter who wants to send a signal to a single receiver spreads the signal power over a wide frequency spectrum with the aim of stopping a jammer from blocking the transmission. In this paper, we consider the case that there are multiple receivers and the transmitter wants to broadcast a message to all receivers such that colluding groups of receivers cannot jam the reception of any other receiver. We propose efficient coding methods that achieve this goal and link this problem to well-known problems in combinatorics. We also link a generalisation of this problem to the Key Distribution Pattern problem studied in combinatorial cryptography

Learning from ordered sets and applications in collaborative ranking

Ranking over sets arise when users choose between groups of items. For example, a group may be of those movies deemed 5 stars to them, or a customized tour package. It turns out, to model this data type properly, we need to investigate the general combinatorics problem of partitioning a set and ordering the subsets. Here we construct a probabilistic log-linear model over a set of ordered subsets. Inference in this combinatorial space is highly challenging: The space size approaches (N!/2)6.93145N+1 as N approaches infinity. We propose a split-and-merge Metropolis-Hastings procedure that can explore the state-space efficiently. For discovering hidden aspects in the data, we enrich the model with latent binary variables so that the posteriors can be efficiently evaluated. Finally, we evaluate the proposed model on large-scale collaborative filtering tasks and demonstrate that it is competitive against state-of-the-art methods.

The Lamination of Infinitely Renormalizable Dissipative Gap Maps: Analyticity, Holonomies and Conjugacies

Motivated by return maps near saddles for three-dimensional flows and also by return maps in the torus associated to Cherry flows, we study gap maps with derivative positive and smaller than one outside the discontinuity point. We prove that the lamination of infinitely renormalizable maps (or else maps with irrational rotation numbers) has analytic leaves in a natural subset of a Banach space of analytic maps of this kind. With maps having Hölder continuous derivative and derivative bounded away from zero, we also prove Hölder continuity of holonomies of the lamination and also of conjugacies between maps having the same combinatorics. © 2011 Springer Basel AG.

Um estudo sobre a resolução de problemas e suas relações com a afetividade

This research aims at examining the relationship between the performance of elementary school students Cycle I in problem solving and attitudes toward mathematics. For this, a research was conducted at a state school in the city of Bauru which was selected for convenience. Participants were randomly selected consisting of 75 students, of whom 21 were third years and 57 were of three classes of fifth year. The instruments used for data collection were: a informative questionnaire to characterize the students in age, grade, favorite subjects and the least liked, among others, an attitude scale, Likert type, to examine the attitudes toward mathematics; a interviews with 11 selected students according to scores on the attitudes and mathematical problems to be solved through the method of thinking aloud. The results showed that the major difficulties encountered by students in solving problems were: to understand the problems, formalizing the reasoning, recognize in the problem the algorithms needed for its resolution, make calculations with decimal numbers, do combinatorics, using the sum of equal portions instead of multiplying, self-confidence and autonomy in what he was doing, and others; participants with positive attitudes towards mathematics showed greater confidence to solve problems as well as a greater understanding on what was required by them, but were not detected significant relation between the attitudes and performance, since it was unfavorable

A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemeredi Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. (C) 2011 Elsevier B.V. All rights reserved.

Lindelof spaces which are indestructible, productive, or D

We discuss relationships in Lindelof spaces among the properties "indestructible". "productive", "D", and related properties. (C) 2011 Elsevier B.V. All rights reserved.

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

Hypergraphs with many Kneser colorings

For fixed positive integers r, k and E with 1 <= l < r and an r-uniform hypergraph H, let kappa(H, k, l) denote the number of k-colorings of the set of hyperedges of H for which any two hyperedges in the same color class intersect in at least l elements. Consider the function KC(n, r, k, l) = max(H epsilon Hn) kappa(H, k, l), where the maximum runs over the family H-n of all r-uniform hypergraphs on n vertices. In this paper, we determine the asymptotic behavior of the function KC(n, r, k, l) for every fixed r, k and l and describe the extremal hypergraphs. This variant of a problem of Erdos and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdos-Ko-Rado Theorem (Erdos et al., 1961 [8]) on intersecting systems of sets. (C) 2011 Elsevier Ltd. All rights reserved.

Rigidity for piecewise smooth homeomorphisms on the circle

We find conditions for two piecewise 'C POT.2+V' homeomorphisms f and g of the circle to be 'C POT.1' conjugate. Besides the restrictions on the combinatorics of the maps (we assume that the maps have bounded combinatorics), and necessary conditions on the one-side derivatives of points where f and g are not differentiable, we also assume zero mean-nonlinearity for f and g.

Die Rolle von Hopfkategorien und Operaden in störungstheoretischen Quantenfeldtheorien

Die Vorhersagen störungstheoretischer Quantenfeldtheorienzeigen eine gute Übereinstimmung mit experimentellgemessenen Werten. Bei diesen störungstheoretischenBerechnungen treten allerdings Ultraviolettdivergenzen auf,die keine physikalische Interpretation der Ergebnisseermöglichen. Durch Renormierung dieser Theorien erhält manjedoch berechnbare Ergebnisse mit hoher experimentellerVorhersagekraft. Der Renormierungsvorgang kann durch eineHopfalgebra, die sogenannte 'Hopfalgebra der Wurzelbäume',beschrieben werden.Die vorliegende Arbeit leistet einen Beitrag für weitereUntersuchungen dieser Hopfalgebrenstruktur und Bestimmungneuer mathematischer Methoden zur Beschreibung desRenormierungsvorgangs. Dazu wird die algebraische Strukturvon Renormierung aus der Sicht der Kategorientheorie und derTheorie von Operaden untersucht.Aus Sicht der Kategorientheorie lassen sich die den Renormierungsprozess beschreibenden mathematischen Größen ineiner Kategorie zusammenfassen. Eine additive Strukturermöglicht dabei die Berücksichtigung beliebigerRenormierungsschemata. Auf dieser Kategorie kann einassoziativitätsverletzendes Produkt definiert werden, wobeidie Verletzung durch einen sogenannten 'Assoziator'kontrolliert werden kann. Die Struktur wird auf die einerHopfkategorie erweitert, so daß eine kategorientheoretischeUntersuchung des Renormierungsprozesses ermöglicht wird.Diese Hopfkategorie wird aus Sicht von Renormierunginterpretiert, wobei Beispielrechnungen die definierteStruktur verdeutlichen.Aus algebraischer Sicht kann aufgrund der graphischenDarstellung des Operadenproduktes eine Bijektivität zwischenWurzelbäumen und Operaden gezeigt werden. Auf diesenOperaden kann wiederum eine Hopfalgebrenstruktur definiertwerden. Beispiele verdeutlichen diese Bijektivität.

Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics

Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.