European Journal of Combinatorics

European Journal of Combinatorics

Monotonicity and decompositions of random regular graphs

In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters d1≤d2, there exists a coupling of G(n,d1) and G(n,d2) satisfying that G(n,d1)⊆G(n,d2) with high probability, confirming a conjecture of Ga...

Fractional clique decompositions in random hypergraphs

We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic er...

Paths maximize the expected range of graph-indexed random walks

We prove that a path maximizes the expected range of a uniformly chosen graph homomorphism into the integers, with one vertex pinned at zero, among all connected bipartite graphs of the same order. This establishes the expectation form of the Benjamini--H\"aggstr\"om--Mossel conjecture. The proof restricts and rescales...

Circular Flows of Random Regular Graphs With Large Valency

For positive integers with , a circular ‐flow of a graph is defined as a pair where represents an orientation of , and is a function mapping the edges of to the set such that, at each vertex, the sum of the ‐values of the incoming edges equals the sum of the ‐values of the outgoing edges. The flow index of , denoted...

Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees

We prove an annealed central limit theorem for the weight of the maximum weight matching on uniformly random simple graphs with prescribed, uniformly bounded degrees and i.i.d. exponential edge weights. In particular, the result applies to random $d$-regular graphs for every fixed $d \ge 2$. The proof separates the flu...