Spelling suggestions: "subject:"tournoi"" "subject:"tournois""
1 |
L’incidence du rendement sur la gestion du risque au sein de l’industrie des fonds communs de placementLamoureux-Bélair, Guillaume January 2014 (has links)
D’un point de vue théorique, la délégation de la gestion au sein de l’industrie des fonds communs de placement présente un conflit d’intérêt important. Les investisseurs désirent maximiser leur rendement ajusté pour leur risque, tandis que les gestionnaires sont davantage motivés par leurs propres intérêts personnels. Le présent mémoire s’intéresse à l’incidence du rendement d’un gestionnaire sur son comportement de prise de risque. Brown al. (1996) font partie des premiers auteurs à étudier ce phénomène, qu’ils appellent l’effet tournoi. L’hypothèse de tournoi amené par ceux-ci stipule que les gestionnaires ayant connu de mauvaises performances relativement aux pairs pendant les six premiers mois d’une année sont tentés d’altérer le risque de leur portefeuille avant la fin de l’année. Leur motivation est de ne pas finir en bas du classement relatif. Notre échantillon est composé de 16 965 fonds communs de placement américains orientés croissance et petites capitalisations croissance, sur la période du 2 janvier 1996 au 31 décembre 2012. Nous testons d’abord l’hypothèse de tournoi dans notre échantillon avec des mesures de risque total et systématique ex post et ex ante, via des tables de contingence et de tests de Friedman (1920). Nous visons ainsi à confronter la littérature qui emploie majoritairement des mesures de risque réalisées, ainsi que des tables de contingence. Nos résultats montrent que le choix de la mesure de risque a une incidence importante sur les conclusions relatives à l’hypothèse de tournoi. Nous exposons par ailleurs que les gestionnaires aux rendements relatifs les plus faibles au cours des six premiers mois de l’année (les perdants) ont l’intention de hausser davantage leur risque total et systématique conditionnel au cours du dernier semestre de l’année, comparativement aux autres gestionnaires (les gagnants). Nous analysons ensuite spécifiquement le comportement des gestionnaires gagnants de fonds communs de placement. Plus précisément, nous vérifions si le risque systématique (résiduel) des fonds communs de placement se rapproche de un (zéro) suite à l’évaluation relative des gestionnaires. À cet effet, nous employons des tests de Friedman (1920) avec deux blocs temporels de deuxième période, à savoir un mois et six mois. Nos résultats exposent bien la dynamique de la prise de risque de ces gestionnaires. En outre, nos conclusions relatives au bloc temporel d’un mois sont davantage significatives et concluantes, en regard à nos hypothèses.
|
2 |
Graphes de cordes : une caractérisation et ses applicationsNaji, Walid 15 May 1985 (has links) (PDF)
Introduction. Graphes de cordes. Généralités. Diagrammes orientés. Orientations géométriques. Pseudo-tournois de cordes orientées. PL-graphes. Graphes de cordes et matroïdes binaires. Bibliographie
|
3 |
Les tribus ludiques du "LAN party" : perspectives d'apprentissage et de socialisation en contexte de compétition de jeux vidéo en réseau localDucrocq, Samuelle 01 1900 (has links) (PDF)
Cette thèse interroge le potentiel communicationnel et éducatif d'un dispositif sociotechnique événementiel, le LAN party. Elle documente depuis 2001 le constat étonnant de centaines de joueurs interrogés, disant devoir leur maîtrise de l'anglais, de l'informatique, de la réseautique, d'un esprit tactique ou sportif et leurs rapprochements avec équipiers ou adversaires devenus proches, à des compétitions de jeux vidéo. Parlerait-on d'une pratique virtuelle collective qui soit facteur d'apprentissage et de socialisation? Le LAN party est une compétition de jeux vidéo en réseau local pouvant réunir des centaines de joueurs des jours durant au même endroit. Un réseau informatique y supporte l'interconnexion de serveurs locaux à l'ordinateur que chacun apporte sur place, en vue d'organiser un tournoi par équipes s'affrontant sur des jeux multi-joueurs de stratégie et de tir. Exploratoire, ethnographique, née d'une intuition, cette étude multi-cas menée de 2001 à 2009 dans la foulée d'un constructiviste nourri du paradigme de la complexité, s'appuie sur le courant interactionniste axé sur la relation entre joueurs. Son fil conducteur est donc une interaction vue comme « un champ d'influence mutuelle » (Le Breton, 2008). Prenant la forme inductive d'une théorisation ancrée inspirée de la Grounded Theory (G laser et Strauss, 1967), elle synthétise ses conclusions dans une proposition théorique dite du « LAN pédagogique » (ou LP), comme modèle d'intervention groupale. L'étude de grands LAN québécois (2003-2007) offre des comparaisons statistiques dressant le portrait d'équipes et de joueurs interrogés issus de la génération montante des 15-25 ans. Via les rapprochements qu'il offre, le LAN incarne un rite de passage fondé sur un système tribal (Maffesoli, 2000) où le contexte compétitif favorise socialisation, apprentissage ou développement de compétences nouvelles (Brougère, 2005; Gee, 2007), dans un parallèle étonnant avec des mouvements sociaux tels que le scoutisme de Baden-Powel. Interdisciplinaire, une généalogie conceptuelle nourrie d'auteurs voyant dans l'interaction, l'assise des enjeux relationnels (Edmond et Picard, 2008), permet d'envisager la socialisation comme un construit identitaire (Piaget, 1937) et un autrui généralisé (Mead, 1934). S'y observent des patterns sociaux devenus rituels en cadre expérientiel (Goffman 1974), pour former un écosystème. En rattachant l'apprentissage à une expérience où la motivation reste l'enjeu (Vallerand 1997), dans un contexte de pratique inspiré de la théorie de l'activité selon Engestrom (1999), une modélisation systémique du LAN dévoile que l'identité du joueur se nourrit d'une socialisation introspective et évolutive par paliers, renforcée par l'expérience dite « optimale » qu'offrent les jeux vidéo (Csikszentmihalyi, 2000). Des apprentissages s'y opèrent par interactions en présence et « alteractions » en jeu, ce qui favorise introspection et feedbacks sociaux. Le modèle théorique du LP propose la superposition simultanée d'un dispositif communicationnel rassembleur dans deux mondes à la fois. Transposable à toute discipline disposant d'une salle informatique, ce type de LAN permet d'axer l'expérience immersive sur le comportement groupai et prône la création de scénarios d'apprentissage applicables à des jeux existants mais adaptés: des « mods ». En détournant l'usage de jeux en réseau populaires, le LAN peut donc mobiliser, à d'autres fins, l'intérêt de générations dont il incarne aussi langage et culture.
______________________________________________________________________________
|
4 |
Production scientifique, externalités et compétition académique : applications microéconomiques / Scientific production, externalities and academic competitionKossi, Yann 03 December 2015 (has links)
Dans un contexte où la recherche de l’excellence universitaire est au coeur des préoccupations des institutions académiques et des pouvoirs publics, cette thèse a pour objectif de contribuer à l’étude des déterminants de la production scientifique des enseignants-chercheurs français en économie. En mobilisant les données originales issues des candidatures des enseignants-chercheurs à la ‘’Prime d’Excellence Scientifique’’, les quatre contributions proposées s’attachent à articuler deux importantes dimensions, jusqu’ici rarement traitées conjointement par la littérature : les effets d’externalités collectives dans la production scientifique, et le caractère multitâche de l’activité des enseignants-chercheurs. Le premier chapitre de la thèse analyse les déterminants de l’obtention de la Prime d’Excellence Scientifique des enseignants-chercheurs français en économie. Nous nous intéressons au caractère multitâche de la production individuelle et à la dimension dynamique de cette forme particulière de compétition académique mise en place depuis 2009. Les résultats économétriques obtenus à partir d’un modèle séquentiel montrent que les publications scientifiques constituent le facteur le plus déterminant dans les chances de succès à la PES. Nous identifions les facteurs de découragement au cours de ce tournoi dynamique. Les résultats montrent également que la promotion passée au titre du précédent dispositif PEDR augmente les chances de promotion des enseignants-chercheurs. Le second chapitre se penche sur le facteur déterminant de l’attribution de la PES et de la promotion des enseignants-chercheurs : la production scientifique. Ce chapitre met en évidence que les effets d’externalités associés à l’environnement de recherche des enseignants-chercheurs sont susceptibles d’expliquer à la fois la dynamique individuelle de la production scientifique et la concentration de celle-ci entre un petit nombre d’enseignants-chercheurs. Nos résultats économétriques par quantiles concluent à l’existence de deux régimes de production scientifiques extrêmes : les polyvalents et les spécialistes. Toutefois, nos résultats ne réfutent pas l’existence d’un cycle de production scientifique qui serait sensible au stock de compétences accumulées dans l’environnement de travail des enseignants-chercheurs. Tenant compte des interactions potentielles entre les tâches d’enseignement et de recherche mises en évidence dans le second chapitre, le troisième chapitre propose d’analyser à partir d’un modèle théorique et économétrique, les effets de l’environnement de recherche sur le choix d’activités des enseignants-chercheurs. En contrôlant la simultanéité et l’endogénéité du choix des tâches de l’enseignement et de la recherche, les résultats économétriques sur nos données confortent largement les prédictions théoriques : les effets d’externalités issus de la concentration spatiale des compétences en recherche et/ou en formation à un moment donné, conduit à des profils « typés » de spécialistes (en recherche ou en formation) ou à l’opposé de « généralistes » associant production scientifique, implications pédagogiques et responsabilités collectives. Prenant en compte l’hétérogénéité des publications scientifiques en économie, le quatrième chapitre analyse des déterminants de l’arbitrage « quantité-qualité » dans la production scientifique. Nous étudions en particulier les déterminants du choix de deux types publications définies dans le classement CNRS des revues d’économie: les publications de premier rang et les publications de second rang. Les résultats économétriques de l’estimation jointe de ces deux types de publications concluent à un arbitrage entre les publications de bonne qualité et les publications dans les revues moins bien classées, arbitrage sensible aux effets d’externalité de l’environnement de recherche des enseignants-chercheurs. / In a context where both academic institutions and government consider academic excellence as crucial, this thesis aims at contributing to the study of the determinants of scientific productivity of professors. Using an original database of French academic economists involved in the “Prime d’Excellence Scientifique” tournament, the four proposed contributions show the importance of considering two dimensions often ignored so far: first, collective externalities, and the multidimensional nature of professors’ activities.The first chapter investigates the determinants of success in a large competition among French academic economists, the “Prime d’Excellence Scientifique (PES)”. We are particularly interested in the dynamic aspects of this repeated tournament initiated by the French academic system in 2009 to select the best productive researchers for promotion. The econometric estimation of the transition probabilities using sequential-response models allows for identification of changes in weightings assigned to each criterion. Our results confirm the importance of peer-reviewed publications and identify discouraging factors in this dynamic tournament. We also find that past success influences the promotion of professors.The second chapter focuses on the most decisive factor in the award of the “Prime d’Excellence Scientifique”: the scientific production. It shows that the scientific environment can explain both the path dependency in individual scientific productivity and the high inequality and skewness of individual productivity distributions. The results of quantile regressions show the existence of two separated regimes of scientific production, namely the regime of specialists and the regime of generalists. Our results also show that life-cycle effects are not only significant for the evaluation of individual productivity scores but also for the stock of knowledge accumulated in economics departments.Taking into account the potential interactions between teaching and research activities highlighted in the second chapter, the third chapter investigates the determinants of scientific production, including collective determinants related to the research environment, in the context of multitasking teachers. The chapter develops a principal-agent model to understand how university professors allocate their time between two substitutable tasks: publishing and teaching. The theoretical model predicts that professors devote more time to the tasks for which they have a marginal advantage. Controling for endogeneity activity choices, the econometric analysis confirm the key predictions ofthe model: these tasks are conflicting and the institutional context affects the activity choices of professors.Based on the heterogeneity of publication outlets, the fourth chapter analyzes the determinants of the quantity-quality tradeoff in scientific production. The focus is on the determinants of two types of publications identified by the journals ranking in Economics of the French National Committee for Scientific Research (CNRS): publications in high-quality journals and publications in low quality journals. The joint estimates of these two types of publications indicate that there is a tradeoff between the high quality publications and low quality publications, and this tradeoff is imputable to the scientific environment of professors. Our results confirm a negative impact of teaching and administrative duties on the publications in high quality journals.
|
5 |
Étude de la conjecture de Seymour sur le second voisinageGhazal, Salman 15 December 2011 (has links) (PDF)
Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale et qui convient à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions à cette conjecture. Suivant la méthode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certains cas, on trouve au moins deux sommets avec la propriété désirée.
|
6 |
Essays on the econometrics of inequality and poverty measurements / Essais à l'économétrie des mesures d'inégalité et de pauvretéNdoye, Abdoul Aziz Junior 02 July 2013 (has links)
Cette thèse est composée de quatre essais sur l'économétrie des mesures d'inégalité et de pauvreté. Elle fournit un traitement statistique fondé sur l'analyse de modèles probabilistes de mélange fini de distributions et de modèle de régression quantile, le tout dans une approche Bayésienne.Le deuxième chapitre s'intéresse à la modélisation d'une distribution de revenus par un mélange fini de lois log-normales dont les paramètres sont estimés par la méthode d'échantillonnage de Gibbs. Ce chapitre propose une méthode d'inférence statistique pour certains indices d'inégalité par une Rao-Blackwellisation de l'échantillonnage de Gibbs. Le troisième chapitre propose une estimation Bayésienne de la récente régression quantile non-conditionnelle basée sur la fonction d'influence recentrée (regression RIF) dans laquelle la densité est estimée par un mélange de lois normales. De cette approche, on déduit une inférence Bayesienne pour la méthode de décomposition d'Oaxaca-Blinder. La méthode proposée est utilisée pour analyser la dispersion des salaires aux Etats-Unis entre 1992-2009.Le quatrième chapitre propose une inférence Bayésienne d'un mélange de deux lois de Pareto simples pour modéliser la partie supérieure d'une distribution de salaires. Cette approche est utilisée pour analyser la répartition des hauts salaires aux Etats-Unis afin de tester les deux modèles (Tournoi et Superstar). Le cinquième chapitre de la thèse est consacré à l'analyse des rendements privés de l'éducation sur le revenu des ménages et des inégalités entre les populations urbaines et rurales. Il considère le cas du Sénégal et utilise les dépenses totales de consommation comme indicateur du revenu. / This dissertation consists of four essays on the econometrics of inequality and poverty measurement. It provides a statistical analysis based on probabilistic models, finite mixture distributions and quantile regression models, all using aBayesian approach.Chapter 2 models income distribution using a mixture of lognormal densities. Using the analytical expression of inequality indices, it shows how a Rao-Blackwellised Gibbs sampler can lead to accurate inference on income inequality measurements even in small samples.Chapter 3 develops Bayesian inference for the unconditional quantile regression model based on the Re-centered Influence Function (RIF). It models the considered distribution by a mixture of lognormal densities and then provides conditional posterior densities for the quantile regression parameters. This approach is perceived to provide better estimates in the extreme quantiles in the presence of heavy tails as well as valid small sample confidence intervalsfor the Oaxaca-Blinder decomposition.Chapter 4 provides Bayesian inference for a mixture of two Pareto distributions which is then used to approximate the upper tail of a wage distribution. This mixture model is applied to the data from the CPS ORG to analyze the recent structure of top wages in the U.S. from 1992 through 2009. Findings are largely in accordance with the explanations combining the model of superstars and the model of tournaments in hierarchical organization structures. Chapter 5 makes use of the RIF-regression to measure both changes in the return to education across quantiles and rural urban inequality decomposition in consumption expenditure in Senegal.
|
7 |
Chevaliers et hommes d'armes dans l'espace bourguignon au XVe siècle / Knights and men-at-arms in the Burgundian territories in the 15th centuryForster, Lois 07 December 2018 (has links)
Chacun de leur côté, les phénomènes de la guerre et des tournois au Moyen Âge ont déjà bénéficié d’études nombreuses et approfondies. En revanche, on a négligé d’analyser en profondeur le lien entre ces deux mondes, accusé pourtant de s’étioler au XVe siècle au profit de spectacles grandioses n’ayant plus rien à voir avec la réalité d’un champ de bataille. Par ailleurs, dans le domaine militaire, les gentilshommes imprégnés d’un idéal chevaleresque obsolète se débattraient pour essayer de faire encore croire au maintien de leur suprématie guerrière.La réalité est bien plus complexe et les interactions entre le domaine de la guerre et celui des lices sont multiples. Ce sont d’abord les mêmes personnes qu’on peut retrouver à combattre dans tous les contextes, des hommes censés être nobles, adoubés ou non, qui possèdent un équipement caractéristique, armes et armures, ainsi qu’un cheval entraîné au combat. Les adaptations de leur matériel aux rencontres normées, prévues pour augmenter leur sécurité, ne changent fondamentalement rien à leur façon de combattre. Leurs techniques martiales se révèlent riches et variées, tout comme leurs tactiques collectives, qui savent s’adapter aux différentes configurations rencontrées à la guerre grâce à une surprenante polyvalence. Enfin, la mentalité avec laquelle les hommes d’armes abordent les rencontres armées montrent d’importantes similitudes dans tous les contextes : on attend d’eux qu’ils donnent le meilleur d’eux-mêmes, en démontrant leur prouesse, sans renoncer face à l’adversité. Ainsi, à tous les niveaux, la frontière entre les lices et le champ de bataille s’avère finalement assez floue. / The phenomena of war and tournaments in the Middle Ages have already benefitted from several individual in-depth studies. However, a detailed analysis of the link between the two themes has always been lacking, even though we often accusingly claim that this link declined during the 15th century to be replaced by spectacular shows which had nothing to do with the reality of battlefields anymore. Moreover, some people would argue that, in the military field, noblemen – immersed in an obsolete chivalrous model – would have desperately tried to maintain a semblance of belligerent dominion.But the truth is far more complex and the interactions between the world of war and the world of lists are numerous. First, the same persons could be found in each context: men supposed to be noble – knighted or not – with characteristic pieces of equipment – arms and armours – and horses trained for combat. Adjusting their equipment for formal combats to improve their safety did not fundamentally change the way they fought. Their martial techniques were, in fact, rich and diverse – and so was their group tactic, which could adapt to different configurations encountered at war thanks to their surprising versatility. Lastly, the ways of men-at-arms in martial encounters reveals important similarities in every context: we expected them to give their best and achieve feats with no sign of renouncement while facing the enemy. Thus, the boundary between lists and battlefields actually turns out to be quite vague at every level.
|
8 |
Étude de la conjecture de Seymour sur le second voisinage / A study of Seymour's second neighborhood conjectureGhazal, Salman 15 December 2011 (has links)
Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale et qui convient à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions à cette conjecture. Suivant la méthode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certains cas, on trouve au moins deux sommets avec la propriété désirée. / Let D be a digraph without digons (directed cycles of length 2). In 1990, Seymour [1] conjectured that D has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). This conjecture is known as the second neighborhood conjecture (SNC). This conjecture, if true, would imply a weakening of a particular case (but important) of a long standing conjecture proposed by Caccetta and H aggkvist in 1978, which states that every digraph D with minimum out-degree at least jV (D)j=k has a directed cycle of length at most k. The special case is when k = 3 and the weakening requires both minimum out-degree and minimum in-degree at least jV (D)j=k [2]. Seymour's conjecture restricted to tournaments is known as Dean's conjecture [1]. In 1996, Fisher [3] gave a probabilistic proof to Dean's conjecture. In 2003 Chen, Shen and Yuster [4] proved that every digraph contains a vertex v such that d+(v) _ d++(v), where = 0:657298::: is the unique real root of the equation 2x3 + x2 1 = 0. In 2000, another proof of Dean's conjecture was given by Havet and Thomassé using a tool called median order [5]. They proved that the last vertex of this order, called a feed vertex, has second out-neighborhood at least as large as its first out-neighborhood. Median order is found to be a useful tool not only for the class of tournaments but for other classes of digraphs. In 2007, Fidler and Yuster [6] used also median orders to prove Seymour's conjecture for the class of digraphs with minimum degree jV (D)j 2 (i.e. D is a digraph missing a matching) and tournaments minus another subtournament. El Sahili conjectured that for every digraph D there is a completion T of D and a median order of T whose feed vertex has the SNP in D. Clearly, El Sahili's conjecture (EC) implies SNC. However, as one can observe, EC suggests a method (an approach) for solving the SNC, which we will call the completion approach. In general, following this approach, we orient the missing edges of D in some 'proper' way, to obtain a tournament T. Then we consider a particular feed vertex (clearly, it has the SNP in T) and try to prove that it has the SNP in D as well. Clearly, the result of Havet and Thomassé shows that EC is true for tournaments and the result of Fidler and Yuster [6] shows that EC holds for tournaments minus another subtournament. We will verify EC for the class 1 of tournaments missing a matching. So EC is verified for all the classes of digraphs where the SNC is known to hold non trivially. We will be interested also in the weighted version of EC and SNC. In reality, Fidler and Yuster [6] used dependency digraphs as a supplementary tool for proving the SNC for digraphs missing a matching and the fact that the weighted SNC holds for tournaments. We define dependency digraphs in a more general way, which is suitable to any digraph, and use them in our contribution to Seymour's conjecture. We also use the median order as a tool in our contribution. Using these two tools, and following the completion approach, we prove the weighted version of EC, and consequently the SNC, for several classes of digraphs: Digraphs missing a generalized star, sun, star or a complete graph. In addition, we prove EC, and consequently the SNC for digraphs missing a comb, and digraphs whose missing graph is a complete graph minus two independent edges or the edges of a cycle of length five. Moreover, we prove it for digraphs missing n disjoint stars under some conditions. Weaker conditions are required for n = 1; 2; 3. In some cases, we exhibit at least two vertices with the SNP.
|
Page generated in 0.0915 seconds