Authors:Meysam Alishahi; Hajiabolhassan Hossein Pages: 1 - 21 Abstract: In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000178 Issue No:Vol. 29, No. 1 (2020)

Authors:Omer Angel; Asaf Ferber, Benny Sudakov, Vincent Tassion Pages: 22 - 30 Abstract: Given a graph G and a bijection f : E(G) → {1, 2,…,e(G)}, we say that a trail/path in G is f-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1-o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1). PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S096354831900018X Issue No:Vol. 29, No. 1 (2020)

Authors:Simeon Ball; Bence Csajbók Pages: 31 - 43 Abstract: We prove that, for q odd, a set of q + 2 points in the projective plane over the field with q elements has at least 2q − c odd secants, where c is a constant and an odd secant is a line incident with an odd number of points of the set. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000245 Issue No:Vol. 29, No. 1 (2020)

Authors:Patrick Bennett; Andrzej Dudek, Bernard Lidický, Oleg Pikhurko Pages: 44 - 67 Abstract: Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $ , where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000257 Issue No:Vol. 29, No. 1 (2020)

Authors:Lorenzo Federico; Remco Van Der Hofstad, Frank Den Hollander, Tim Hulshof Pages: 68 - 100 Abstract: The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let ${m=d(n-1)}$ be the degree and $V = n^d$ be the number of vertices of H(d, n). Let $p_c^{(d)}$ be the critical point for bond percolation on H(d, n). We show that, for $d \in \mathbb{N}$ fixed and $n \to \infty$ , $$p_c^{(d)} = {1 \over m} + {{2{d^2} - 1} \over {2{{(d - 1)}^2}}}{1 \over {{m^2}}} + O({m^{ - 3}}) + O({m^{ - 1}}{V^{ - 1/3}}),$$ which extends the asymptotics found in [10] by one order. The term $O(m^{-1}V^{-1/3})$ is the width of the critical window. For $d=4,5,6$ we have $m^{-3} =O(m^{-1}V^{-1/3})$ , and so the above formula represents the full asymptotic expansion of $p_c^{(d)}$ . In [16] we show that this formula... PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000208 Issue No:Vol. 29, No. 1 (2020)

Authors:Jacob Fox; Ray Li Pages: 101 - 112 Abstract: The hedgehog Ht is a 3-uniform hypergraph on vertices $1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$ such that, for any pair (i, j) with 1 ≤ i < j ≤ t, there exists a unique vertex k > t such that {i, j, k} is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog Ht is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r(Ht) = O(t2 ln t). PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000312 Issue No:Vol. 29, No. 1 (2020)

Authors:Rajko Nenadov; Nemanja Škorić Pages: 113 - 127 Abstract: Given graphs G and H, a family of vertex-disjoint copies of H in G is called an H-tiling. Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ>0, there exists C>0 such that if $p \ge C{n^{ - 1/{m_2}(H)}}$ , then asymptotically almost surely every spanning subgraph G of the random graph í?¯?¢(n, p) with minimum degree at least $\delta (G) \ge (1 - \frac{1}{{{\chi _{{\rm{cr}}}}(H)}} + \gamma )np$ contains an H-tiling that covers all but at most γn vertices. Here, χcr(H) denotes the critical chromatic number, a parameter introduced by Komlós, and m2(H) is the 2-density of H. We show that this theorem can be bootstrapped to obtain an H-tiling covering all but at most $\gamma {(C/p)^{{m_2}(H)}}$ vertices, which is strictly smaller when $p \ge C{n^{ - 1/{m_2}(H)}}$ . In the case where H = K3, this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph H we give an upper bound on p for which some leftover is unavoidable and a bound on the size of a largest H -tiling for p below this value. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000129 Issue No:Vol. 29, No. 1 (2020)

Authors:Bo Ning; Xing Peng Pages: 128 - 136 Abstract: The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2m)/n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least $${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$ edges, where Nj(G) denotes the number of j-cliques in G for 1≤ j ≤ ω(G). We also construct a family of graphs which shows our extension improves the estimate given by the Erdős–Gallai theorem. Among applications, we show, for example, that the main results of [20], which are on the maximum possible number of s-cliques in an n-vertex graph without a path with ℓ vertices (and without cycles of length at least c), can be easily deduced from this extension. Indeed, to prove these results, Luo [20] generalized a classical theorem of Kopylov and established a tight upper bound on the number of s-cliques in an n-vertex 2-connected graph with circumference less than c. We prove a similar result for an n-vertex 2-connected graph with circumference less than c and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000269 Issue No:Vol. 29, No. 1 (2020)

Authors:Ross G. Pinsky Pages: 137 - 152 Abstract: For $$\tau \in {S_3}$$ , let $$\mu _n^\tau $$ denote the uniformly random probability measure on the set of $$\tau $$ -avoiding permutations in $${S_n}$$ . Let $${\mathbb {N}^*} = {\mathbb {N}} \cup \{ \infty \} $$ with an appropriate metric and denote by $$S({\mathbb{N}},{\mathbb{N}^*})$$ the compact metric space consisting of functions $$\sigma {\rm{ = }}\{ {\sigma _i}\} _{i = 1}^\infty {\rm{ }}$$ from $$\mathbb {N}$$ to $${\mathbb {N}^ * }$$ which are injections when restricted to $${\sigma ^{ - 1}}(\mathbb {N})$$ ; that is, if $${\sigma _i}{\rm{ = }}{\sigma _j}$$ PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000270 Issue No:Vol. 29, No. 1 (2020)

Authors:Shachar Sapir; Asaf Shapira Pages: 153 - 162 Abstract: The induced removal lemma of Alon, Fischer, Krivelevich and Szegedy states that if an n-vertex graph G is ε-far from being induced H-free then G contains δH(ε) · nh induced copies of H. Improving upon the original proof, Conlon and Fox proved that 1/δH(ε)is at most a tower of height poly(1/ε), and asked if this bound can be further improved to a tower of height log(1/ε). In this paper we obtain such a bound for graphs G of density O(ε). We actually prove a more general result, which, as a special case, also gives a new proof of Fox’s bound for the (non-induced) removal lemma. PubDate: 2020-01-01T00:00:00.000Z DOI: 10.1017/S0963548319000233 Issue No:Vol. 29, No. 1 (2020)