[논문]On the rational Turán exponents conjecture

Kang, Dong Yeap; Kim, Jaehoon; Liu, Hong

doi:10.1016/j.jctb.2020.12.003

[해외논문] On the rational Turán exponents conjecture

Journal of combinatorial theory. Series B, v.148, 2021년, pp.149 - 172

Kang, Dong Yeap (School of Mathematics, University of Birmingham) , Kim, Jaehoon (Department of Mathematical Sciences, KAIST) , Liu, Hong (Mathematics Institute, University of Warwick)

Abstract ▼ AI-Helper

Abstract The extremal number ex ( n , F ) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r ∈ [ 1 , 2 ] is realisable if there exists a graph F with ex ( n , F ) = Θ ( n r ) . Several decades ago, Erdős and Simonovits conjectured that every rational number in [ 1 , 2 ] is realisable. Despite decades of effort, the only known realisable numbers are 0 , 1 , 7 5 , 2 , and the numbers of the form 1 + 1 m , 2 − 1 m , 2 − 2 m for integers m ≥ 1 . In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2 − a b is realisable for any integers a , b ≥ 1 with b > a and b ≡ ± 1 ( mod a ) . This includes all previously known ones, and gives infinitely many limit points 2 − 1 m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

Keyword

참고문헌 (28)

J. Comb. Theory, Ser. B Alon 76 2 280 1999 10.1006/jctb.1999.1906 Norm-graphs: variations and applications

상세보기
Bull. Lond. Math. Soc. Bukh 47 6 939 2015 Random algebraic construction of extremal graphs

상세보기
J. Eur. Math. Soc. Bukh 20 1747 2018 10.4171/JEMS/798 Rational exponents in extremal graph theory

상세보기
Comb. Probab. Comput. Bukh 29 4 495 2020 10.1017/S0963548320000012 Turan number of theta graphs

상세보기
Bull. Lond. Math. Soc. Conlon 51 6 1015 2019 10.1112/blms.12295 Graphs with few paths of prescribed length between any two vertices

상세보기
Combinatorica Conlon 2020 More on the extremal number of subdivisions
Int. Math. Res. Not. Conlon 2019 10.1093/imrn/rnz088 On the extremal number of subdivisions

상세보기
Combinatorica Erds 1 1 25 1981 10.1007/BF02579174 On the combinatorial problems which I would most like to see solved

상세보기
Erds vol. 72 81 1988 Proceedings of the First Japan Conference on Graph Theory and Applications Problems and results in combinatorial analysis and graph theory
Studia Sci. Math. Hung. Erds 1 51 1966 A limit theorem in graph theory
Erds 377 1970 Combinatorial theory and its applications, I (Proc. Colloq., Balatonfured, 1969) Some extremal problems in graph theory
Bull. Am. Math. Soc. Erds 52 1087 1946 10.1090/S0002-9904-1946-08715-7 On the structure of linear graphs

상세보기
Combinatorica Faudree 3 1 83 1983 10.1007/BF02579343 On a class of degenerate extremal graph problems

상세보기
J. Comb. Fitch 10 1 61 2019 Rational exponents for hypergraph Turan problems

상세보기
Random Struct. Algorithms Fox 38 1-2 68 2011 10.1002/rsa.20344 Dependent random choice

상세보기
J. Comb. Theory, Ser. A Frankl 42 2 200 1986 10.1016/0097-3165(86)90090-7 All rationals occur as exponents

상세보기
Furedi vol. 25 169 2013 Erdos Centennial The history of degenerate (bipartite) extremal graph problems
Elecron. J. Combin. Janzer 26 3 6 2019 Improved bounds for the extremal number of subdivisions
SIAM J. Discrete Math. Janzer 34 1 241 2020 10.1137/19M1269798 The extremal number of the subdivisions of the complete bipartite graph

상세보기
Jiang
Jiang
Jiang
SIAM J. Discrete Math. Jiang 34 1 556 2020 10.1137/19M1265442 Turan numbers of bipartite subdivisions

상세보기
Colloq. Math. Kvari 3 50 1954 10.4064/cm-3-1-50-57 On a problem of K. Zarankiewicz

상세보기
Combinatorica Kollar 16 3 399 1996 10.1007/BF01261323 Norm-graphs and bipartite Turan numbers

상세보기
Wiskd. Opgaven Mantel 10 60 1907 Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)
J. Comb. Theory, Ser. B Verstraete 134 76 2019 10.1016/j.jctb.2018.05.003 Graphs without theta subgraphs

상세보기
Zhang

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 URL 링크

DOI : 10.1016/j.jctb.2020.12.003
Elsevier : 저널 > 논문

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증