A note on a conjecture by Füredi

In [Z. Füredi, Turán type problems, in: Surveys in Combinatorics, Guildford, 1991, in: London Math. Soc. Lecture Note Ser., vol. 166, Cambridge Univ. Press, Cambridge, 1991, pp. 253-300, MR1161467 (93d:05072)], Füredi raised a conjecture about the maximum size of L-intersecting families. In this note, we address a variant of this conjecture. In particular, we show that for any Steiner triple system S on [k], there exist a family F of k-sets on [n] with |F|=Ω(n2+?) and such that for every F₀∈F the family is isomorphic to S.     

On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

For a given permutation matrix P, let fP(n) be the maximum number of 1-entries in an n×n(0,1)-matrix avoiding P and let SP(n) be the set of all n×n permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that cP:=limn→∞fP(n)/n is finite, while the Stanley-Wilf conjecture asserts that is finite.In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture.We focus on the values of the Stanley-Wilf limit (sP) and the Füredi-Hajnal limit (cP). We improve the reduction and obtain which decreases the general upper bound on sP from sP?constconstO(klog(k)) to sP?constO(klog(k)) for any k×k permutation matrix P. In the opposite direction, we show .For a lower bound, we present for each k a k×k permutation matrix satisfying cP=Ω(k²).     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Co-countable sets of uniqueness for series of independent random variables

Given a sequence of independent random variables (fk) on a standard Borel space Ω with probability measure μ and a measurable set F, the existence of a countable set S⊂F is shown, with the property that series k_∑ckfk which are constant on S are constant almost everywhere on F. As a consequence, if the functions fk are not constant almost everywhere, then there is a countable set S⊂Ω such that the only series k_∑ckfk which is null on S is the null series; moreover, if there exists b<1 such that for every k and every α, then the set S can be taken inside any measurable set F with μ(F)>b.     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).     

Unprovability threshold for the planar graph minor theorem

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture (*): ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant (27.2269≤γ<30.061). Let P(c) be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G₁,G₂,…,G_N are unlabelled planar graphs with |G_i|<K+c⋅log₂i then for some i<j≤N, G_i is isomorphic to a minor of G_j”. Then

1.

for every , P(c) is provable in IΔ₀+exp;

2.

for every , P(c) is unprovable in .

We also give proofs of some upper and lower bounds for unprovability thresholds in the general case of the finite graph minor theorem.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

Coefficients of ternary cyclotomic polynomials

It is customary to define a cyclotomic polynomial Φn(x) to be ternary if n is the product of three distinct primes, p<q<r. Let A(n) be the largest absolute value of a coefficient of Φn(x) and M(p) be the maximum of A(pqr). In 1968, Sister Marion Beiter (1968, 1971) [3] and [4] conjectured that . In 2008, Yves Gallot and Pieter Moree (2009) [6] showed that the conjecture is false for every p≥11, and they proposed the Corrected Beiter conjecture: . Here we will give a sufficient condition for the Corrected Beiter conjecture and prove it when p=7.     

Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let S_k be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K_k/2's or simply one K_k/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of K_n, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k).     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

A generalization of Gruenhage's example

We construct, assuming the continuum hypothesis, an example of nonmetrizable n-dimensional Cantor manifold Xn(n∈N) with the following properties: 1) is hereditarily separable for all k∈N; 2) is perfectly normal for every k∈N; 3) the space F(Xn) is hereditarily normal for every seminormal functor F that preserves weights and one-to-one points and such that sp(F)={1,k}; in particular, and λ₃Xn are hereditarily normal. This example is a generalization of famous Gruenhage's example given in Gruenhage and Nyikos (1993) [4].     

Waring's number mod m

Let p be an odd prime and γ(k,pn) be the smallest positive integer s such that every integer is a sum of s kth powers . We establish γ(k,pn)?[k/2]+2 and provided that k is not divisible by (p−1)/2. Next, let t=(p−1)/(p−1,k), and q be any positive integer. We show that if ?(t)?q then γ(k,pn)?c(q)k1/q for some constant c(q). These results generalize results known for the case of prime moduli.

Video abstract

For a video summary of this paper, please visit http://www.youtube.com/watch?v=zpHYhwL1kD0.     

Hasse principle for classical groups over function fields of curves over number fields

In (Letter to J.-P. Serre, 12 June 1991) Colliot-Thélène conjectures the following: Let F be a function field in one variable over a number field, with field of constants k and G be a semisimple simply connected linear algebraic group defined over F. Then the map has trivial kernel, denoting the set of places of k.The conjecture is true if G is of type 1A∗, i.e., isomorphic to SL₁(A) for a central simple algebra A over F of square free index, as pointed out by Colliot-Thélène, being an immediate consequence of the theorems of Merkurjev-Suslin [S1] and Kato [K]. Gille [G] proves the conjecture if G is defined over k and F=k(t), the rational function field in one variable over k. We prove that the conjecture is true for groups G defined over k of the types 2A∗, B_n, C_n, D_n (D₄ nontrialitarian), G₂ or F₄; a group is said to be of type 2A∗, if it is isomorphic to SU(B,τ) for a central simple algebra B of square free index over a quadratic extension k′ of k with a unitary k′|k involution τ.     

On complete subsets of the cyclic group

A subset X of an abelian G is said to be complete if every element of G can be expressed as a nonempty sum of distinct elements from X.Let A⊂Zn be such that all the elements of A are coprime with n. Solving a conjecture of Erd?s and Heilbronn, Olson proved that A is complete if n is a prime and if . Recently Vu proved that there is an absolute constant c, such that for an arbitrary large n, A is complete if , and conjectured that 2 is essentially the right value of c.We show that A is complete if , thus proving the last conjecture.     

On 2-factors with k components

In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n₀=n₀(k) such that every Hamiltonian graph G of order n?n₀ with has a 2-factor with k components.     

Integer solutions to decomposable form inequalities

This paper obtains a result on the finiteness of the number of integer solutions to decomposable form inequalities. Let k be a number field and let F(X₁,...,X_m) be a non-degenerate decomposable form with coefficients in k. We prove that, for every finite set of places S of k containing the archimedean places of k, for each real number and for each constant c>0, the inequality

(1)