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.

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.

New genetic loci link adipose and insulin biology to body fat distribution

Body fat distribution is a heritable trait and a well-established predictor of adverse metabolic outcomes, independent of overall adiposity. To increase our understanding of the genetic basis of body fat distribution and its molecular links to cardiometabolic traits, here we conduct genome-wide association meta-analyses of traits related to waist and hip circumferences in up to 224,459 individuals. We identify 49 loci (33 new) associated with waist-to-hip ratio adjusted for body mass index (BMI), and an additional 19 loci newly associated with related waist and hip circumference measures (P < 5 × 10−8). In total, 20 of the 49 waist-to-hip ratio adjusted for BMI loci show significant sexual dimorphism, 19 of which display a stronger effect in women. The identified loci were enriched for genes expressed in adipose tissue and for putative regulatory elements in adipocytes. Pathway analyses implicated adipogenesis, angiogenesis, transcriptional regulation and insulin resistance as processes affecting fat distribution, providing insight into potential pathophysiological mechanisms.

Association analyses of 249,796 individuals reveal 18 new loci associated with body mass index

Obesity is globally prevalent and highly heritable, but its underlying genetic factors remain largely elusive. To identify genetic loci for obesity susceptibility, we examined associations between body mass index and approximately 2.8 million SNPs in up to 123,865 individuals with targeted follow up of 42 SNPs in up to 125,931 additional individuals. We confirmed 14 known obesity susceptibility loci and identified 18 new loci associated with body mass index (P < 5 x 10(-)(8)), one of which includes a copy number variant near GPRC5B. Some loci (at MC4R, POMC, SH2B1 and BDNF) map near key hypothalamic regulators of energy balance, and one of these loci is near GIPR, an incretin receptor. Furthermore, genes in other newly associated loci may provide new insights into human body weight regulation.

Meta-analysis identifies 13 new loci associated with waist-hip ratio and reveals sexual dimorphism in the genetic basis of fat distribution

Waist-hip ratio (WHR) is a measure of body fat distribution and a predictor of metabolic consequences independent of overall adiposity. WHR is heritable, but few genetic variants influencing this trait have been identified. We conducted a meta-analysis of 32 genome-wide association studies for WHR adjusted for body mass index (comprising up to 77,167 participants), following up 16 loci in an additional 29 studies (comprising up to 113,636 subjects). We identified 13 new loci in or near RSPO3, VEGFA, TBX15-WARS2, NFE2L3, GRB14, DNM3-PIGC, ITPR2-SSPN, LY86, HOXC13, ADAMTS9, ZNRF3-KREMEN1, NISCH-STAB1 and CPEB4 (P = 1.9 × 10−9 to P = 1.8 × 10−40) and the known signal at LYPLAL1. Seven of these loci exhibited marked sexual dimorphism, all with a stronger effect on WHR in women than men (P for sex difference = 1.9 × 10−3 to P = 1.2 × 10−13). These findings provide evidence for multiple loci that modulate body fat distribution independent of overall adiposity and reveal strong gene-by-sex interactions.

Remark on factorials that are products of factorials

In a paper published in 1993, Erdos proved that if n! = a! b!, where 1 < a a parts per thousand currency sign b, then the difference between n and b does not exceed 5 log log n for large enough n. In the present paper, we improve this upper bound to ((1 + epsilon)/ log 2) log log n and generalize it to the equation a (1)!a (2)! ... a (k) ! = n!. In a recent paper, F. Luca proved that n - b = 1 for large enough n provided that the ABC-hypothesis holds.

Sustaining cooperation on networks: an analytical study based on evolutionary game theory

We analytically study the role played by the network topology in sustaining cooperation in a society of myopic agents in an evolutionary setting. In our model, each agent plays the Prisoner's Dilemma (PD) game with its neighbors, as specified by a network. Cooperation is the incumbent strategy, whereas defectors are the mutants. Starting with a population of cooperators, some agents are switched to defection. The agents then play the PD game with their neighbors and compute their fitness. After this, an evolutionary rule, or imitation dynamic is used to update the agent strategy. A defector switches back to cooperation if it has a cooperator neighbor with higher fitness. The network is said to sustain cooperation if almost all defectors switch to cooperation. Earlier work on the sustenance of cooperation has largely consisted of simulation studies, and we seek to complement this body of work by providing analytical insight for the same. We find that in order to sustain cooperation, a network should satisfy some properties such as small average diameter, densification, and irregularity. Real-world networks have been empirically shown to exhibit these properties, and are thus candidates for the sustenance of cooperation. We also analyze some specific graphs to determine whether or not they sustain cooperation. In particular, we find that scale-free graphs belonging to a certain family sustain cooperation, whereas Erdos-Renyi random graphs do not. To the best of our knowledge, ours is the first analytical attempt to determine which networks sustain cooperation in a population of myopic agents in an evolutionary setting.

Lovasz theta function, SVMs and Finding Dense Subgraphs

In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

Percolation on networks with antagonistic and dependent interactions

Drawing inspiration from real world interacting systems, we study a system consisting of two networks that exhibit antagonistic and dependent interactions. By antagonistic and dependent interactions we mean that a proportion of functional nodes in a network cause failure of nodes in the other, while failure of nodes in the other results in failure of links in the first. In contrast to interdependent networks, which can exhibit first-order phase transitions, we find that the phase transitions in such networks are continuous. Our analysis shows that, compared to an isolated network, the system is more robust against random attacks. Surprisingly, we observe a region in the parameter space where the giant connected components of both networks start oscillating. Furthermore, we find that for Erdos-Renyi and scale-free networks the system oscillates only when the dependence and antagonism between the two networks are very high. We believe that this study can further our understanding of real world interacting systems.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Campaigning in Heterogeneous Social Networks: Optimal Control of SI Information Epidemics

We study the optimal control problem of maximizing the spread of an information epidemic on a social network. Information propagation is modeled as a susceptible-infected (SI) process, and the campaign budget is fixed. Direct recruitment and word-of-mouth incentives are the two strategies to accelerate information spreading (controls). We allow for multiple controls depending on the degree of the nodes/individuals. The solution optimally allocates the scarce resource over the campaign duration and the degree class groups. We study the impact of the degree distribution of the network on the controls and present results for Erdos-Renyi and scale-free networks. Results show that more resource is allocated to high-degree nodes in the case of scale-free networks, but medium-degree nodes in the case of Erdos-Renyi networks. We study the effects of various model parameters on the optimal strategy and quantify the improvement offered by the optimal strategy over the static and bang-bang control strategies. The effect of the time-varying spreading rate on the controls is explored as the interest level of the population in the subject of the campaign may change over time. We show the existence of a solution to the formulated optimal control problem, which has nonlinear isoperimetric constraints, using novel techniques that is general and can be used in other similar optimal control problems. This work may be of interest to political, social awareness, or crowdfunding campaigners and product marketing managers, and with some modifications may be used for mitigating biological epidemics.

Comparing the sustainability of an innovative dry sanitation (Ecosan) system in China to a conventional waterborne sanitation system

The use of sustainability indicators for evaluating sanitation systems is applied to the Erdos Eco- Town Project (EETP) in China for illustration. The EETP is the largest urban settlement in the world employing ecological sanitation, which incorporates separation of waste streams, dry toilets, and resource recovery. The EETP’s dry sanitation system is compared against the Dongsheng District’s conventional sewer and centralised STP. The two systems are compared based on technological, environmental, economic, and societal indicators. Overall, the two systems perform reasonably well from a technological perspective. The conventional system performs significantly better than the dry system with regards to land and energy requirements, and global warming potential; it also performs better based on freshwater aquatic and terrestrial ecotoxicity potentials, but by a smaller margin. The dry system has superior environmental performance based on water consumption, eutrophication potential, and nutrient and organic matter recovery. The dry system is a more costly system as it requires greater infrastructure and higher operational costs, and does not benefit from economies of scale. The waterborne system performs better based on the societal indicators largely because it is a well-established system.

鄂尔多斯植物遥感光谱及植被分布特征

本研究通过对鄂尔多斯（主要为毛乌素地区）植物遥感光谱和土壤结皮光谱的测定，通过专题资料搜集、野外踏查、植被样方调查和室内盆栽试验和实验室分析等工作，利用遥感和地理信息系统技术，测定了研究区主要植物光谱和土壤结皮光谱，建立了研究区生态环境本底数据库，在以上的基础上，进行了3方面的详细研究： （1） 通过野外样方调查，野外和室内培养的生物结皮的地面高光谱测定和野外典型地物（鄂尔多斯地区优势高等植物种和沙地土壤）的高光谱测定。采用人工模拟降雨，从苔藓休眠-正常代谢-休眠过程中，研究苔藓土壤结皮的光谱变化，得出苔藓结皮在夏季的生命活动期（正常代谢）的光谱曲线具有高等植物光谱曲线特征;不同地物的NDVI在降水前后变化：苔藓结皮NDVI的变化为0.3-0.35左右，藻类结皮变化为0.15左右，100%盖度的油蒿变化约为0.03左右，而土壤物理结皮的NDVI变化为0.06-0.08左右，可见降水对结皮的归一化植被指数的影响较土壤和高等植被大的多，对苔藓结皮的影响尤其显著。 通过线性模型研究了生物结皮对区域植被遥感解译的影响：模拟得出调查区域（11km样线）由于干湿结皮的变换， NDVI值平均变化0.03， 苔藓湿时的NDVI较苔藓干时相对提高9.3%。可见在研究区，由于苔藓结皮等土壤结皮的存在和干旱半干旱区降雨的不稳定性，必然造成该区域短时间内NDVI的不稳定性。研究结果可为如何结合苔藓结皮的高光谱特征及其变化规律选择和研究合适的生物结皮（苔藓）遥感解译方法提供借鉴。 （2）通过对1980S,1990s,2000s三个时期遥感图像解译，分析了毛乌素沙地沙漠化过程及其驱动机制，认为毛乌素沙地近20年来沙漠化程度有所减轻，植被覆盖有所增加。气候因素和人为因素是导致植被覆盖增加的决定因素，通过多元回归分析确定降水和温度是影响毛乌素沙地植被变化的关键气候因子，并建立了相应的回归方程;人为因素的影响表现在20年来农田和林地的大面积增加。 （3）在建立研究区生态环境本底数据库的基础上，利用遥感解译结果和地理信息系统的空间分析功能，分析了气候因素、地质水文因素、地形和地貌等对植被分布的影响，得出在不同尺度上，影响植被分布的关键因素不同。在鄂尔多斯研究区，区域年降水量对全区的植被分布有着重要影响，尽管地质水文条件的不同也影响了小区域的植被分布。在毛乌素沙地区，在宏观尺度上（旗县），植被分布与其所处的海拔高度关系不明显，在小尺度上，植被分布表现出趋向于相对低海拔分布;小尺度研究中发现，植被分布受地形和基质岩性的组合的综合影响。