Polynomial-time perfect matchings in dense hypergraphs

Let H be a k-graph on n   vertices, with minimum codegree at least n/k+cn$n/k+cn$ for some fixed c>0$c>0$. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H   or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cn$n/k-cn$. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.     

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

A central limit theorem with applications to random hypergraphs

Define for each subset I included in {1, …, n} the σ-algebra F_I = σ {X_i:iϵI} with X₁, …, X_n independent random variables. In this paper we consider F_I-measurable random variables W_isubject to the centering condition E(W_I|F_J) = 0 a.s., unless I ⊂ J. A central limit theorem is proved for sums of a finite degree Z = Σ_{I included in {1, …, n},|I|⩽d} W_I under the condition that certain partial sums of the fourth moment vanish. This result is applied to generalizations of the random graph model. © 1996 John Wiley & Sons, Inc.     

Extremals of functions on graphs with applications to graphs and hypergraphs

The method used in an article by T. S. Matzkin and E. G. Straus [Canad. J. Math.17 (1965), 533–540] is generalized by attaching nonnegative weights to t-tuples of vertices in a hypergraph subject to a suitable normalization condition. The edges of the hypergraph are given weights which are functions of the weights of its t-tuples and the graph is given the sum of the weights of its edges. The extremal values and the extremal points of these functions are determined. The results can be applied to various extremal problems on graphs and hypergraphs which are analogous to P. Turán's Theorem [Colloq. Math.3 (1954), 19–30: (Hungarian) Mat. Fiz. Lapok48 (1941), 436–452].     

On the complexity of the dualization problem

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form.     

Exploring hypergraphs with martingales

Recently, in [Random Struct Algorithm 41 (2012), 441–450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 (2007), 133–142], in turn based on ideas of Martin‐Löf [J Appl Probab 23 (1986), 265–282], Karp [Random Struct Alg 1 (1990), 73–93] and Aldous [Ann Probab 25 (1997), 812–854], to prove asymptotic normality of the number L₁ of vertices in the largest component of the random r‐uniform hypergraph in the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of L₁, and joint asymptotic normality of L₁ and the number M₁ of edges of in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 (2016), 21–75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325–352, 2017     

Complex symplectic geometry with applications to ordinary differential operators

Complex symplectic spaces, and their Lagrangian subspaces, are defined in accord with motivations from Lagrangian classical dynamics and from linear ordinary differential operators; and then their basic algebraic properties are established. After these purely algebraic developments, an Appendix presents a related new result on the theory of self-adjoint operators in Hilbert spaces, and this provides an important application of the principal theorems.

     

Divisibility of multilinear mappings with applications to affine differential geometry

For real finite-dimensional vector spaces V, W we call a bilinear symmetric mapping h?:?V?×?V?→?W non-degenerate if the components of h with respect to a certain basis are linearly independent and non-degenerate. We say that a symmetric trilinear mapping C?:?V?×?V?×?V?→?W is divisible by h if there exists a linear form α such that C(v,?v,?v)?=?α(v)h(v,?v) for every v?∈?V. In affine differential geometry of affine immersions h is the second fundamental form and C – the cubic form of the immersion. The immersion has pointwise planar normal sections if h(v,?v)?∧?C(v,?v,?v)?=?0 for every tangent vector v. We prove that it implies that C is divisible by h if h is non-degenerate and the codimension is greater than two. For immersions with Wiehe's or Sasaki's choice of transversal bundles divisibility of C by h implies vanishing of C.     

On Pfaff systems with coefficients and their applications in differential geometry

We prove that a Pfaff system with coefficients in , p>2, in a simply-connected open subset Ω of has at least a nontrivial solution of class provided that its coefficients satisfies a compatibility condition in the distributional sense. If in addition the set Ω is connected, the Cauchy problem associated with the Pfaff system has a unique solution. An application of this result is that the fundamental theorem of surface theory holds under the assumption that the first and second fundamental forms are respectively of class and , with p>2, and satisfy together the Gauss and Codazzi–Mainardi equations in the distributional sense.     

On dualization of double frobenius algebras

Double Frobenius algebras (or dF-algebras) were recently introduced by the author. The concept generalizes finite-dimensional Hopf algebras, adjacency algebras of (non-commutative) association schemes, and C-algebras (or character algebras). In this paper we define a dualization construction of a dF-algebra, the so-called linear dual. We show that in the case of a Hopf algebra the linear dual gives the usual dual Hopf algebra and in the case of a C-algebra it essentially gives the usual Kawada’s dual.     

Polynomial-time versions of Sylow's theorem

Let G be a subgroup of S_n, given in terms of a generating set of permutations, and let p be a prime divisor of |G|. If G is solvable—and, more generally, if the nonabelian composition factors of G are suitably restricted—it is shown that the following can be found in polynomial time: a Sylow p-subgroup of G containing a given p-subgroup, and an element of G conjugating a given Sylow p-subgroup to another. Similar results are proved for Hall subgroups of solvable groups and a version of the Schur-Zassenhaus theorem is obtained.     

Polynomial-time approximation of largest simplices in V-polytopes

This paper considers the problem of computing the squared volume of a largest j-dimensional simplex in an arbitrary d-dimensional polytope P given by its vertices (a “V-polytope”), for arbitrary integers j and d with 1⩽j⩽d. The problem was shown by Gritzmann, Klee and Larman to be $\text{NP}$-hard. This paper examines the possible accuracy of deterministic polynomial-time approximation algorithms for the problem. On the negative side, it is shown that unless $\text{P}\text{=}\text{NP}$, no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the $\text{NP}$-hardness and inapproximability continue to hold when the polytope P is restricted to be an affine crosspolytope.On the positive side, a simple deterministic polynomial-time approximation algorithm for the problem is described. The algorithm takes as input integers j and d with 1⩽j⩽d and a V-polytope P of dimension d. It returns a j-simplex S⊂P such that$\text{vol}{}^2\text{(T)}\text{vol}{}^2\text{(S)}\text{⩽A(Bj)}{}^{\mathrm{j}}\text{,}$where T is any largest j-simplex in P, and A and B are positive constants independent of j,d,P.     

New applications of random sampling in computational geometry

This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requiresO(s ^d+ ) expected preprocessing time to build a search structure for an arrangement ofs hyperplanes ind dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query pointp, the cell of the arrangement containingp can be found inO(logs) worst-case time. (The bound holds for any fixed >0, with the constant factors dependent ond and .) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expectedO(n ^[d/2]) time, wheren is the total number of vertices of the two polytopes. This matches previous results [10] for the cased = 3 and extends them. Another algorithm samples points in the plane to determine their orderk Voronoi diagram, and requires expectedO(s ¹⁺ k) time fors points. (It is assumed that no four of the points are cocircular.) This sharpens the boundO(sk ² logs) for Lee's algorithm [21], andO(s ² logs+k(s–k) log² s) for Chazelle and Edelsbrunner's algorithm [4]. Finally, random sampling is used to show that any set ofs points inE ³ hasO(sk ² log⁸ s/(log logs)⁶) distinctj-sets withjk. (ForS E ^d , a setS S with |S| =j is aj-set ofS if there is a half-spaceh ⁺ withS =S h ⁺.) This sharpens with respect tok the previous boundO(sk ⁵) [5]. The proof of the bound given here is an instance of a probabilistic method [15].A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986.     

Covers in hypergraphs

Let α(H) denote the stability number of a hypergraphH. The covering number ?(H) is defined as the minimal number of edges fromH to cover its vertex setV(H). The main result is the following extension of König’s wellknown theorem: If α(H′)≧|V(H′)|/2 holds for every section hypergraphH′ ofH then ?(H)≦α(H). This theorem is applied to obtain upper bounds on certain covering numbers of graphs and hypergraphs. In par ticular, we prove a conjecture of B. Bollobás involving the hypergraph Turán numbers.     

Independence in hypergraphs

Suppose an integral function (|A|)q₁ defined on the subsets of edges of a hypergraph (X,u,) satisfies the following two conditions: 1) any set W u such that |A|(|A|) for any AW is matroidally independent; 2) if W is an independent set, then there exists a unique partitionW=T₁+ T₂+...+T_v such that |T ⁱ |=(|T ⁱ |),i1:v, and for any AW, |A|(|A|) there exists a T_i such that AT_i. The form of such a function is found, in terms of parameters of generalized connected components, hypercycles, and hypertrees.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 196–204, 1982.