The Number of Seymour Vertices in Random Tournaments and Digraphs

Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almo...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2016-09, Vol.32 (5), p.1805-1816
Main Authors: Cohn, Zachary, Godbole, Anant, Harkness, Elizabeth Wright, Zhang, Yiguang
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83
cites cdi_FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83
container_end_page 1816
container_issue 5
container_start_page 1805
container_title Graphs and combinatorics
container_volume 32
creator Cohn, Zachary
Godbole, Anant
Harkness, Elizabeth Wright
Zhang, Yiguang
description Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.
doi_str_mv 10.1007/s00373-015-1672-9
format article
fullrecord <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_1007_s00373_015_1672_9</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1007_s00373_015_1672_9</sourcerecordid><originalsourceid>FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83</originalsourceid><addsrcrecordid>eNp9kM1OwzAQhC0EEqXwANz8AoZdJ3biY1V-pQokKFwtx9m0qZqkstND3x6XcmYvK83OrDQfY7cIdwhQ3EeArMgEoBKoCynMGZtgnimhDObnbAIGMV3RXLKrGDcAoDCHCZst18Tf9l1FgQ8N_6RDN-wD_6Ywtp4ib3v-4fp66Pgy6b3rqB8jTwp_aFfB7dbxml00bhvp5m9P2dfT43L-Ihbvz6_z2UJ4WZajwMoZD5lCLZ0zSroy06BBachr5fPCS01ee6lIGUVpSpA1Nso1nnyV3FOGp78-DDEGauwutJ0LB4tgjwzsiYFNDOyRgTUpI0-ZmLz9ioLd_LbYxn9CP3D0XtM</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>The Number of Seymour Vertices in Random Tournaments and Digraphs</title><source>Springer Nature</source><creator>Cohn, Zachary ; Godbole, Anant ; Harkness, Elizabeth Wright ; Zhang, Yiguang</creator><creatorcontrib>Cohn, Zachary ; Godbole, Anant ; Harkness, Elizabeth Wright ; Zhang, Yiguang</creatorcontrib><description>Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.</description><identifier>ISSN: 0911-0119</identifier><identifier>EISSN: 1435-5914</identifier><identifier>DOI: 10.1007/s00373-015-1672-9</identifier><language>eng</language><publisher>Tokyo: Springer Japan</publisher><subject>Combinatorics ; Engineering Design ; Mathematics ; Mathematics and Statistics ; Original Paper</subject><ispartof>Graphs and combinatorics, 2016-09, Vol.32 (5), p.1805-1816</ispartof><rights>Springer Japan 2015</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83</citedby><cites>FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Cohn, Zachary</creatorcontrib><creatorcontrib>Godbole, Anant</creatorcontrib><creatorcontrib>Harkness, Elizabeth Wright</creatorcontrib><creatorcontrib>Zhang, Yiguang</creatorcontrib><title>The Number of Seymour Vertices in Random Tournaments and Digraphs</title><title>Graphs and combinatorics</title><addtitle>Graphs and Combinatorics</addtitle><description>Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.</description><subject>Combinatorics</subject><subject>Engineering Design</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Original Paper</subject><issn>0911-0119</issn><issn>1435-5914</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNp9kM1OwzAQhC0EEqXwANz8AoZdJ3biY1V-pQokKFwtx9m0qZqkstND3x6XcmYvK83OrDQfY7cIdwhQ3EeArMgEoBKoCynMGZtgnimhDObnbAIGMV3RXLKrGDcAoDCHCZst18Tf9l1FgQ8N_6RDN-wD_6Ywtp4ib3v-4fp66Pgy6b3rqB8jTwp_aFfB7dbxml00bhvp5m9P2dfT43L-Ihbvz6_z2UJ4WZajwMoZD5lCLZ0zSroy06BBachr5fPCS01ee6lIGUVpSpA1Nso1nnyV3FOGp78-DDEGauwutJ0LB4tgjwzsiYFNDOyRgTUpI0-ZmLz9ioLd_LbYxn9CP3D0XtM</recordid><startdate>20160901</startdate><enddate>20160901</enddate><creator>Cohn, Zachary</creator><creator>Godbole, Anant</creator><creator>Harkness, Elizabeth Wright</creator><creator>Zhang, Yiguang</creator><general>Springer Japan</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20160901</creationdate><title>The Number of Seymour Vertices in Random Tournaments and Digraphs</title><author>Cohn, Zachary ; Godbole, Anant ; Harkness, Elizabeth Wright ; Zhang, Yiguang</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Combinatorics</topic><topic>Engineering Design</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Original Paper</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Cohn, Zachary</creatorcontrib><creatorcontrib>Godbole, Anant</creatorcontrib><creatorcontrib>Harkness, Elizabeth Wright</creatorcontrib><creatorcontrib>Zhang, Yiguang</creatorcontrib><collection>CrossRef</collection><jtitle>Graphs and combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Cohn, Zachary</au><au>Godbole, Anant</au><au>Harkness, Elizabeth Wright</au><au>Zhang, Yiguang</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The Number of Seymour Vertices in Random Tournaments and Digraphs</atitle><jtitle>Graphs and combinatorics</jtitle><stitle>Graphs and Combinatorics</stitle><date>2016-09-01</date><risdate>2016</risdate><volume>32</volume><issue>5</issue><spage>1805</spage><epage>1816</epage><pages>1805-1816</pages><issn>0911-0119</issn><eissn>1435-5914</eissn><abstract>Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.</abstract><cop>Tokyo</cop><pub>Springer Japan</pub><doi>10.1007/s00373-015-1672-9</doi><tpages>12</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0911-0119
ispartof Graphs and combinatorics, 2016-09, Vol.32 (5), p.1805-1816
issn 0911-0119
1435-5914
language eng
recordid cdi_crossref_primary_10_1007_s00373_015_1672_9
source Springer Nature
subjects Combinatorics
Engineering Design
Mathematics
Mathematics and Statistics
Original Paper
title The Number of Seymour Vertices in Random Tournaments and Digraphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T15%3A16%3A06IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20Number%20of%20Seymour%20Vertices%20in%20Random%20Tournaments%20and%20Digraphs&rft.jtitle=Graphs%20and%20combinatorics&rft.au=Cohn,%20Zachary&rft.date=2016-09-01&rft.volume=32&rft.issue=5&rft.spage=1805&rft.epage=1816&rft.pages=1805-1816&rft.issn=0911-0119&rft.eissn=1435-5914&rft_id=info:doi/10.1007/s00373-015-1672-9&rft_dat=%3Ccrossref_sprin%3E10_1007_s00373_015_1672_9%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c288t-1ba9c035162aa952a8360605604d5c47c26ec6c25e595eeee802d1f5afcecba83%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true