A scaling limit for the length of the longest cycle in a sparse random digraph

We discuss the length of the longest directed cycle in the sparse random digraph , constant. We show that for large there exists a function such that a.s. The function where is a polynomial in . We are only able to explicitly give the values , although we could in principle compute any .     

Counting restricted orientations of random graphs

We count orientations of avoiding certain classes of oriented graphs. In particular, we study , the number of orientations of the binomial random graph in which every copy of is transitive, and , the number of orientations of containing no strongly connected copy of . We give the correct order of growth of and up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.     

Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

Fractal graphs

The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.     

The Ramsey number of loose cycles versus cliques

Let be the Ramsey number of an -uniform loose cycle of length versus an -uniform clique of order . Kostochka et al. showed that for each fixed , the order of magnitude of is up to a polylogarithmic factor in . They conjectured that for each we have . We prove that , and more generally for every that . We also prove that for every and , if is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every and we have .     

Distance matching extension and local structure of graphs

A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally -connected -free graph of even order is distance matchable. We also prove that every connected, locally -connected -free graph of even order is distance matchable. Furthermore, we make more detailed analysis of -free graphs and study their distance matching extension properties.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

Reconstruction from the deck of -vertex induced subgraphs

The - deck of a graph is its multiset of subgraphs induced by vertices; we study what can be deduced about a graph from its -deck. We strengthen a result of Manvel by proving for that when is large enough ( suffices), the -deck determines whether an -vertex graph is connected ( suffices when , and cannot suffice). The reconstructibility of a graph with vertices is the largest such that is determined by its -deck. We generalize a result of Bollobás by showing for almost all graphs. As an upper bound on , we have . More generally, we compute whenever , which involves extending a result of Stanley. Finally, we show that a complete -partite graph is reconstructible from its -deck.     

Maximizing the mean subtree order

This article focuses on properties and structures of trees with maximum mean subtree order in a given family; such trees are called optimal in the family. Our main goal is to describe the structure of optimal trees in and , the families of all trees and caterpillars, respectively, of order . We begin by establishing a powerful tool called the Gluing Lemma, which is used to prove several of our main results. In particular, we show that if is an optimal tree in or for , then every leaf of is adjacent to a vertex of degree at least . We also use the Gluing Lemma to answer an open question of Jamison and to provide a conceptually simple proof of Jamison's result that the path has minimum mean subtree order among all trees of order . We prove that if is optimal in , then the number of leaves in is and that if is optimal in , then the number of leaves in is . Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees.     

On the exact decomposition threshold for even cycles

A graph has a -decomposition if its edge set can be partitioned into cycles of length . We show that if , then has a -decomposition, and if , then has a -decomposition, where and (we assume is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, Kühn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when is bipartite or satisfies certain expansion properties.     

On polynomial approximations to AC

Classical approximation results show that any circuit of size and depth has an ‐error probabilistic polynomial over the reals of degree . We improve this upper bound to , which is much better for small values of . We then use this result to show that ‐wise independence fools circuits of size and depth up to error at most , improving on Tal's strengthening of Braverman's result that ‐wise independence suffices. To our knowledge, this is the first PRG construction for that achieves optimal dependence on the error . We also prove lower bounds on the best polynomial approximations to . We show that any polynomial approximating the function on bits to a small constant error must have degree at least . This result improves exponentially on a result of Meka, Nguyen, and Vu (Theory Comput. 2016).     

Rainbow structures in locally bounded colorings of graphs

We study approximate decompositions of edge‐colored quasirandom graphs into rainbow spanning structures: an edge‐coloring of a graph is locally ‐bounded if every vertex is incident to at most edges of each color, and is (globally) ‐bounded if every color appears at most times. Our results imply the existence of: (1) approximate decompositions of properly edge‐colored into rainbow almost‐spanning cycles; (2) approximate decompositions of edge‐colored into rainbow Hamilton cycles, provided that the coloring is ‐bounded and locally ‐bounded; and (3) an approximate decomposition into full transversals of any array, provided each symbol appears times in total and only times in each row or column. Apart from the logarithmic factors, these bounds are essentially best possible. We also prove analogues for rainbow ‐factors, where is any fixed graph. Both (1) and (2) imply approximate versions of the Brualdi‐Hollingsworth conjecture on decompositions into rainbow spanning trees.     

Bipartite spanning sub(di)graphs induced by 2-partitions

For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges that have one end in each . We determine, for all pairs of nonnegative integers , the complexity of deciding whether has a 2-partition such that each vertex in (for ) has at least (out-)neighbours in . We prove that it is -complete to decide whether a digraph has a 2-partition such that each vertex in has an out-neighbour in and each vertex in has an in-neighbour in . The problem becomes polynomially solvable if we require to be strongly connected. We give a characterisation of the structure of -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes -complete even for strong digraphs. A further result is that it is -complete to decide whether a given digraph has a -partition such that is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.     

Normal approximation and fourth moment theorems for monochromatic triangles

Given a graph sequence denote by T₃(G_n) the number of monochromatic triangles in a uniformly random coloring of the vertices of G_n with colors. In this paper we prove a central limit theorem (CLT) for T₃(G_n) with explicit error rates, using a quantitative version of the martingale CLT. We then relate this error term to the well-known fourth-moment phenomenon, which, interestingly, holds only when the number of colors satisfies . We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any , which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of T₃(G_n), whenever . Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in [7].     

Stable blow-up dynamics in the -critical and -supercritical generalized Hartree equation

We study stable blow-up dynamics in the generalized Hartree equation with radial symmetry, which is a Schrödinger-type equation with a nonlocal, convolution-type nonlinearity: First, we consider the -critical case in dimensions and obtain that a generic blow-up has a self-similar structure and exhibits not only the square root blowup rate , but also the log-log correction (via asymptotic analysis and functional fitting), thus, behaving similarly to the stable blow-up regime in the -critical nonlinear Schrödinger equation. In this setting, we also study blow-up profiles and show that generic blow-up solutions converge to the rescaled , a ground state solution of the elliptic equation . We also consider the -supercritical case in dimensions . We derive the profile equation for the self-similar blow-up and establish the existence and local uniqueness of its solutions. As in the NLS -supercritical regime, the profile equation exhibits branches of nonoscillating, polynomially decaying (multi-bump) solutions. A numerical scheme of putting constraints into solving the corresponding ordinary differential equation is applied during the process of finding the multi-bump solutions. Direct numerical simulation of solutions to the generalized Hartree equation by the dynamic rescaling method indicates that the is the profile for the stable blow-up. In this supercritical case, we obtain the blow-up rate without any correction. This blow-up happens at the focusing level , and thus, numerically observable (unlike the -critical case). In summary, we find that the results are similar to the behavior of stable self-similar blowup solutions in the corresponding settings for the nonlinear Schrödinger equation. Consequently, one may expect that the form of the nonlinearity in the Schrödinger-type equations is not essential in the stable formation of singularities.     

A survey on the study of real zeros of flow polynomials

For a bridgeless graph , its flow polynomial is defined to be the function , which counts the number of nonwhere-zero -flows on an orientation of whenever is a positive integer and is an additive Abelian group of order . It was introduced by Tutte in 1950, and the locations of zeros of this polynomial have been studied by many researchers. This paper gives a survey on the results and problems on the study of real zeros of flow polynomials.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

Extending edge-colorings of complete hypergraphs into regular colorings

Let be the collection of all -subsets of an -set . Given a coloring (partition) of a set , we are interested in finding conditions under which this coloring is extendible to a coloring of so that the number of times each element of appears in each color class (all sets of the same color) is the same number . The case was studied by Sylvester in the 18th century and remained open until the 1970s. The case is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. For , we settle the cases , and completely. Moreover, we make partial progress toward solving the case where . These results can be seen as extensions of the famous Baranyai’s theorem, and make progress toward settling a 40-year-old problem posed by Cameron.