Umeå University's logo

The upper density of an infinite graph G with V(G)⊆N is defined as d¯(G)=lim supn→∞|V(G)∩{1,…,n}|/n. Let KN be the infinite complete graph with vertex set N. Corsten, DeBiasio, Lamaison and Lang showed that in every 2-edge-colouring of KN, there exists a monochromatic path with upper density at least (12+8)/17, which is best possible. In this paper, we extend this result to k-edge-colouring of KN for k≥3. We conjecture that every k-edge-coloured KN contains a monochromatic path with upper density at least 1/(k−1), which is best possible (when k−1 is a prime power). We prove that this is true when k=3 and asymptotically when k=4. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.

An (n,s,q)-graph is an n-vertex multigraph in which every s-set of vertices spans at most q edges. Turán-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry (2019) [13] posed the problem of determining the maximum of the product of the edge multiplicities in (n,s,q)-graphs. We give a general lower bound construction for this problem for many pairs (s,q), which we conjecture is asymptotically best possible. We prove various general cases of our conjecture, and in particular we settle a conjecture of Mubayi and Terry on the (s,q)=(4,6a+3) case of the problem (for a≥2); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for ‘sparse’ multigraphs (i.e. when q≤2(s2)). Finally we introduce some tools that are likely to be useful for attacking the problem in general.

Motivated by problems in percolation theory, we study the following two-player positional game. Let ?(mxn) be a rectangular grid-graph with m vertices in each row and n vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims p (as yet unclaimed) edges of the board ?(mxn), while on each of his turns Breaker claims q (as yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the (p, q)-crossing game on ?(mxn). Given m, n is an element of N, for which pairs (p, q) does Maker have a winning strategy for the (p, q)-crossing game on ?(mxn)? The (1, 1)-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper we study the general (p, q)-case. Our main result is to establish the following transition. If >= 2, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2, )-crossing game on ?x(+1 for any is an element of N. pqqqmq)mIf p <= 2q - 1, then for every width n of the board, Breaker has a winning strategy for the (p, q)-crossing game on ?mxn for all sufficiently large board-lengths m. Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.

Let Lambda be an infinite connected graph, and let v(0) be a vertex of Lambda. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of Lambda are marked as unsafe. On each of her turns, Maker marks p unsafe edges as safe, while on each of his turns Breaker takes q unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing v(0) becomes finite. Otherwise if Maker is able to ensure that v(0) remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given (p, q) and (Lambda, v(0)), we would like to know: which of the two players has a winning strategy?

Our main result in this paper establishes that when Lambda = Z(2) and v(0) is any vertex, Maker has a winning strategy whenever p >= 2q, while Breaker has a winning strategy whenever 2p <= q. In addition, we completely determine which of the two players has a winning strategy for every pair (p, q) when Lambda is an infinite d -regular tree. Finally, we give some results for general graphs and lattices and pose some open problems. (C) 2020 Elsevier Inc. All rights reserved.

We disprove a conjecture of Nagy on the maximum number of copies N(G, H) of a_xed graph G in a large graph H with prescribed edge density. Nagy conjectured that for all G, the quantity N(G, H) is asymptotically maximized by either a quasi-star or a quasi-clique. We show this is false for in_nitely many graphs, the smallest of which has six vertices and six edges. We also propose some new conjectures for the behavior of N(G, H) and present some evidence for them.

A probability measure on the subsets of the edge set of a graph G is a 1‐independent probability measure (1‐ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1‐ipm , denote by the associated random graph model. Let denote the collection of 1‐ipms on G for which each edge is included in with probability at least p. For , Balister and Bollobás asked for the value of the least p_⋆ such that for all p > p_⋆ and all , almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p_⋆. We also determine the 1‐independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f_1, G(p), the infimum over all of the probability that is connected. We determine f_1, G(p) exactly when G is a path, a complete graph and a cycle of length at most 5.