After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.
Abstract
For every integer $r\ge4$, and $\rho \in [0,1]$, we asymptotically determine the maximum proportion of $r$-element sets of vertices that induce either a clique or an independent set in a large graph with density $\rho$. This generalizes a result of Olpp for $r=3$. After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.
We prove that, for every integer $k\ge 2$, there exists a constant $c_k>0$ such that every graph on $n\ge R(k,k)$ vertices with maximum degree $\Delta$ contains an induced subgraph on at least $n-c_k\sqrt{\Delta}$ vertices whose maximum degree is attained by at least $k$ vertices. This confirms a conjecture of Caro and...
We show that, for some absolute constants $c_1,c_2>0$, every $(n,d,\lambda)$-graph with $\lambda\le c_1 d$ contains an induced cycle of length at least $c_2n\log(d/\lambda)/d$. This is best possible up to the values of $c_1,c_2$. Our techniques include a multi-scale algorithmic analysis, an adapted depth-first explorat...
Sahar Diskin, Lyuben Lichev, Michael Krivelevich et al.· 1 citation
For fixed integers $k\ge3$ and $1\le d\le k-1$ and sufficiently large $n\in k\mathbb N$, we establish the sharp minimum $d$-degree thresholds that forces perfect matching in every $n$-vertex $k$-uniform hypergraphs. This was conjectued by Treglown and Zhao, and the $d=1$ case was conjectued by K\"uhn, Osthus and Treglo...
Jie Han, Hong-Liang Lu, Bin Wang et al.· 1 citation
The book with $t$ pages is the graph on $t+2$ vertices consisting of $t$ triangles which intersect at exactly one common edge. For a given graph $F$, the $r$-expansion $F^r$ of $F$ is the $r$-uniform hypergraph obtained from $F$ by adding $r-2$ distinct new vertices to each edge of $F$. We determine the Tur\'an number...
For every natural number $r\geq 2$, we construct $r^{th}$ powers of bipartite graphs whose chromatic number is quadratic in their clique number, showing that the straightforward quadratic upper bound is best possible. We thereby settle an open problem posed by Chakraborty, Chandran, Jacob and Pillai [J. Graph Theory 11...
In 1977, Erd\H{o}s posed the problem of determining the maximum number $f_r(n)$ of edges in an $n$-vertex $r$-uniform hypergraph in which all disjoint pairs of edges have distinct unions. F\"uredi later conjectured that, for every fixed $r\ge 4$ and all sufficiently large $n$, $f_r(n)=\binom{n-1}{r-1}+\lfloor \frac{n-1...
Hao-Wei Huang, Jie Ma, Tian-Chi Yang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
