Teambildung in dreiteiliger Grafik

Die Regierung will ein Team mit einem Alchemisten , einem Baumeister und einem Informatiker bilden .

Für eine gute Zusammenarbeit ist es wichtig, dass sich die 3 Teammitglieder mögen.

Deshalb versammelt sich die Regierung $k$Kandidaten für jeden Beruf und erstellt ihre "Gefällt mir" -Diagramme. Dies ist ein dreiteiliger Graph, zwischen dem sich eine Kante befindet$a$ und $b$ iff $a$ Likes $b$.

(Beachten Sie, dass die "like" -Relation symmetrisch, aber nicht transitiv ist, dh: if $a$ Likes $b$ dann $b$ Likes $a$, doch wenn $a$ Likes $b$ und $b$ Likes $c$dann nicht unbedingt $a$ Likes $c$).

Ist es immer möglich, ein Team zu bilden? Natürlich nicht. Zum Beispiel ist es möglich, dass kein Alchemist einen Baumeister mag.

Angenommen, das "Gefällt mir" -Diagramm hat die folgende Eigenschaft: In jeder Gruppe von 3 Alchemisten und 3 Buildern gibt es mindestens ein Alchemisten-Builder-Paar, das sich mag. Das Gleiche gilt für Alchemisten-Computeristen und Bauherren-Computeristen .

Ist es angesichts dieser Eigenschaft immer möglich, ein Team zu bilden, in dem sich alle drei Mitglieder mögen? Wenn ja, wie viele Kandidaten gibt es mindestens für jeden Typ ($k$) dass sich die Regierung versammeln muss?

Ich möchte sowohl k finden als auch beweisen, dass es das Minimum ist.

Eine möglicherweise verwandte Unterfrage ist: in einer Gruppe von $k$ Alchemisten und $k$Bauherren, wie viele Paare mögen sich mindestens? Zum$k=3$Unter der Annahme der Frage ist diese Zahl 1. Was ist mit $k>3$?

Eine dritte Frage lautet: Wie heißen diese Probleme?

Die Zusammenfassung bisher (als CW).

Yuval Filmus formulierte die Frage konventioneller um, als

Was ist das Minimum $k$ so dass für jede rot / blaue Färbung der Kanten von $K_{k,k,k}$ (das komplette 3-teilige Diagramm mit $k$ Eckpunkte in jeder Partition) gibt es entweder ein rotes Dreieck oder ein blaues $K_{3,3}$?

Erel bewies, dass die Untergrenze an $k$ ist mindestens 5 und verwendet dann eine SAT-Formulierung, die $k \ge 8$.

frafl zeigte, dass die obere grenze an $k$ ist höchstens 15. Aravind skizzierte ein schönes Argument für eine bessere Obergrenze.

Hier ist eine detailliertere Form von Aravinds Argumentation.

Wenn ein Scheitelpunkt $u$ in Partition $A$ ist rot mit 3 Eckpunkten verbunden $S$ in Partition $B$ und 3 Eckpunkte $T$ in Partition $C$, dann ist entweder ein rotes Dreieck beteiligt $u$ und jeweils einen Scheitelpunkt von $S$ und $T$, oder andernfalls $S\cup T$ induziert ein Blau $K_{3,3}$. Kein Scheitelpunkt kann also mehr als 2 rot verbundene Nachbarn in beiden Nachbarpartitionen haben.

Daher hat jeder Scheitelpunkt mindestens $k-2$blau verbundene Nachbarn in mindestens einer ihrer Nachbarpartitionen. Lassen$S$ seien Sie die Eckpunkte in $A$ die haben zumindest $k-2$ blau verbundene Nachbarn in $B$, und $T$ seien diese Eckpunkte in $A$ die haben zumindest $k-2$ blau verbundene Nachbarn in $C$;; beachten Sie, dass$A = S\cup T$. Wenn$S\cap T$ ist nicht leer, dann ergibt das Wechseln der Farben einen Widerspruch da $k\ge 5$. Also nimm an$S$ und $T$sind disjunkt. In der Tat ist jeder Scheitelpunkt in$S$ muss mit höchstens 2 Eckpunkten in blau verbunden sein $C$ (also zumindest rot verbunden $k-2$ Eckpunkte in $C$) und jeder Scheitelpunkt in $T$ muss mit höchstens 2 Eckpunkten in blau verbunden sein $B$ (und mindestens mit rot verbunden $k-2$ Eckpunkte in $C$).

Jetzt $k \ge 6$ Nehmen wir also ohne Verlust der Allgemeinheit an, dass $S$ enthält eine Teilmenge $S'$mit mindestens 3 Eckpunkten. Sie sind jeweils mindestens mit blau verbunden$k-2$ Eckpunkte in $B$Daher müssen diese Stadtteile eine gemeinsame Kreuzung haben $U$ mit mindestens $k-6$Eckpunkte. Wenn$k\ge 9$, dann $U$ enthält mindestens 3 Eckpunkte, also $S'\cup U$ induziert ein Blau $K_{3,3}$.

Dies zeigt, dass $k\ge 9$ reicht aus, um immer die Bedingungen zu erfüllen, und 9 ist daher eine Obergrenze für die gewünschte Menge.

Was bleibt, ist entweder ein Gegenbeispiel mit zu demonstrieren $k=8$ (was zeigen würde, dass die gewünschte Menge 9 ist), oder um das zu zeigen $k=8$ ist immer genug, um ein rotes Dreieck oder ein blaues zu garantieren $K_{3,3}$ (was zeigen würde, dass es 8 ist).

Eine Obergrenze für die erste Frage ist $k\leq 15$: Nehmen Sie eine Reihe von $5$ $a$s $A=\{a_1,\dots,a_5\}$, $5$ $b$s $B_1=\{b_1,\dots,b_5\}$ und $5$ $c$s $C_1=\{c_1,\dots,c_5\}$. Wir wissen, dass höchstens 2 der$a$s haben keinen Nachbarn unter den $B$s, sonst haben wir eine Ergänzung von a gefunden $K_{3,3}$, was verboten ist. Gleiches gilt für$a$s und $c$s. Es muss also einen geben$a_1'$das hat einen Nachbarn unter beiden Sätzen. Wir nennen diese Nachbarn$b_1'$ und $c_1'$ beziehungsweise.

Wir reparieren jetzt das Set $A$ und überlegen $10$ zusätzliche Paare von Sätzen von $b$s und $c$s $(B_i,C_i)_{i\in\{2,\dots,11\}}$ mit

Zumindest jetzt $3$ Paare von Sätzen stimmen darin überein $a$ nach dem Pigeonhole-Prinzip, dh es gibt eine $a_l\in A$ und paarweise unterschiedlich $m_1,m_2,m_3 \in \{1,\dots,11\}$ so dass $a_l = a_{m_1}' = a_{m_2}' = a_{m_3}'$. Jetzt$b_{m_p}'$ und $c_{m_p}'$ sind Nachbarn von $a_l$ zum $p\in\{1,\dots,3\}$. Also für einige$p,p'\in \{1,2,3\}$ der Satz $\{a_l,b_{m_p}',c_{m_{p'}}'\}$ induziert ein Dreieck von Freunden.

Nach András Salamons Kommentar beschloss ich, meine Frage als SAT-Problem zu stellen. Ich habe eine Javascript-Anwendung erstellt , die die Anzahl der Kandidaten pro Beruf als Eingabe verwendet ($k$) und generiert eine CNF-Formel, die ein Diagramm mit k Kandidaten pro Beruf definiert, das eine Kante zwischen jeweils zwei Tripeln enthält, aber KEIN Dreieck von Kandidaten enthält.

Wenn diese Formel erfüllt ist, bedeutet dies, dass $k$ist zu klein, um zu garantieren, dass es immer ein machbares Team gibt. Wenn diese Formel nicht zufriedenstellend ist, bedeutet dies Folgendes$k$ ist groß genug, da es immer ein machbares Team gibt.

Ich habe MiniSAT-Eingabedateien für erstellt $k=3..8$. Zum$k<=7$MiniSAT kehrte in weniger als einer Sekunde zurück und sagte, dass es zufriedenstellend ist (dh k ist zu klein). Hier ist die Zuordnung, für die MiniSAT gefunden wurde$k=7$. Dies bedeutet, dass 8 eine Untergrenze für die Anzahl der erforderlichen Kandidaten ist (besser als die Untergrenze von 7, die ich in der vorherigen Antwort gefunden habe).

Zum $k=8$Ich habe MiniSAT vor einigen Minuten gestartet und es läuft noch. Die Eingabedatei enthält 192 Variablen und 9920 Klauseln. Ich weiß nicht, wie lange es dauern wird, bis es fertig ist.

Aufgrund der Langsamkeit der Berechnung (und unter der Annahme, dass ich keinen Fehler in der Implementierung habe) vermute ich, dass 8 oder höchstens 9 Kandidaten ausreichen. Aber ich warte immer noch ab, was MiniSAT sagt.

Hier ist die aktuelle Ausgabe:

============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:           192                                         |
|  Number of clauses:            9920                                         |
|  Parse time:                   0.01 s                                       |
|  Simplification time:          0.03 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |     192     9920    86208 |     3637      100     16 |  0.003 % |
|       250 |     192     9920    86208 |     4001      250     22 |  0.003 % |
|       475 |     192     9920    86208 |     4401      475     25 |  0.003 % |
|       812 |     192     9920    86208 |     4841      812     29 |  0.003 % |
|      1318 |     192     9920    86208 |     5325     1318     31 |  0.003 % |
|      2077 |     192     9920    86208 |     5857     2077     32 |  0.003 % |
|      3216 |     192     9920    86208 |     6443     3216     35 |  0.003 % |
|      4924 |     192     9920    86208 |     7088     4924     34 |  0.003 % |
|      7486 |     192     9920    86208 |     7796     3907     35 |  0.003 % |
|     11330 |     192     9920    86208 |     8576     7751     36 |  0.003 % |
|     17096 |     192     9920    86208 |     9434     4866     39 |  0.003 % |
|     25745 |     192     9920    86208 |    10377     8762     36 |  0.003 % |
|     38719 |     192     9920    86208 |    11415     6081     39 |  0.003 % |
|     58180 |     192     9920    86208 |    12557     8338     35 |  0.003 % |
|     87372 |     192     9920    86208 |    13812    12272     37 |  0.003 % |
|    131161 |     192     9920    86208 |    15194     7495     36 |  0.003 % |
|    196845 |     192     9920    86208 |    16713    12107     38 |  0.003 % |
|    295371 |     192     9920    86208 |    18384     9989     32 |  0.003 % |
|    443160 |     192     9920    86208 |    20223    10152     40 |  0.003 % |
|    664843 |     192     9920    86208 |    22245    18854     37 |  0.003 % |
|    997368 |     192     9920    86208 |    24470    15595     40 |  0.003 % |
|   1496156 |     192     9920    86208 |    26917    15102     34 |  0.003 % |
|   2244338 |     192     9920    86208 |    29608    19091     42 |  0.003 % |
|   3366612 |     192     9920    86208 |    32569    16905     35 |  0.003 % |
|   5050023 |     192     9920    86208 |    35826    21640     37 |  0.003 % |
|   7575139 |     192     9920    86208 |    39409    34856     39 |  0.003 % |
|  11362814 |     192     9920    86208 |    43350    20735     38 |  0.003 % |
|  17044326 |     192     9920    86208 |    47685    35456     42 |  0.003 % |
|  25566595 |     192     9920    86208 |    52453    43639     34 |  0.003 % |
|  38349998 |     192     9920    86208 |    57699    48290     42 |  0.003 % |
|  57525103 |     192     9920    86208 |    63469    22810     40 |  0.003 % |
|  86287761 |     192     9920    86208 |    69816    55424     36 |  0.003 % |
| 129431749 |     192     9920    86208 |    76797    69548     43 |  0.003 % |

Nach weiteren 4 Stunden immer noch kein Ergebnis:

| 194147731 |     192     9920    86208 |    84477    67509     38 |  0.003 % |
| 291221704 |     192     9920    86208 |    92925    61375     34 |  0.003 % |

Obergrenze von 9:

Ich benutze die Charakterisierung von Yuval Filmus.

Angenommen, ein Scheitelpunkt in A hat sowohl in B als auch in C mindestens 3 rote Nachbarn. Dann gibt es entweder eine rote Kante zwischen den beiden Nachbarmengen, was zu einem roten Dreieck führt, oder es gibt ein blaues $K_{3,3}$.

Wenn also k> = 6 ist, erhalten wir, dass es in A drei Eckpunkte gibt, von denen jeder höchstens zwei rote Nachbarn in B hat (wlog-in B). Somit müssen diese 3 Eckpunkte mindestens k-6 blaue Nachbarn gemeinsam haben. Wenn$k \geq 9$Wir bekommen ein Blau $K_{3,3}$.

Als Untergrenze ist hier ein Beweis dafür, dass 5 Kandidaten für jeden Beruf nicht ausreichen. Angenommen, es gibt$n=5$ Kandidaten nummeriert $i=0..4$mit folgenden Beziehungen:

• Alchimist $i$ mag Builder $i$
• Baumeister $i$ mag Computerist $i$
• Computerist $i$ mag Alchemist $(i+1)\ mod\ n$.

Nach dem Pigeonhole-Prinzip gibt es in jeder Gruppe von 3 Alchemisten und 3 Bauherren mindestens 1 Paar, das sich mag (ebenso für die anderen Berufe). Der gesamte Graph ist jedoch ein einzelner Kreis mit der Länge 15, und es gibt keinen Kreis mit der Länge 3.

Die Konstruktion kann verlängert werden für $n=6$durch Hinzufügen des folgenden großen Kreises:

• $A[i]$ Likes $B[(i+1)\ mod\ n]$
• $B[i]$ Likes $C[(i+1)\ mod\ n]$
• $C[i]$ Likes $A[(i+2)\ mod\ n]$

Leider funktioniert die Konstruktion nicht für $n>6$. Es gibt immer noch eine große Lücke zwischen dieser Untergrenze und der Obergrenze von frafl von 15.