Optimal conflict-avoiding codes of odd length and weight three

A conflict-avoiding code (CAC) \({\mathcal{C}}\) of length n and weight k is a collection of k-subsets of \({\mathbb{Z}_{n}}\) such that \({\Delta (x) \cap \Delta (y) = \emptyset}\) for any \({x, y \in \mathcal{C}}\) , \({x\neq y}\) , where \({\Delta (x) = \{a - b:\,a, b \in x, a \neq b\}}\) . Let CAC(n, k) denote the class of all CACs of length n and weight k. A CAC with maximum size is called optimal. In this paper, we study the constructions of optimal CACs for the case when n is odd and k = 3.     

Smallest Set-Transversals of k-Partitions

We asymptotically solve an open problem raised independently by Sterboul (Colloq Math Soc J Bolyai 3:1387–1404, 1973), Arocha et al. (J Graph Theory 16:319–326, 1992) and Voloshin (Australas J Combin 11:25–45, 1995). For integers n ≥ k ≥ 2, let f(n, k) denote the minimum cardinality of a family ${\mathcal H}$ of k-element sets over an n-element underlying set X such that every partition ${X_1\cup\cdots\cup X_k=X}$ into k nonempty classes completely partitions some ${H\in\mathcal H}$ ;  that is, ${|H\cap X_i|=1}$ holds for all 1 ≤ i ≤ k. This very natural function—whose defining property for k = 2 just means that ${\mathcal H}$ is a connected graph—turns out to be related to several extensively studied areas in combinatorics and graph theory. We prove general estimates from which ${ f(n,k) = (1+o(1))\, \tfrac{2}{n}\,{n\choose k}}$ follows for every fixed k, and also for all k = o(n ^1/3), as n → ∞. Further, we disprove a conjecture of Arocha et al. (1992). The exact determination of f(n,k) for all n and k appears to be far beyond reach to our present knowledge, since e.g. the equality ${f(n,n-2)={n-2\choose 2}-{\rm ex}(n,\{C_3,C_4\})}$ holds, where the last term is the Turán number for graphs of girth 5.     

Mutually disjoint t-designs and t-SEEDs from extremal doubly-even self-dual codes

It is known that extremal doubly-even self-dual codes of length \(n\equiv 8\) or \(0\ (\mathrm {mod}\ 24)\) yield 3- or 5-designs respectively. In this paper, by using the generator matrices of bordered double circulant doubly-even self-dual codes, we give 3-(n, k; m)-SEEDs with (n, k, m) \(\in \{(32,8,5), (56,12,9), (56,16,9), (56,24,9), (80,16,52)\}\) . With the aid of computer, we obtain 22 generator matrices of bordered double circulant doubly-even self-dual codes of length 48, which enable us to get 506 mutually disjoint 5-(48, k, \(\lambda \) ) designs for (k, \(\lambda \) )=(12, 8),(16, 1356),(20, 36176). Moreover, this implies 5-(48, k; 506)-SEEDs for \(k=12, 16, 20, 24\) .     

Length of Geodesics and Quantitative Morse Theory on Loop Spaces

Let M ⁿ be a closed Riemannian manifold of diameter d. Our first main result is that for every two (not necessarily distinct) points ${p,q \in M^n}$ and every positive integer k there are at least k distinct geodesics connecting p and q of length ${\leq 4nk^2d}$ . We demonstrate that all homotopy classes of M ⁿ can be represented by spheres swept-out by “short” loops unless the length functional has “many” “deep” local minima of a “small” length on the space ${\Omega_{pq}M^n}$ of paths connecting p and q. For example, one of our results implies that for every positive integer k there are two possibilities: Either the length functional on ${\Omega_{pq} M^n}$ has k distinct non-trivial local minima with length ${\leq 2kd}$ and “depth” ${\geq 2d}$ ; or for every m every map of S ^m into ${\Omega_{pq}M^n}$ is homotopic to a map of S ^m into the subspace ${\Omega_{pq}^{4(k+2)(m+1)d}M^n}$ of ${\Omega_{pq}M^n}$ that consists of all paths of length ${\leq 4(k+2)(m+1)d}$ .     

Disproof of the neighborhood conjecture with implications to SAT

We study a special class of binary trees. Our results have implications on Maker/Breaker games and SAT: We disprove a conjecture of Beck on positional games and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovász Local Lemma is tight up to a constant factor. A (k, s)-CNF formula is a boolean formula in conjunctive normal form where every clause contains exactly k distinct literals and every variable occurs in at most s clauses. The (k, s)-SAT problem is the satisfiability problem restricted to (k, s)-CNF formulas. Kratochvíl, Savický and Tuza showed that for every k≥3 there is an integer f(k) such that every (k, f(k))-CNF formula is satisfiable, but (k, f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvíl, Savický and Tuza also gave the best known lower bound $f(k) = \Omega \left( {\tfrac{{2^k }} {k}} \right)$ , which is a consequence of the Lovász Local Lemma. We prove that, in fact, $f(k) = \Theta \left( {\tfrac{{2^k }} {k}} \right)$ , improving upon the best known upper bound $O\left( {(\log k) \cdot \tfrac{{2^k }} {k}} \right)$ by Hoory and Szeider. Finally we establish a connection between the class of trees we consider and a certain family of positional games. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph $\mathcal{F}$ , with Maker going first. Maker’s goal is to completely occupy a hyperedge and Breaker tries to prevent this. The maximum neighborhood size of a hypergraph $\mathcal{F}$ is the maximal s such that some hyperedge of $\mathcal{F}$ intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of $\mathcal{F}$ is smaller than 2 ^n?1 ? 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every n≥3, the existence of an n-uniform hypergraph with maximum neighborhood size 3·2 ^n?3 where Maker has a winning strategy. Moreover, we show how to construct, for every n, an n-uniform hypergraph with maximum degree at most $\frac{{2^{n + 2} }} {n}$ where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most $\frac{{2^{n - 2} }} {{en}}$ has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.     

A note on propositional proof complexity of some Ramsey-type statements

A Ramsey statement denoted ${n \longrightarrow (k)^2_2}$ says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(n ^k ) and with terms of size ${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$ . Let r _k be the minimal n for which the statement holds. We prove that RAM(r _k , k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák??s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4 ^k , k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R.     

On the number of even and odd strings along the overpartitions of n

Recently, Andrews, Chan, Kim, and Osburn introduced the even strings and the odd strings in the overpartitions. We show that their conjecture $$A_k (n) \geq B_k (n)$$ holds for large enough positive integers n, where A _k (n) (resp. B _k (n)) is the number of odd (resp. even) strings along the overpartitions of n. We introduce m-strings and show how this new combinatorial object is related with another positivity conjecture of Andrews, Chan, Kim, and Osburn. Finally, we confirm that the positivity conjecture is also true for large enough integers.     

Group homomorphic encryption: characterizations, impossibility results, and applications

We give a complete characterization both in terms of security and design of all currently existing group homomorphic encryption schemes, i.e., existing encryption schemes with a group homomorphic decryption function such as ElGamal and Paillier. To this end, we formalize and identify the basic underlying structure of all existing schemes and say that such schemes are of shift-type. Then, we construct an abstract scheme that represents all shift-type schemes (i.e., every scheme occurs as an instantiation of the abstract scheme) and prove its IND-CCA1 (resp. IND-CPA) security equivalent to the hardness of an abstract problem called Splitting Oracle-Assisted Subgroup Membership Problem (SOAP) (resp. Subgroup Membership Problem, SMP). Roughly, SOAP asks for solving an SMP instance, i.e., for deciding whether a given ciphertext is an encryption of the neutral element of the ciphertext group, while allowing access to a certain oracle beforehand. Our results allow for contributing to a variety of open problems such as the IND-CCA1 security of Paillier’s scheme, or the use of linear codes in group homomorphic encryption. Furthermore, we design a new cryptosystem which provides features that are unique up to now: Its IND-CPA security is based on the k-linear problem introduced by Shacham, and Hofheinz and Kiltz, while its IND-CCA1 security is based on a new k-problem that we prove to have the same progressive property, namely that if the k-instance is easy in the generic group model, the (k+1)-instance is still hard.     

A linear time approximation scheme for computing geometric maximum k-star

Facility dispersion seeks to locate the facilities as far away from each other as possible, which has attracted a multitude of research attention recently due to the pressing need on dispersing facilities in various scenarios. In this paper, as a facility dispersion problem, the geometric maximum k-star problem is considered. Given a set P of n points in the Euclidean plane, a k-star is defined as selecting k points from P and linking k ? 1 points to the center point. The maximum k-star problem asks to compute a k-star on P with the maximum total length over its k ? 1 edges. A linear time approximation scheme is proposed for this problem. It approximates the maximum k-star within a factor of ${(1+\epsilon)}$ in ${O(n+1/\epsilon^4 \log 1/\epsilon)}$ time for any ${\epsilon >0 }$ . To the best of the authors’ knowledge, this work presents the first linear time approximation scheme on the facility dispersion problems.     

The h,k-equal Partition Lattice is EL-shellable when h \geq k

It has been shown that the h, k-equal partition lattice \(\tilde \Pi_n^{h, k}\) is EL-shellable when h?<?k. We produce an EL-shelling for \(\tilde \Pi_n^{h, k}\) when n?≥?h?≥?k?≥?2 and observe that, in this shelling, there are no weakly decreasing chains. This shows that \(\tilde \Pi_n^{h, k}\) is contractible for such values of h and k, which can also be seen by the fact that \(\tilde \Pi_n^{h, k}\) is noncomplemented.     

Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric

In this paper, we examine the problem of finding the number ${k}$ of elements at a given location on the line segment between two elements in the geometry the Hausdorff metric imposes on the set ${\mathcal{H} (\mathbb{R}^{n})}$ of all nonempty compact sets in n-dimensional real space. We demonstrate that this problem is equivalent to counting the edge coverings of simple bipartite graphs. We prove the novel results that there exist no simple bipartite graphs with exactly 19 or 37 edge coverings, and hence there do not exist any two elements of ${\mathcal{H} (\mathbb{R}^{n})}$ with exactly 19 or 37 elements at a given location lying between them—although there exist pairs of elements in ${\mathcal{H} (\mathbb{R}^{n})}$ that have k elements at any given location between them for infinitely many values of k, including k from 1 to 18 and 20 to 36. This paper extends results in the geometry of the Hausdorff metric given in J. Geom. 92: 28–59 (2009). In addition to our results about counting edge coverings, we give a brief introduction to this geometry.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

Longest Partial Transversals in Plexes

A k-protoplex of order n is a partial latin square of order n such that each row and column contains precisely k entries and each symbol occurs precisely k times. If a k-protoplex is completable to a latin square, then it is a k-plex. A 1-protoplex is a transversal. Let \({\phi_k}\) denote the smallest order for which there exists a k-protoplex that contains no transversal, and let \({{{\phi_k}^{*}}}\) denote the smallest order for which there exists a k-plex that contains no transversal. We show that \({k \leqslant \phi_k = {{\phi_k}^{*}} \leqslant k+1}\) for all \({k \geqslant 6}\) . Given a k-protoplex P of order n, we define T(P) to be the size of the largest partial transversal in P. We explore upper and lower bounds for T(P). Aharoni et al. have conjectured that \({T(P) \geqslant (k-1)n/k}\) . We find that $$T(P) > max \{ k(1-n^{-1/2}), k-n/(n-k), n-O (nk^{-1/2}log^{3/2} k)\}$$ . In the special case of 3-protoplexes, we improve the lower bound for T(P) to 3n/5.     

Symmetric Graphs from Polytopes of High Rank

Given a polytope ${{\mathcal{P}}}$ of rank 2n, the faces of middle ranks n ? 1 and n constitute the vertices of a bipartite graph, the medial layer graph ${{M(\mathcal{P})}}$ of ${{\mathcal{P}}}$ . The group ${{D(\mathcal{P})}}$ of automorphisms and dualities of ${{\mathcal{P}}}$ has a natural action on this graph. We prove algebraic and combinatorial conditions on ${{\mathcal{P}}}$ that ensure this action is transitive on k-arcs in ${{M(\mathcal{P})}}$ for some small k (in particular focussing on k?=?3), and provide examples of families of polytopes that satisfy these conditions. We also examine how ${{D(\mathcal{P})}}$ acts on the k-stars based at vertices of ${{M(\mathcal{P})},}$ and describe self-dual regular polytopes (in particular those of rank 6) for which this action is transitive on the k-stars for small k.     

D’Atri Spaces of Type k and Related Classes of Geometries Concerning Jacobi Operators

In this article, we continue the study of the geometry of k-D’Atri spaces, 1≤k ≤n?1 (n denotes the dimension of the manifold), begun by the second author. It is known that k-D’Atri spaces, k≥1, are related to properties of Jacobi operators R _v along geodesics, since she has shown that ${\operatorname{tr}}R_{v}$ , ${\operatorname{tr}}R_{v}^{2}$ are invariant under the geodesic flow for any unit tangent vector v. Here, assuming that the Riemannian manifold is a D’Atri space, we prove in our main result that ${ \operatorname{tr}}R_{v}^{3}$ is also invariant under the geodesic flow if k≥3. In addition, other properties of Jacobi operators related to the Ledger conditions are obtained, and they are used to give applications to Iwasawa type spaces. In the class of D’Atri spaces of Iwasawa type, we show two different characterizations of the symmetric spaces of noncompact type: they are exactly the $\frak{C}$ -spaces, and on the other hand they are k -D’Atri spaces for some k≥3. In the last case, they are k-D’Atri for all k=1,…,n?1 as well. In particular, Damek–Ricci spaces that are k -D’Atri for some k≥3 are symmetric. Finally, we characterize k-D’Atri spaces for all k=1,…,n?1 as the $\frak{SC}$ -spaces (geodesic symmetries preserve the principal curvatures of small geodesic spheres). Moreover, applying this result in the case of 4 -dimensional homogeneous spaces, we prove that the properties of being a D’Atri (1-D’Atri) space, or a 3-D’Atri space, are equivalent to the property of being a k-D’Atri space for all k=1,2,3.     

On certain forms and quadrics related to symplectic dual polar spaces in characteristic 2

Let V be a 2n-dimensional vector space over a field ${\mathbb {F}}$ and ξ a non-degenerate alternating form defined on V. Let Δ be the building of type C _n formed by the totally ξ-isotropic subspaces of V and, for 1 ≤ k ≤ n, let ${\mathcal {G}_k}$ and Δ _k be the k-grassmannians of PG(V) and Δ, embedded in ${W_k=\wedge^kV}$ and in a subspace ${V_k\subseteq W_k}$ respectively, where ${{\rm dim}(V_k)={2n \choose k} - {2n \choose {k-2}}}$ . This paper is a continuation of Cardinali and Pasini (Des. Codes. Cryptogr., to appear). In Cardinali and Pasini (to appear), focusing on the case of k = n, we considered two forms α and β related to the notion of ‘being at non maximal distance’ in ${\mathcal {G}_n}$ and Δ _n and, under the hypothesis that ${{\rm char}(\mathbb {F}) \neq 2}$ , we studied the subspaces of W _n where α and β coincide or are opposite. In this paper we assume that ${{\rm char}(\mathbb {F}) = 2}$ . We determine which of the quadrics associated to α or β are preserved by the group ${G= {\rm Sp}(2n, \mathbb {F})}$ in its action on W _n and we study the subspace ${\mathcal {D}}$ of W _n formed by vectors v such that α(v, x) = β(v, x) for every ${x \in W_n}$ . Finally, we show how properties of ${\mathcal {D}}$ can be exploited to investigate the poset of G-invariant subspaces of V _k for k = n ? 2i and ${1\leq i \leq \lfloor n/2\rfloor}$ .     

A polynomial case of the cardinality-constrained quadratic optimization problem

We propose in this paper a fixed parameter polynomial algorithm for the cardinality-constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size n (the number of decision variables) and s (the cardinality), if the n?k largest eigenvalues of the coefficient matrix of the problem are identical for some 0 < k ≤ n, we can construct a solution algorithm with computational complexity of ${\mathcal{O}\left(n^{2k}\right)}$ . Note that this computational complexity is independent of the cardinality s and is achieved by decomposing the primary problem into several convex subproblems, where the total number of the subproblems is determined by the cell enumeration algorithm for hyperplane arrangement in ${\mathbb{R}^k}$ space.     

Dedekind zeta motives for totally real number fields

Let k be a totally real number field. For every odd n≥3, we construct an element in the category MT(k) of mixed Tate motives over k out of the quotient of a product of hyperbolic spaces by an arithmetic group. By a volume calculation, we prove that its period is a rational multiple of $\pi^{n[k:\mathbb{Q}]}\zeta^{*}_{k}(1-n)$ , where $\zeta^{*}_{k}(1-n)$ denotes the special value of the Dedekind zeta function of k. We deduce that the group $\mathrm {Ext}^{1}_{\mathrm {MT}(k)} (\mathbb{Q}(0),\mathbb{Q}(n))$ is generated by the cohomology of a quadric relative to hyperplanes, and that $\zeta^{*}_{k}(1-n)$ is a determinant of volumes of geodesic hyperbolic simplices defined over k.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

A lower bound on the barrier parameter of barriers for convex cones

Let ${K \subset \mathbb R^n}$ be a regular convex cone, let ${e_1,\ldots,e_n \in \partial K}$ be linearly independent points on the boundary of a compact affine section of the cone, and let ${x^* \in K^{0}}$ be a point in the relative interior of this section. For k =  1, . . . , n, let l _k be the line through the points e _k and x ^*, let y _k be the intersection point of l _k with ${\partial K}$ opposite to e _k , and let z _k be the intersection point of l _k with the linear subspace spanned by all points e _l , l =  1, . . . , n except e _k . We give a lower bound on the barrier parameter ν of logarithmically homogeneous self-concordant barriers ${F: K^{0}\to \mathbb R}$ on K in terms of the projective cross-ratios ${q_k = (e_k,x^*;y_k,z_k)}$ . Previously known lower bounds by Nesterov and Nemirovski can be obtained from our result as a special case. As an application, we construct an optimal barrier for the epigraph of the ${||\cdot||_{\infty}}$ -norm in ${\mathbb R^n}$ and compute lower bounds on the barrier parameter for the power cone and the epigraph of the ${||\cdot||_p}$ -norm in ${\mathbb R^2}$ .