Cover Image

Seymour's second neighbourhood conjecture: random graphs and reductions

A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short note we show that, for any fixed p∈[0,1/2)\ pın łeft[0,1/2\right) \, a.a.s. every orientation of G(n,p)\ Głeft(n,p\righ...

Full description

Saved in:
Bibliographic Details
Main Authors: Espuny Díaz, Alberto (Author) , Girão, António (Author) , Granet, Bertille (Author) , Kronenberg, Gal (Author)
Format: Article (Journal)
Language:English
Published: January 2025
In: Random structures & algorithms
Year: 2025, Volume: 66, Issue: 1, Pages: 1-12
ISSN:1098-2418
DOI:10.1002/rsa.21251
Online Access:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.21251
Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21251
Get full text
Author Notes:Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg

MARC

LEADER 00000caa a2200000 c 4500
001 1920856897
003 DE-627
005 20250717003637.0
007 cr uuu---uuuuu
008 250331s2025 xx |||||o 00| ||eng c
024 7 |a 10.1002/rsa.21251  |2 doi 
035 |a (DE-627)1920856897 
035 |a (DE-599)KXP1920856897 
035 |a (OCoLC)1528043768 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 28  |2 sdnb 
100 1 |a Espuny Díaz, Alberto  |e VerfasserIn  |0 (DE-588)1229848681  |0 (DE-627)1752024702  |4 aut 
245 1 0 |a Seymour's second neighbourhood conjecture  |b random graphs and reductions  |c Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg 
264 1 |c January 2025 
300 |a 12 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Erstveröffentlichung: 7. August 2024 
500 |a Gesehen am 31.03.2025 
520 |a A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short note we show that, for any fixed p∈[0,1/2)\ pın łeft[0,1/2\right) \, a.a.s. every orientation of G(n,p)\ Głeft(n,p\right) \ satisfies Seymour's conjecture (as well as a related conjecture of Sullivan). This improves on a recent result of Botler, Moura and Naia. Moreover, we show that p=1/2\ p=1/2 \ is a natural barrier for this problem, in the following sense: for any fixed p∈(1/2,1)\ pın łeft(1/2,1\right) \, Seymour's conjecture is actually equivalent to saying that, with probability bounded away from 0, every orientation of G(n,p)\ Głeft(n,p\right) \ satisfies Seymour's conjecture. This provides a first reduction of the problem. For a second reduction, we consider minimum degrees and show that, if Seymour's conjecture is false, then there must exist arbitrarily large strongly-connected counterexamples with bounded minimum outdegree. Contrasting this, we show that vertex-minimal counterexamples must have large minimum outdegree. 
650 4 |a oriented graphs 
650 4 |a random graphs 
650 4 |a second neighbourhood conjecture 
700 1 |a Girão, António  |e VerfasserIn  |4 aut 
700 1 |a Granet, Bertille  |e VerfasserIn  |0 (DE-588)1274018277  |0 (DE-627)1823726569  |4 aut 
700 1 |a Kronenberg, Gal  |e VerfasserIn  |4 aut 
773 0 8 |i Enthalten in  |t Random structures & algorithms  |d New York, NY [u.a.] : Wiley, 1990  |g 66(2025), 1 vom: Jan., Artikel-ID e21251, Seite 1-12  |h Online-Ressource  |w (DE-627)306711141  |w (DE-600)1500812-5  |w (DE-576)082436185  |x 1098-2418  |7 nnas  |a Seymour's second neighbourhood conjecture random graphs and reductions 
773 1 8 |g volume:66  |g year:2025  |g number:1  |g month:01  |g elocationid:e21251  |g pages:1-12  |g extent:12  |a Seymour's second neighbourhood conjecture random graphs and reductions 
856 4 0 |u https://doi.org/10.1002/rsa.21251  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21251  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20250331 
993 |a Article 
994 |a 2025 
998 |g 1274018277  |a Granet, Bertille  |m 1274018277:Granet, Bertille  |d 110000  |d 110300  |e 110000PG1274018277  |e 110300PG1274018277  |k 0/110000/  |k 1/110000/110300/  |p 3 
998 |g 1229848681  |a Espuny Díaz, Alberto  |m 1229848681:Espuny Díaz, Alberto  |d 110000  |d 110300  |e 110000PE1229848681  |e 110300PE1229848681  |k 0/110000/  |k 1/110000/110300/  |p 1  |x j 
999 |a KXP-PPN1920856897  |e 469552399X 
BIB |a Y 
SER |a journal 
JSO |a {"recId":"1920856897","language":["eng"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Erstveröffentlichung: 7. August 2024","Gesehen am 31.03.2025"],"title":[{"title":"Seymour's second neighbourhood conjecture","subtitle":"random graphs and reductions","title_sort":"Seymour's second neighbourhood conjecture"}],"person":[{"family":"Espuny Díaz","given":"Alberto","roleDisplay":"VerfasserIn","display":"Espuny Díaz, Alberto","role":"aut"},{"family":"Girão","given":"António","display":"Girão, António","roleDisplay":"VerfasserIn","role":"aut"},{"given":"Bertille","family":"Granet","role":"aut","display":"Granet, Bertille","roleDisplay":"VerfasserIn"},{"given":"Gal","family":"Kronenberg","role":"aut","display":"Kronenberg, Gal","roleDisplay":"VerfasserIn"}],"relHost":[{"title":[{"title_sort":"Random structures & algorithms","title":"Random structures & algorithms"}],"note":["Gesehen am 17.02.05"],"disp":"Seymour's second neighbourhood conjecture random graphs and reductionsRandom structures & algorithms","type":{"bibl":"periodical","media":"Online-Ressource"},"recId":"306711141","language":["eng"],"pubHistory":["1.1990 -"],"titleAlt":[{"title":"Random structures and algorithms"}],"part":{"issue":"1","pages":"1-12","year":"2025","extent":"12","text":"66(2025), 1 vom: Jan., Artikel-ID e21251, Seite 1-12","volume":"66"},"origin":[{"publisherPlace":"New York, NY [u.a.]","publisher":"Wiley","dateIssuedKey":"1990","dateIssuedDisp":"1990-"}],"id":{"zdb":["1500812-5"],"eki":["306711141"],"doi":["10.1002/(ISSN)1098-2418"],"issn":["1098-2418"]},"physDesc":[{"extent":"Online-Ressource"}]}],"physDesc":[{"extent":"12 S."}],"id":{"doi":["10.1002/rsa.21251"],"eki":["1920856897"]},"origin":[{"dateIssuedKey":"2025","dateIssuedDisp":"January 2025"}],"name":{"displayForm":["Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg"]}} 
SRT |a ESPUNYDIAZSEYMOURSSE2025 

Similar Items