Search for: All records

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. 

We study several variants of a combinatorial game which is based on Cantor’s diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor’s arguments about the infinite, and even referred to him as a “scientific charlatan.” In the game Kronecker maintains a list of m binary vectors, each of length n, and Cantor’s goal is to produce a new binary vector which is different from each of Kronecker’s vectors, or prove that no such vector exists. Cantor does not see Kronecker’s vectors but he is allowed to ask queries of the form What is bit number j of vector number i? What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries adaptively, based on Kronecker’s previous replies? The case when m = n is solved by diagonalization using n (nonadaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the nonadaptive case. 

A group of players are supposed to follow a prescribed profile of strategies. If they follow this profile, they will reach a given target. We show that if the target is not reached because some player deviates, then an outside observer can identify the deviator. We also construct identification methods in two nontrivial cases. 

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. 

A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the (k−1)-dimensional projective space over F_q that have size at most cqk for some universal constant c. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of F_q-linear minimal codes of length n and dimension k, for every prime power q, for which n ≤ cqk. This solves one of the main open problems on minimal codes. 

We determine the maximum possible number of edges of a graph with n vertices, matching number at most s and clique number at most k for all admissible values of the parameters.