Search for: All records

Let $$S=(d_1,d_2,d_3, \ldots )$$ be an infinite sequence of rolls of independent fair dice. For an integer $$k \geq 1$$, let $$L_k=L_k(S)$$ be the smallest $$i$$ so that there are $$k$$ integers $$j \leq i$$ for which $$\sum_{t=1}^j d_t$$ is a prime. Therefore, $$L_k$$ is the random variable whose value is the number of dice rolls required until the accumulated sum equals a prime $$k$$ times. It is known that the expected value of $$L_1$$ is close to $2.43$. Here we show that for large $$k$$, the expected value of $$L_k$$ is $$(1+o(1)) k\log_e k$$, where the $o(1)$-term tends to zero as $$k$$ tends to infinity. We also include some computational results about the distribution of $$L_k$$ for $$k \leq 100$$. 

We observe that several vertex Turán type problems for the hypercube that received a considerable amount of attention in the combinatorial community are equivalent to questions about erasure list-decodable codes. Analyzing a recent construction of Ellis, Ivan and Leader, and determining the Turán density of certain hypergraph augmentations we obtain improved bounds for some of these problems. 

Abstract An edge‐coloured graph is said to berainbowif no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge‐coloured graph on vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of for this question. Very recently, Janzer–Sudakov and Kim–Lee–Liu–Tran independently removed the term in Tomon's bound, showing a bound of . We prove an upper bound of for this maximum possible average degree when there is no rainbow cycle. Our result is tight up to the term, and so, it essentially resolves this question. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non‐abelian groups. 

The symmetric difference of two graphs on the same set of vertices is the graph on whose set of edges are all edges that belong to exactly one of the two graphs . For a fixed graph call a collection of spanning subgraphs of a connectivity code for if the symmetric difference of any two distinct subgraphs in is a connected spanning subgraph of . It is easy to see that the maximum possible cardinality of such a collection is at most , where is the edge‐connectivity of and is its minimum degree. We show that equality holds for any ‐regular (mild) expander, and observe that equality does not hold in several natural examples including any large cubic graph, the square of a long cycle and products of a small clique with a long cycle.