Droites sur les hypergraphes

Le Théorème de Sylvester-Gallai affirme que dans un ensemble fini S de points dans le plan, où les points ne sont pas tous sur une même droite, il y a une droite qui passe par exactement deux points de S. Chvátal [14] a étendu la notion de droites aux espaces métriques arbitraires et a fait une conjecture généralisant le Théorème de Sylvester-Gallai. Chen [10] a démontré cette conjecture qui s’appelle maintenant le Théorème de Sylvester-Chvátal. En 1943, Erdos [18] a remarqué un corollaire pour le Théorème de Sylvester-Gallai affirmant que, dans un ensemble fini V de points dans le plan, où les points ne sont pas tous sur une droite, le nombre de droites qui passent par au moins deux points de V est au moins |V |. De Bruijn et Erdos [7] ont généralisé ce corollaire, en utilisant une définition généralisée de droite (voir Chapitre 2) et ont prouvé que tout ensemble de n points, où les points ne sont pas tous sur une même droite, détermine au moins n droites distinctes. Dans le présent mémoire, nous allons étudier les théorèmes mentionnés ci-dessus. Nous allons aussi considérer le Théorème de De Bruijn-Erdos dans le cadre des hypergraphes et des espaces métriques.

Review of de Bruijn, M., F. Nyamnjoh and I. Brinkman (eds.). 2009. Mobile phones : the new talking drums of everyday Africa

Since the late 1990s, there has been great enthusiasm expressed about the positive impact that can be obtained for poor and disadvantaged people from information and communication technologies (ICTs). This school of thought among researchers and practitioners is identified as ICTs for development (ICT4D). By contrast, a growing number of researchers eschew the technologically deterministic nature of the claims being made for development progress and seek to understand the role of technology in people’s lives, primarily through ethnographic studies. This book, which focuses on mobile telephony on the African continent, fits into the latter body of literature, with several authors explicitly stating they are examining social and cultural settings and are not taking a technologically deterministic view. The book captures the diverse ways various communities are using this communication technology. It adds to the burgeoning field of mobile phone studies, in which an increasing number of studies is emerging from developing countries.

High-Throughput Flexible Constraint Length Viterbi Decoders on De Bruijn, Shuffle-Exchange and Butterfly Connected Architectures

Flexible constraint length channel decoders are required for software defined radios. This paper presents a novel scalable scheme for realizing flexible constraint length Viterbi decoders on a de Bruijn interconnection network. Architectures for flexible decoders using the flattened butterfly and shuffle-exchange networks are also described. It is shown that these networks provide favourable substrates for realizing flexible convolutional decoders. Synthesis results for the three networks are provided and a comparison is performed. An architecture based on a 2D-mesh, which is a topology having a nominally lesser silicon area requirement, is also considered as a fourth point for comparison. It is found that of all the networks considered, the de Bruijn network offers the best tradeoff in terms of area versus throughput.

Realizing a flexible constraint length Viterbi decoder for software radio on a de Bruijn interconnection network

Building flexible constraint length Viterbi decoders requires us to be able to realize de Bruijn networks of various sizes on the physically provided interconnection network. This paper considers the case when the physical network is itself a de Bruijn network and presents a scalable technique for realizing any n-node de Bruijn network on an N-node de Bruijn network, where n < N. The technique ensures that the length of the longest path realized on the network is minimized and that each physical connection is utilized to send only one data item, both of which are desirable in order to reduce the hardware complexity of the network and to obtain the best possible performance.

On the Erdos-Szekeres n-interior point problem

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

On the Erdos-Szekeres n-interior-point problem

The n-interior-point variant of the Erdos Szekeres problem is the following: for every n, n >= 1, does there exist a g(n) such that every point set in the plane with at least g(n) interior points has a convex polygon containing exactly n interior points. The existence of g(n) has been proved only for n <= 3. In this paper, we show that for any fixed r >= 2, and for every n >= 5, every point set having sufficiently large number of interior points and at most r convex layers contains a subset with exactly n interior points. We also consider a relaxation of the notion of convex polygons and show that for every n, n >= 1, any point set with at least n interior points has an almost convex polygon (a simple polygon with at most one concave vertex) that contains exactly n interior points. (C) 2013 Elsevier Ltd. All rights reserved.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Comparison of K-ary N-cube and de Bruijn Overlays in QoS-Constrained Multicast Applications

Research on the construction of logical overlay networks has gained significance in recent times. This is partly due to work on peer-to-peer (P2P) systems for locating and retrieving distributed data objects, and also scalable content distribution using end-system multicast techniques. However, there are emerging applications that require the real-time transport of data from various sources to potentially many thousands of subscribers, each having their own quality-of-service (QoS) constraints. This paper primarily focuses on the properties of two popular topologies found in interconnection networks, namely k-ary n-cubes and de Bruijn graphs. The regular structure of these graph topologies makes them easier to analyze and determine possible routes for real-time data than complete or irregular graphs. We show how these overlay topologies compare in their ability to deliver data according to the QoS constraints of many subscribers, each receiving data from specific publishing hosts. Comparisons are drawn on the ability of each topology to route data in the presence of dynamic system effects, due to end-hosts joining and departing the system. Finally, experimental results show the service guarantees and physical link stress resulting from efficient multicast trees constructed over both kinds of overlay networks.

A new optimised De Bruijn coding strategy for structured light patterns

Coded structured light is an optical technique based on active stereovision that obtains the shape of objects. One shot techniques are based on projecting a unique light pattern with an LCD projector so that grabbing an image with a camera, a large number of correspondences can be obtained. Then, a 3D reconstruction of the illuminated object can be recovered by means of triangulation. The most used strategy to encode one-shot patterns is based on De Bruijn sequences. In This work a new way to design patterns using this type of sequences is presented. The new coding strategy minimises the number of required colours and maximises both the resolution and the accuracy

Grafi aleatori - il modello di Erdos-Rényi

Dopo aver dato una definizione formale per il modello di Erdos-Rényi, si dimostra che in un grafo ER il grado dei nodi (misura della connessione) risulta essere una variabile aleatoria con distribuzione binomiale, mentre il clustering (misura della densità di archi a livello locale) tende a zero. Successivamente si determinano le funzioni soglia per alcune proprietà monotone particolarmente significative, consentendo così di descrivere diverse configurazioni possibili per un grafo ER al variare dei suoi parametri. Infine, si mostra come si possano utilizzare i grafi ER per modellizzare la diffusione di una malattia infettiva all’interno di una popolazione numerosa.

Assemblage d’ADN avec graphes de de Bruijn sur FPGA

Ce mémoire est consacré à la parallélisation d’un algorithme d’assemblage d’ADN de type de novo sur différentes plateformes matérielles, soit les processeurs multicoeurs et les accélérateurs de type FPGA. Plus précisément, le langage OpenCL est utilisé pour accélérer l’algorithme dont il est question, et de permettre un comparatif direct entre les les plateformes. Cet algorithme est d’abord introduit, puis son implémentation originale, développée pour une exécution sur une grappe de noeuds, est discutée. Les modifications apportées à l’algorithme dans le but de faciliter la parallélisation sont ensuite divulgées. Ensuite, le coeur du travail est présenté, soit la programmation utilisant OpenCL. Finalement, les résultats sont présentés et discutés.

Smart material interfaces : a new form of physical interaction

Smart Material Interface (SMI) is the latest generation of user interface that makes use of engineered materials and leverages their special properties. SMIs are capable of changing their physical properties such as shape, size and color, and can be controlled under certain (external) conditions. We provide an example of such an SMI in the form of a prototype of a vacuum cleaner. The prototype uses schematic electrochromic polymer at the suction nozzle of the vacuum cleaner, which changes its color depending on the dust level on a floor. We emphasize on the new affordances and communication language supported by SMIs, which challenges the current metaphors of user interfaces in the field of HCI.

Cardiometabolic effects of genetic upregulation of the interleukin 1 receptor antagonist: A Mendelian randomisation analysis

Background To investigate potential cardiovascular and other effects of long-term pharmacological interleukin 1 (IL-1) inhibition, we studied genetic variants that produce inhibition of IL-1, a master regulator of inflammation. Methods We created a genetic score combining the effects of alleles of two common variants (rs6743376 and rs1542176) that are located upstream of IL1RN, the gene encoding the IL-1 receptor antagonist (IL-1Ra; an endogenous inhibitor of both IL-1α and IL-1β); both alleles increase soluble IL-1Ra protein concentration. We compared effects on inflammation biomarkers of this genetic score with those of anakinra, the recombinant form of IL-1Ra, which has previously been studied in randomised trials of rheumatoid arthritis and other inflammatory disorders. In primary analyses, we investigated the score in relation to rheumatoid arthritis and four cardiometabolic diseases (type 2 diabetes, coronary heart disease, ischaemic stroke, and abdominal aortic aneurysm; 453 411 total participants). In exploratory analyses, we studied the relation of the score to many disease traits and to 24 other disorders of proposed relevance to IL-1 signalling (746 171 total participants). Findings For each IL1RN minor allele inherited, serum concentrations of IL-1Ra increased by 0·22 SD (95% CI 0·18–0·25; 12·5%; p=9·3 × 10−33), concentrations of interleukin 6 decreased by 0·02 SD (−0·04 to −0·01; −1·7%; p=3·5 × 10−3), and concentrations of C-reactive protein decreased by 0·03 SD (−0·04 to −0·02; −3·4%; p=7·7 × 10−14). We noted the effects of the genetic score on these inflammation biomarkers to be directionally concordant with those of anakinra. The allele count of the genetic score had roughly log-linear, dose-dependent associations with both IL-1Ra concentration and risk of coronary heart disease. For people who carried four IL-1Ra-raising alleles, the odds ratio for coronary heart disease was 1·15 (1·08–1·22; p=1·8 × 10−6) compared with people who carried no IL-1Ra-raising alleles; the per-allele odds ratio for coronary heart disease was 1·03 (1·02–1·04; p=3·9 × 10−10). Per-allele odds ratios were 0·97 (0·95–0·99; p=9·9 × 10−4) for rheumatoid arthritis, 0·99 (0·97–1·01; p=0·47) for type 2 diabetes, 1·00 (0·98–1·02; p=0·92) for ischaemic stroke, and 1·08 (1·04–1·12; p=1·8 × 10−5) for abdominal aortic aneurysm. In exploratory analyses, we observed per-allele increases in concentrations of proatherogenic lipids, including LDL-cholesterol, but no clear evidence of association for blood pressure, glycaemic traits, or any of the 24 other disorders studied. Modelling suggested that the observed increase in LDL-cholesterol could account for about a third of the association observed between the genetic score and increased coronary risk. Interpretation Human genetic data suggest that long-term dual IL-1α/β inhibition could increase cardiovascular risk and, conversely, reduce the risk of development of rheumatoid arthritis. The cardiovascular risk might, in part, be mediated through an increase in proatherogenic lipid concentrations. Funding UK Medical Research Council, British Heart Foundation, UK National Institute for Health Research, National Institute for Health Research Cambridge Biomedical Research Centre, European Research Council, and European Commission Framework Programme 7.

Common variants at 12q14 and 12q24 are associated with hippocampal volume

Aging is associated with reductions in hippocampal volume that are accelerated by Alzheimer's disease and vascular risk factors. Our genome-wide association study (GWAS) of dementia-free persons (n = 9,232) identified 46 SNPs at four loci with P values of <4.0 × 10 -7. In two additional samples (n = 2,318), associations were replicated at 12q14 within MSRB3-WIF1 (discovery and replication; rs17178006; P = 5.3 × 10 -11) and at 12q24 near HRK-FBXW8 (rs7294919; P = 2.9 × 10 -11). Remaining associations included one SNP at 2q24 within DPP4 (rs6741949; P = 2.9 × 10 -7) and nine SNPs at 9p33 within ASTN2 (rs7852872; P = 1.0 × 10 -7); along with the chromosome 12 associations, these loci were also associated with hippocampal volume (P < 0.05) in a third younger, more heterogeneous sample (n = 7,794). The SNP in ASTN2 also showed suggestive association with decline in cognition in a largely independent sample (n = 1,563). These associations implicate genes related to apoptosis (HRK), development (WIF1), oxidative stress (MSR3B), ubiquitination (FBXW8) and neuronal migration (ASTN2), as well as enzymes targeted by new diabetes medications (DPP4), indicating new genetic influences on hippocampal size and possibly the risk of cognitive decline and dementia.