Constructing set systems with prescribed intersection sizes

Let f be an n-variable polynomial with positive integer coefficients, and let be a set system on the n-element universe. We define a set system and prove that f(H_i1∩H_i2∩∩H_ik)=|G_i1∩G_i2∩∩G_ik|, for any 1km, where f(H_i1∩H_i2∩∩H_ik) denotes the value of f on the characteristic vector of H_i1∩H_i2∩∩H_ik. The construction of is a straightforward polynomial-time algorithm from the set system and the polynomial f. In this paper we use this algorithm for constructing set systems with prescribed intersection sizes modulo an integer. As a by-product of our method, some upper bounds on the number of sets in set systems with prescribed intersection sizes are extended.     

Fractional set systems with few disjoint pairs

Ahlswede (1980) [1] and Frankl (1977) [5] independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) [3] gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are {0,1}-valued. In this paper we show that this technique does not extend to t-intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding {0,1}-valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set.     

On set systems with restricted k‐wise L‐intersection modulo a prime,and beyond

In this paper, we derive the following bound on the size of a k‐wise L‐intersecting family (resp. cross L‐intersecting families) modulo a prime number:

• (i) Let p be a prime, , and . Let and be two disjoint subsets of such that , or . Suppose that is a family of subsets of [n] such that for every and for every collection of k distinct subsets in . Then, This result may be considered as a modular version of Theorem 1.10 in [J. Q. Liu, S. G. Zhang, S. C. Li, H. H. Zhang, Eur. J. Combin. 58 (2016), 166‐180].
• (ii) Let p be a prime, , and . Let and be two subsets of such that , or , or . Suppose that and are two families of subsets of [n] such that (1) for every pair ; (2) for every ; (3) for every . Then,

This result extends the well‐known Alon–Babai–Suzuki theorem to two cross L‐intersecting families.     

Disjoint systems

A disjoint system of type (?, ?, k, n) is a collection ?? = {??₁,…, ??_m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair ??_i and ??_j of distinct members of ?? and for every A ? ??_i there exists a B ? ??_j that does not intersect A. Let D_n (?, ?, k) denote the maximum possible cardinality of a disjoint system of type (?, ?, k, n). It is shown that for every fixed k ? 2,. This settles a problem of Ahlswede, Cai, and Zhang. Several related problems are considered as well.     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

Disjoint empty disks supported by a point set

For a planar point-set P, let D(P) be the minimum number of pairwise-disjoint empty disks such that each point in P lies on the boundary of some disk. Further define D(n) as the maximum of D(P) over all n-element point sets. Hosono and Urabe recently conjectured that ${D(n) = \lceil n/2 \rceil}$ . Here we show that ${D(n) \geq n/2 + n/236 - O(\sqrt{n})}$ and thereby disprove this conjecture.     

Simultaneous intersection representation of pairs of graphs

We characterize the pairs (G₁, G₂) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G₁ is the intersection graph of the subsets and G₂ is the intersection graph of their complements. We also consider several special cases and explore bounds on the size of the universal set. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 171–190, 1999     

A set intersection theorem and applications

Using Scarf's algorithm for “computing” a fixed point of a continuous mapping, the following is proved: LetM ₁ ? M _n be closed sets inR ⁿ which cover the standard simplexS, so thatM _i coversS _i , the face ofS opposite vertexi. We say a point inS iscompletely labeled if it belongs to everyM _i andk-almost-completely labeled if it belongs to all butM _k . Then there exists a closed setT ofk-almost-completely labeled points which connects vertexk with some completely labeled point. This result is used to prove Browder's theorem (a parametric fixed-point theorem) inR ⁿ . It is also used to generate “algorithms” for the nonlinear complementarity problem which are analogous to the Lemke—Howson algorithm and the Cottle—Dantzig algorithm, respectively, for the linear complementarity problem.     

Disjoint covering systems of rational beatty sequences

We prove that for a disjoint covering system with rational moduli, the two largest numerators of the moduli are identical. Furthermore, if the two moduli corresponding to these two identical numerators are distinct, then actually the three largest numerators of the moduli are identical for a system with at least three moduli.     

Functional encryption for set intersection in the multi-client setting

Designs, Codes and Cryptography - Functional encryption for set intersection (FE-SI) in the multi-client environment is that each client i encrypts a set $$X_i$$ associated with time T by using its...     

Exact and heuristic approaches for the set cover with pairs problem

This work deals with the set cover with pairs problem (SCPP) which is a generalization of the set cover problem (SCP). In the SCPP the elements have to be covered by specific pairs of objects, instead of a single object. We propose a new mathematical formulation using extended variables that is capable of consistently solve instances with up to 500 elements and 500 objects. We also developed an ILS heuristic which was capable of finding better solutions for several tested instances in less computational time.     

Unordered pairs in the set theory of Bourbaki 1949

Working informally in ZF, we build a pair of supertransitive models of Z, of which pair the union is shown to be a supertransitive model of Bourbaki’s 1949 system for set theory in which some unordered pair fails to exist even though ordered pairs are available.     

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G₁(V,E₁),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K₅ or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n⁴)-time algorithms to compute a SEFE.     

Disjoint cycles with chords in graphs

Let be integers, , , and let for each , be a cycle or a tree on vertices. We prove that every graph G of order at least n with contains k vertex disjoint subgraphs , where , if is a tree, and is a cycle with chords incident with a common vertex, if is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009     

The intersection problem for m-cycle systems

Let I_m(v) denote the set of integers k for which a pair of m-cycle systems of K_v, exist, on the same vertex set, having k common cycles. Let J_m(v) = {0, 1, 2,…, t_v ?2, t_v} where t_v = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when I_m(2mn + x) = J_m(2mn + x), for both m even and m odd. Results include J^m(2mn + 1) = I^m(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K_2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc.