Skip to main content

STRUCTURE, RANDOMNESS AND COMPUTATIONAL METHODS IN EXTREMAL COMBINATORICS

PCI2024-155080-2

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de Transferencia y Colaboración
Subprogram Subprograma Estatal para impulsar la Colaboración en y entre los Sectores Público y Privado
Call Proyectos Programación Conjunta Internacional
Call year 2024
State Plan 2024-2027 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Counting cliques without generalized theta graphs

  • Gao, Jun
  • Wu, Zhuo|||0009-0008-5144-7335
  • Xue, Yisai|||0009-0008-6407-1031
The generalized Turán number ex(n,T,F) is the maximum possible number of copies of T in an F-free graph on n vertices for any two graphs T and F. For the book graph Bb, there is a close connection between ex(n,K3,Bt) and the Ruzsa-Szemerédi triangle removal lemma. Motivated by this, in this paper, we study the generalized Turán problem for generalized theta graphs, a natural extension of book graphs. Our main result provides a complete characterization of the magnitude of ex(n,K3,H) when H is a generalized theta graph, indicating when it is quadratic, when it is nearly quadratic, and when it is subquadratic. Furthermore, as an application, we obtain the exact value of ex(n,Kr,kF), where F is an edge-critical generalized theta graph, and 3 <= r <= k+1, extending several recent results., Z. Wu acknowledges the bilateral AEI+DFG research project PCI2024-155080-2: SRC-ExCo– Structure, Randomness and Computational Methods in Extremal Combinatorics, and the PID2023-147202NB-I00 (COCOA: COntemporary COmbinatorics and its Applications), all funded by MICIU/AEI/10.13039/501100011033.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)