← All problems

Király–Nagy–Pálvölgyi–Visontai conjecture on weakly cross intersecting set pair systems

11 years old · traced to

Let A1,A2,…,AmA_1,A_2,\dots,A_m and B1,B2,…,BmB_1,B_2,\dots,B_m be sets such that ∣Ai∣=k|A_i|=k and ∣Bi∣=l|B_i|=l for all 1≤i≤m1\le i\le m. Suppose that Ai∩Bi=∅A_i\cap B_i=\emptyset for all 1≤i≤m1\le i\le m, and that Ai∩Bj≠∅A_i\cap B_j\neq\emptyset or Aj∩Bi≠∅A_j\cap B_i\neq\emptyset for all distinct i,ji,j. Such a system is called a (k,l)(k,l)-weakly cross intersecting set pair system, and let mmax⁡(k,l)m_{\max}(k,l) denote the largest m∈Zm\in\mathbb{Z} for which one exists.

Király–Nagy–Pálvölgyi–Visontai conjecture.

mmax⁡(k,l)≤2(k+lk).m_{\max}(k,l)\leq 2\binom{k+l}{k}.

Tuza's upper bound and the cited construction show that the conjectured bound is asymptotically sharp up to a factor approaching 11. The conjecture concerns the maximum size of weakly cross intersecting set pair systems.

References
  1. Zoltán Lóránt Nagy and Balázs Patkós, “On the number of maximal intersecting k-uniform families and further applications of Tuza's set pair method”, arXiv:1501.00648 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.