Timeline for Creating $p$ intersecting sets of $q$ equally distributed integers between $1$ and $r$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 21, 2017 at 15:54 | comment | added | Alice J. | @ThomasKalinowski Thank you for the help, I'll explore the equivalent formulations. The last necessary condition is still not enough unfortunately. | |
| Mar 20, 2017 at 21:32 | comment | added | Thomas Kalinowski | The graph formulation gives the necessary condition $pq(q-1)\geqslant r(r-1)$ (I did not check if that's implied by Fedor's conditions). | |
| Mar 20, 2017 at 21:23 | comment | added | Thomas Kalinowski | Interpreting the matrix as the adjacency matrix of a graph gives the following: Given $p$, $q$ and $r$, does there exist a bipartite graph $G=(A\cup B,E)$ with parts of size $|A|=r$ and $|B|=p$ such that (1) every vertex in $A$ has degree $pq/r$, (2) every vertex in $B$ has degree $q$, and (3) the distance between any two vertices in $A$ is 2. | |
| Mar 20, 2017 at 21:19 | comment | added | Thomas Kalinowski | Here is an equivalent formulation: You are looking for $(0,1)$-matrices of size $r\times p$ such that (1) every row has sum $pq/r$, (2) every column has sum $q$, and (3) no two columns are orthogonal. mathoverflow.net/q/36642/12674 might be relevant. | |
| Mar 20, 2017 at 15:23 | comment | added | Alice J. | @GerhardPaseman Thanks a lot, I will look it up ! | |
| Mar 20, 2017 at 15:08 | comment | added | Gerhard Paseman | Also, since every two blocks have an element in common, you might be considering a combinatorial projective plane. The Handbook of Combinatorial Designs should help. Gerhard "Handing It Over To Handbooks" Paseman, 2017.03.20. | |
| Mar 20, 2017 at 15:03 | comment | added | Gerhard Paseman | Look up balanced incomplete block designs. That or a minor variation should apply, and you will see some necessary conditions on the parameters. Gerhard "Block Designs Clear The Way" Paseman, 2017.03.20. | |
| Mar 20, 2017 at 15:02 | comment | added | Alice J. | @FedorPetrov Thank you. I actually saw this one, unfortunately it is not enough in my case. I feel like we are considering that each of the intersecting pairs provided by the elements are independent while they are linked by the fact that each set has $q$ elements. | |
| Mar 20, 2017 at 14:29 | comment | added | Fedor Petrov | There is an element belonging to at least $p(p-1)/2r$ pairs of sets, thus necessary condition is that $pq(pq-r)/2r^2\ge p(p-1)/2r$, $q(pq-r)\ge r(p-1)$, $r\le pq^2/(p+q-1)$. | |
| Mar 20, 2017 at 14:14 | history | asked | Alice J. | CC BY-SA 3.0 |