Let $G(n,m)$ be the Erdos-Renyi random graph with $n$ vertices and $m$ edges and let $\delta>0$. Alon and Krivelevich [Combinatorica 1997] proved that for any sequence $m\leq n^{3/2-\delta}$ there \emph{exists} an integer sequence $q=q(n)$ such that the chromatic number of $G(n,m)$ equals either $q$ or $q+1$ with probability tending to one as $n\to\infty$. In this paper, we give an explicit formula for this sequence $q(n)$ and confirm their result under a less restrictive assumption that $m=o(n^{3/2})$. Furthermore, we show that for all but a vanishing proportion of the admissible values of $m$, the chromatic number of $G(n,m)$ equals $q$ with high probability.
For integers $n>k\ge1$ with $nk$ even, let $m(n,k)$ be the maximum size of a graph of order $n$ with a unique $k$-factor. In 1964, Hetyei and in 1984, Hendry [\emph{J. Combin. Theory Ser. B} \textbf{37} (1984), 53--63] proved $m(n,1)=n^2/4$ for even $n$ and $m(n,2)=\lfloor n(n+1)/4\rfloor$, respectively. In 2000, Johan...
We study the list chromatic number of generalized Johnson graphs. Recall that the vertices of such graphs are all possible $r$-element subsets of $[n] = \{1, \dotsc, n\}$ and an edge is drawn between two vertices if and only if corresponding sets have exactly $s$ common elements. We prove that for any fixed $s \geq 1$...
For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\g...
For a fixed $k$-graph $F$, let $h_F(n,q)$ be the minimum number of copies of $F$ in an $n$-vertex $k$-graph with $\text{ex}(n,F)+q$ edges. Let $c(n,F)$ be the minimum number created by adding one edge to an extremal $F$-free $k$-graph. We construct stable counterexamples to Mubayi's supersaturation conjecture for every...
Li-Ping Zhang, Qing-Hai Liu, Qin-Fei Tang et al.· 0 citations
For positive integers $t$ and $q$ let $b_q(t)$ be the smallest integer $n$ so that any coloring of the edges of the complete bipartite graph $K_{n,n}$ with $q$ colors yields a monochromatic copy of $K_{t,t}$. We give an independent proof that $b_2(t)\le 128\cdot 2^t$ for every positive integer $t$. More generally, for...
An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, R\"{o}dl, and Schacht conjectured that, for any fixed graph $F$, th...
Hyunwoo Lee· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.