Minimum Covering for Hexagon Triple Systems

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c,z,a), where a, b, c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b,y,c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kK ⁿ with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kK ⁿ with hexagon triples is a triple (X, H, P) such that: 1.3kK ⁿ has vertex set X. 2.P is a subset of E(λ K ⁿ ) with vertex set X for some λ, and 3.H is an edge disjoint partition of E(3kK ⁿ )∪ P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kK ⁿ with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kK ⁿ with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kK ⁿ with hexagon triples was given recently by the authors [2]. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kK ⁿ with hexagon triples.     

Arithmetical properties of a sequence arising from an arctangent sum

The sequence {xn} defined by xn=(n+xn−1)/(1−nxn−1), with x₁=1, appeared in the context of some arctangent sums. We establish the fact that xn≠0 for n?4 and conjecture that xn is not an integer for n?5. This conjecture is given a combinatorial interpretation in terms of Stirling numbers via the elementary symmetric functions. The problem features linkage with a well-known conjecture on the existence of infinitely many primes of the form n²+1, as well as our conjecture that (1+¹²)(1+²²)?(1+n²) is not a square for n>3. We present an algorithm that verifies the latter for n?¹⁰³²⁰⁰.     

Adams theorem on Bernoulli numbers revisited

If we denote B_n to be nth Bernoulli number, then the classical result of Adams (J. Reine Angew. Math. 85 (1878) 269) says that p^?|n and (p−1)?n, then p^?|B_n where p is any odd prime p>3. We conjecture that if (p−1)?n, p^?|n and p?+1?n for any odd prime p>3, then the exact power of p dividing B_n is either ? or ?+1. The main purpose of this article is to prove that this conjecture is equivalent to two other unproven hypotheses involving Bernoulli numbers and to provide a positive answer to this conjecture for infinitely many n.     

Tactical decompositions and orbits of projective groups

We consider decompositions of the incidence structure of points and lines of PG(n, q) (n?3) with equally many point and line classes. Such a decomposition, if line-tactical, must also be point-tactical. (This holds more generally in any 2-design.) We conjecture that such a tactical decomposition with more than one class has either a singleton point class, or just two point classes, one of which is a hyperplane. Using the previously mentioned result, we reduce the conjecture to the case n=3, and prove it when q²+q+1 is prime and for very small values of q. The truth of the conjecture would imply that an irreducible collineation group of PG(n, q) (n?3) with equally many point and line orbits is line-transitive (and hence known).     

Covering all triples on n marks by disjoint Steiner systems

Let q be a number all whose prime factors divide integers of the form 2^s ? 1, s odd. If n = q + 2, the (₃ⁿ) triples on n marks can be partitioned into q sets, each forming a Steiner triple system.     

Extremum problems for the cone volume functional of convex polytopes

Lutwak, Yang and Zhang defined the cone volume functional U over convex polytopes in Rn containing the origin in their interiors, and conjectured that the greatest lower bound on the ratio of this centro-affine invariant U to volume V is attained by parallelotopes. In this paper, we give affirmative answers to the conjecture in R² and R³. Some new sharp inequalities characterizing parallelotopes in Rn are established. Moreover, a simplified proof for the conjecture restricted to the class of origin-symmetric convex polytopes in Rn is provided.     

On conjectures of Minkowski and Woods for <Emphasis Type="BoldItalic">n</Emphasis> = 9

Let ?ⁿ be the n-dimensional Euclidean space with O as the origin. Let ∧ be a lattice of determinant 1 such that there is a sphere |X| < R which contains no point of ∧ other than O and has n linearly independent points of ∧ on its boundary. A well known conjecture in the geometry of numbers asserts that any closed sphere in ?ⁿ of radius \( \sqrt {n/4}\) contains a point of ∧. This is known to be true for n≤8. Here we prove a more general conjecture of Woods for n = 9 from which this conjecture follows in ?⁹. Together with a result of McMullen (J. Amer. Math. Soc.18 (2005) 711–734), the long standing conjecture of Minkowski follows for n = 9.     

Deformations of the hemisphere that increase scalar curvature

Consider a compact Riemannian manifold M of dimension n whose boundary ?M is totally geodesic and is isometric to the standard sphere S ^n?1. A natural conjecture of Min-Oo asserts that if the scalar curvature of M is at least n(n?1), then M is isometric to the hemisphere $S_{+}^{n}$ equipped with its standard metric. This conjecture is inspired by the positive mass theorem in general relativity, and has been verified in many special cases. In this paper, we construct counterexamples to Min-Oo??s Conjecture in dimension n??3.     

A theorem on the number of Nash equilibria in a bimatrix game

We show that ify is an odd integer between 1 and 2ⁿ ? 1, there is ann × n bimatrix game with exactlyy Nash equilibria (NE). We conjecture that this 2ⁿ ? 1 is a tight upper bound on the number of NEs in a “nondegenerate”n × n game.     

On a conjecture of Butler and Graham

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k] ⁿ : there exists a way to mark one point on each coordinate line in [k] ⁿ , so that every point in [k] ⁿ is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k ⁿ and as + bt = nk ^n?1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.     

A problem on triples

If a system H of triples (3-uniform hypergraph) on n vertices has the following property: for every 3-coloring of the vertex-set there exists a 3-colored triple, what is the minimum size (S(n)) of H? The first values of S(n) are computed and the asymptotic behaviour of this function is studied.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Power functions with low uniformity on odd characteristic finite fields

In this paper, we give some new low differential uniformity of some power functions defined on finite fields with odd characteristic. As corollaries of the uniformity, we obtain two families of almost perfect nonlinear functions in GF(3 ⁿ ) and GF(5 ⁿ ) separately. Our results can be used to prove the Dobbertin et al.’s conjecture.     

Counting substructures II: Hypergraphs

For various k-uniform hypergraphs F, we give tight lower bounds on the number of copies of F in a k-uniform hypergraph with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of various authors who proved that there is one copy of F. A sample result is the following: Füredi-Simonovits [11] and independently Keevash-Sudakov [16] settled an old conjecture of Sós [29] by proving that the maximum number of triples in an n vertex triple system (for n sufficiently large) that contains no copy of the Fano plane is p(n)=( ₂ ^?n/2? )?n/2?+( ₂ ^?n/2? ?n/2?). We prove that there is an absolute constant c such that if n is sufficiently large and 1 ≤ q ≤ cn ², then every n vertex triple system with p(n)+q edges contains at least $6q\left( {\left( {_4^{\left\lfloor {n/2} \right\rfloor } } \right) + \left( {\left\lceil {n/2} \right\rceil - 3} \right)\left( {_3^{\left\lfloor {n/2} \right\rfloor } } \right)} \right)$ copies of the Fano plane. This is sharp for q≤n/2–2. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Turán problem.     

The steiner ratio conjecture is true for five points

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case.     

Lagrangian 4-planes in holomorphic symplectic varieties of K3[4]-type

We classify the cohomology classes of Lagrangian 4-planes ?⁴ in a smooth manifold X deformation equivalent to a Hilbert scheme of four points on a K3 surface, up to the monodromy action. Classically, the Mori cone of effective curves on a K3 surface S is generated by nonnegative classes C, for which (C, C) ≥ 0, and nodal classes C, for which (C, C) = ?2; Hassett and Tschinkel conjecture that the Mori cone of a holomorphic symplectic variety X is similarly controlled by “nodal” classes C such that (C, C) = ?γ, for (·,·) now the Beauville-Bogomolov form, where γ classifies the geometry of the extremal contraction associated to C. In particular, they conjecture that for X deformation equivalent to a Hilbert scheme of n points on a K3 surface, the class C = ? of a line in a smooth Lagrangian n-plane ? ⁿ must satisfy (?,?) = ?(n + 3)/2. We prove the conjecture for n = 4 by computing the ring of monodromy invariants on X, and showing there is a unique monodromy orbit of Lagrangian 4-planes.     

A maximum degree theorem for diameter-2-critical graphs

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ?n ²/4? and that the extremal graphs are the complete bipartite graphs K _?n/2?,?n/2?. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n ₀ where n ₀ is a tower of 2’s of height about 10¹⁴. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.     

On t-branch split cuts for mixed-integer programs

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n?1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.     

A solution to de Groot’s absolute cone conjecture

A compactum X is an ‘absolute cone’ if, for each of its points x, the space X is homeomorphic to a cone with x corresponding to the cone point. In 1971, J. de Groot conjectured that each n-dimensional absolute cone is an n-cell. In this paper, we give a complete solution to that conjecture. In particular, we show that the conjecture is true for n≤3 and false for n≥5. For n=4, the absolute cone conjecture is true if and only if the 3-dimensional Poincaré Conjecture is true.     

On divisors of binomial coefficients,I

It is a well-known conjecture that (_n²ⁿ) is never squarefree if n > 4. It is shown that (_n²ⁿ) is not squarefree if n > n₀.