A note on the interval number of a graph (Q1065014): Difference between revisions

Three results on the interval number \(i(G)\) and d-dimensional interval number \(i_d(G)\) of a graph \(G\) with n vertices are presented. Theorem 1. The inequalities \(i(G)\geq n/4 lg_2 n\), \(i_d(G)\geq n/4d lg_2 n\) hold for almost every graph (i.e. the probability, that the lower bounds hold, goes to 1 as \(n\to \infty\) in the probability spaces containing all graphs on \(n\) vertices, each of them with the same probability). The first lower bound is also asymptotically true for almost every bipartite graph. Theorem 2. There exist \(K_{m,n}\)-free bipartite graphs with interval number at least \(c(m)\cdot n^{1-2(m+1)}/lg_2 n\), which can be improved to \(\sqrt{n}/4+o(\sqrt{n})\) for \(m=2\) and \((n/2)^{2/3}/lg_2 n\) for \(m=3\). Theorem 3. There exist regular graphs of girth at least \(g\) with interval number at least \(((n-1)/2)^{1/(g-2)}\).