Typical Structure of Hereditary Graph Families. II. Exotic Examples

组合数学 数学 图形 计算机科学 谱系学 历史
作者
Sergey Norin,Yelena Yuditsky
出处
期刊:Random Structures and Algorithms [Wiley]
卷期号:66 (1) 被引量:1
标识
DOI:10.1002/rsa.21272
摘要

ABSTRACT A graph is ‐free if it does not contain an induced subgraph isomorphic to . The study of the typical structure of ‐free graphs was initiated by Erdős, Kleitman, and Rothschild (1976), who have shown that almost all ‐free graphs are bipartite. Since then the typical structure of ‐free graphs has been determined for several families of graphs , including complete graphs, trees, and cycles. Recently, Reed and Scott proposed a conjectural description of the typical structure of ‐free graphs for all graphs , which extends all previously known results in the area. We construct an infinite family of graphs for which the Reed–Scott conjecture fails, and use the methods we developed in the prequel paper Norin and Yuditsky (2024) to describe the typical structure of ‐free graphs for graphs in this family. Using similar techniques, we construct an infinite family of graphs for which the maximum size of a homogenous set in a typical ‐free graph is sublinear in the number of vertices, answering a question of Loebl et al. (2010) and Kang et al. (2014).
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
树袋熊和考拉完成签到,获得积分10
1秒前
77完成签到 ,获得积分10
7秒前
wildeager完成签到,获得积分10
9秒前
CH完成签到,获得积分10
12秒前
萤火虫完成签到,获得积分10
12秒前
量子星尘发布了新的文献求助10
13秒前
王蕊完成签到,获得积分10
14秒前
小羊完成签到 ,获得积分10
23秒前
jeronimo完成签到,获得积分10
26秒前
空白完成签到 ,获得积分10
26秒前
凉面完成签到 ,获得积分10
34秒前
幸福妙柏完成签到 ,获得积分10
36秒前
yellow完成签到,获得积分10
42秒前
42秒前
月军完成签到,获得积分10
48秒前
小静完成签到 ,获得积分10
52秒前
SYLH应助月军采纳,获得10
54秒前
悄悄是心上的肖肖完成签到 ,获得积分10
58秒前
58秒前
wangermazi完成签到,获得积分0
1分钟前
执着的忆雪完成签到 ,获得积分10
1分钟前
骄傲慕尼黑完成签到,获得积分10
1分钟前
飞龙在天完成签到,获得积分0
1分钟前
银海里的玫瑰_完成签到 ,获得积分10
1分钟前
marc107完成签到,获得积分10
1分钟前
朱佳宁完成签到 ,获得积分10
1分钟前
量子星尘发布了新的文献求助50
1分钟前
小土豆完成签到 ,获得积分10
1分钟前
搜集达人应助法桐落梦采纳,获得100
1分钟前
alho完成签到 ,获得积分10
1分钟前
执着乐双完成签到,获得积分10
1分钟前
peng完成签到,获得积分10
1分钟前
波里舞完成签到 ,获得积分10
1分钟前
世间安得双全法完成签到,获得积分0
1分钟前
Xenia完成签到 ,获得积分10
1分钟前
小胖完成签到 ,获得积分10
1分钟前
豆花浮元子完成签到 ,获得积分10
1分钟前
修语完成签到,获得积分10
1分钟前
aDou完成签到 ,获得积分10
1分钟前
菓小柒完成签到 ,获得积分10
1分钟前
高分求助中
【提示信息,请勿应助】关于scihub 10000
A new approach to the extrapolation of accelerated life test data 1000
Coking simulation aids on-stream time 450
北师大毕业论文 基于可调谐半导体激光吸收光谱技术泄漏气体检测系统的研究 390
Phylogenetic study of the order Polydesmida (Myriapoda: Diplopoda) 370
Robot-supported joining of reinforcement textiles with one-sided sewing heads 360
Novel Preparation of Chitin Nanocrystals by H2SO4 and H3PO4 Hydrolysis Followed by High-Pressure Water Jet Treatments 300
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 4015603
求助须知:如何正确求助?哪些是违规求助? 3555597
关于积分的说明 11318138
捐赠科研通 3288782
什么是DOI,文献DOI怎么找? 1812284
邀请新用户注册赠送积分活动 887882
科研通“疑难数据库(出版商)”最低求助积分说明 812015