Abstract A subset of $${\mathbb {F}}_q^2$$ is called an arc if it does not contain three collinear points. We show that there are at most $$\left( {\begin{subarray}{c}(1 + o(1))q\\ m\end{subarray}}\right) $$ arcs of size $$m \gg q^{1/2} (\log q)^{3/2}$$ , nearly matching a trivial lower bound of $$\left( {\begin{subarray}{c}q\\ m\end{subarray}}\right) $$ . This was previously known to hold for $$m \gg q^{2/3} (\log q)^3$$ , by a result of Bhowmick and Roche-Newton. The lower bound on m is best possible up to a logarithmic factor.

Abstract. We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong [Formula: see text]-regular expander graph [Formula: see text] with [Formula: see text] vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths [Formula: see text] in [Formula: see text] and fulfills any series of two types of requests: (1) Given two vertices [Formula: see text] and [Formula: see text] such that each appears as an endpoint in [Formula: see text] paths in [Formula: see text] and, additionally, [Formula: see text], the algorithm finds a path of length at most [Formula: see text] connecting [Formula: see text] and [Formula: see text] which is edge-disjoint from all other paths in [Formula: see text], and adds it to [Formula: see text]. (2) Remove a given path [Formula: see text] from [Formula: see text]. Importantly, each request is processed before seeing the next one. The upper bound on the length of found paths and the constraints are the best possible up to a constant factor. This establishes the first online algorithm for finding edge-disjoint paths in expanders which also allows removals, significantly strengthening a long list of previous results on the topic. We obtain the same result in the case [Formula: see text] is directed.

Abstract. This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Squares (SoS) proof system. Austrin and Risse [ Perfect matching in random graphs is as hard as tseitin, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia] showed that refuting perfect matchings in sparse [Formula: see text]-regular random graphs, in the above proof systems, with high probability requires proofs with degree [Formula: see text]. We extend their result by showing the same lower bound holds for all [Formula: see text]-regular graphs with a mild spectral gap.

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong d-regular expander graph G with n vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths P in G and fulfills any series of two types of requests:

We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: For a graph H, we denote by Hq the graph obtained from H by subdividing its edges with q–1 vertices each. We show that the k-size-Ramsey number Ŗk(Hq) satisfies Ŗk(Hq) = O(qn) for every bounded degree graph H on n vertices and for q = Ω(log n), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an (n, d, λ)-graph with λ = O(d1 – ∊), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/4 vertices from . Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in , and each path is of the same length . Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).

A seminal result by Komlós, Sarközy, and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree at least $kn/(k + 1)$, for some $k \in \mathbb{N}$ and $n$ sufficiently large, then it contains the $k$th power of a Hamilton cycle. This is easily seen to be the largest power of a Hamilton cycle one can guarantee, given such a minimum degree assumption. Following a recent trend of studying effects of adding random edges to a dense graph, the model known as the randomly perturbed graph, Dudek et al. showed that if the minimum degree is at least $kn/(k + 1) + \alpha n$, for any constant $\alpha > 0$, then adding $O(n)$ random edges on top almost surely results in a graph which contains the $(k + 1)$st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely, that one can almost surely find the $(2k + 1)$st power. This is the largest power one can guarantee in such a setting.

A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree $\delta(G) \ge (r-1)n/r$ for some integer $r \ge 2$, then $G$ contains a $K_r$-factor, assuming $r$ divides $n$. Extremal examples which show optimality of the bound on $\delta(G)$ are very structured and, in particular, contain large independent sets. In analogy to the Ramsey--Turán theory, Balogh, Molla, and Sharifzadeh initiated the study of how the absence of such large independent sets influences sufficient minimum degree. We show the following two related results: (a) For any $r > \ell \ge 2$, if $G$ is a graph satisfying $\delta(G) \ge \frac{r - \ell}{r - \ell + 1}n + \Omega(n)$ and $\alpha_\ell(G) =o(n)$, that is, a largest $K_\ell$-free induced subgraph has at most $o(n)$ vertices, then $G$ contains a $K_r$-factor. This is optimal for $\ell = r - 1$ and extends a result of Balogh, Molla, and Sharifzadeh who considered the case $r = 3$. (b) If a graph $G$ satisfies $\delta(G) = \Omega(n)$ and $\alpha_r^*(G) =o(n)$, that is, every induced $K_r$-free $r$-partite subgraph of $G$ has at least one vertex class of size $o(n)$, then it contains a $K_r$-factor. A similar statement is proven for a general graph $H$.

We show that for any constant Δ ≥ 2, there exists a graph Γ with O(nΔ/2) vertices which contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least Ω(nΔ/2) vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of Γ is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph H on n vertices with maximum degree at most Δ, an induced subgraph of Γ isomorphic to H.

In his seminal paper from 1952 Dirac showed that the complete graph on n ≥ 3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊n/2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n ≥ 3 vertices with minimum in- and out-degree at least n/2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property is the maximum number r such that G has the property even if we allow an adversary to remove an r-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p = ω (log n/n) with respect to Hamiltonicity is 1/2 ± o(1). For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability . In this paper we significantly improve their result to p = ω (log8 n/n), which is optimal up to the polylogarithmic factor.

In 1976 Erdös, Kleitman, and Rothschild determined asymptotically the logarithm of the number of graphs without a clique of a fixed size $\ell$. In this note we extend their result to the case of forbidden cliques of increasing size. More precisely we prove that for $\ell_n \le (\log n)^{1/4}/2$ there are $2^{(1-1/(\ell_n-1))n^2/2+o(n^2/\ell_n)} K_{\ell_n}$-free graphs of order $n$. Our proof is based on the recent hypergraph container theorems of Saxton and Thomason and Balogh, Morris, and Samotij, in combination with a theorem of Lovász and Simonovits.