Interesting problems that I cannot solve
A set of n points in general position in Rd determines
simplices. It is always possible to choose a point in Rd, but not necessarily in the set, which lies in a positive proportion of the simplices. How large is this positive proportion? Denote by c(d) the supremum of all c, so that it is possible to choose point in proportion c of all the simplices. Then c(1)=1/2, c(2)=2/9 and (d2+1)(d+1)-d-1≤c(d)≤(d+1)!(d+1)-d-1.
For a graph G let Gp denote the subgraph of G, in which each edge of G is in Gp with probability p independently at random. For any graph H let χ(H) denote the chromatic number of H. Is there a constant c>0 so that E(χ(G1/2))>c χ(G)/log χ(G)?
Since G1/2 and its complement in G have the same distribution, E(χ(G1/2))≥χ(G)1/2. Also, the inequality E(χ(G1/2))>c χ(G)/log n holds, where n is the number of vertices in G.
For a finite set of integers A define A+A={a+a' : a,a'∈A} and A+2⋅A={a+2a' : a,a'∈A}. Is there an ε>0 such that |A+2⋅A|/|A|≤(|A+A|/|A|)3-ε for all finite sets A?
The inclusion A+2⋅A⊆A+A+A and Plünnecke's inequality together imply that |A+2⋅A|/|A|≤(|A+A|/|A|)3. The analogous question with 2 replaced by any sufficiently large integer has affirmative answer.
For a polynomial f in one real variable let T(f) be the number of non-zero terms in f. Is there an ε>0 such that T(f2)≥T(f)ε?
There are polynomials with arbitrarily many terms for which T(f2)≤T(f)99/100. It is known that T(f2)≥(1/100)log T(f).
...but someone else can!
The height of a rational number p/q, where gcd(p,q)=1, is defined to be H(p/q)=|p|+|q|. Suppose f is a real-analytic function on some open interval, which takes rational numbers to rational numbers. Let k be a positive integer. Does H(f(x))≤H(x)k for all rational x imply that f is a rational function with rational coefficients?
I could show this to be true if one assumes that the function f at some point of the domain has Taylor expansion with the first 2k+1 coefficients rational. By theorem 4 in the paper “Rational points near curves and small nonzero |x^3-y^2| via lattice reduction” by Noam Elkies it is always true.
Let G=(V,E) be a finite graph, and suppose that to each edge e∊E a function fe, from a finite set X to a finite set A, is associated. Let N be the number of functions g: V→X satisfying fxy(g(x))=fxy(g(y)) for every edge xy. If G is the triangle, is there an ε>0 such that N≥|X|3/|A|4-ε?
Imre Ruzsa showed that such an ε does not exist. Let X be a subset of {1,...,n}2 of size |X|=n2-o(1) not containing a corner of the form {(x,y),(x+a,y),(x,y+a)}. Its existence follows from Behrend's construction. Let A={1,...,2n} and put f12(x,y)=x, f13(x,y)=y, f23(x,y)=x+y. If ε>0, for large n we reach a contradiction. Though ε=0, it is possible to prove that w(|A|)N≥|X|3/|A|4 for some function w tending to infinity. If G is a tree, then N≥|X||V|/|A||E|.
Let P be a set of n points in R2 in general position and L be the set of
lines determined by P. Is it possible that one can choose a collection of O(n) points disjoint from P such that every line in L contains at least one of the points in the collection? A linear lower bound on the size of the collection follows from the fact that no point in the collection can be contained in more than n/2 of the lines. A superlinear lower bound can be deduced from Freiman's theorem under the stronger assumption that the collection contains the midpoint of each of the
line segments. The answer to the question is negative, as shown in “Blocking visibility for points in general position” by Jiří Matoušek, which was pointed to me by David Wood.Let f(s)=a1+a22-s+a33-s+… be a Dirichlet series whose coefficients satisfy |an|≤nC. Extend f meromorphically as far as possible. Is the domain of the meromorphic continuation a halfplane?
The question was answered in negative by David Speyer.
