71:. The matroid has rank 4: all sets of three or fewer elements are independent, and 65 of the 70 possible sets of four elements are also independent. The five exceptions are four-element circuits in the matroid. Four of these five circuits are formed by faces of the cuboid (omitting two opposite faces). The fifth circuit connects two opposite edges of the cuboid, each of which is shared by two of the chosen four faces.
20:
277:
schemes in which any coalition of users who can gain any information about a secret key can learn the whole key (these coalitions are the dependent sets of the matroid), and in which the shared information contains no more information than is needed to represent the key. These matroids also have
308:
follows from a certain intersection property of the flats of the matroid; the Vámos matroid provides an example of a matroid in which the intersection property is not true, but the Hahn–Banach theorem nevertheless
453:
113:
of these vectors is isomorphic to the Vámos matroid. Indeed, it is one of the smallest non-representable matroids, and served as a counterexample to a conjecture of
540:
244:
264:
206:
186:
162:
142:
691:
621:
569:
321:
536:, Prop. 6.4.10, p. 196. A proof of representability for every matroid with fewer elements or the same number but smaller rank was given by
506:
882:
731:
921:
836:
726:
616:
102:, but it is not identically self-dual (the isomorphism requires a nontrivial permutation of the matroid elements).
654:
305:
997:
114:
768:
Brickell, Ernest F.; Davenport, Daniel M. (1991), "On the classification of ideal secret sharing schemes",
538:
Fournier, Jean-Claude (1970), "Sur la représentation sur un corps des matroïdes à sept et huit éléments",
286:
44:
770:
973:
267:
110:
48:
963:
877:
52:
74:
Another way of describing the same structure is that it has two elements for each vertex of the
502:
290:
105:
The Vámos matroid cannot be represented over any field. That is, it is not possible to find a
496:
930:
891:
845:
808:
779:
740:
700:
663:
630:
578:
313:
301:
273:
The Vámos matroid is not a secret-sharing matroid. Secret-sharing matroids describe "ideal"
944:
905:
859:
820:
754:
712:
675:
642:
590:
553:
940:
901:
873:
855:
816:
750:
708:
671:
638:
586:
549:
501:, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 76,
294:
216:
165:
221:
63:
The Vámos matroid has eight elements, which may be thought of as the eight vertices of a
977:
649:
274:
249:
209:
191:
171:
147:
127:
88:
991:
935:
896:
745:
279:
121:
75:
106:
99:
92:
919:
Bachem, Achim; Wanka, Alfred (1988), "Separation theorems for oriented matroids",
23:
The Vámos matroid; the shaded parallelograms depict its five circuits of size four
492:
28:
958:
Merino, Criel; Ramírez-Ibáñez, Marcelino; Sanchez, Guadalupe Rodríguez (2012),
634:
812:
582:
109:, and a system of eight vectors within that space, such that the matroid of
850:
704:
19:
270:
of sets of these eight elements equals the rank function of the matroid.
784:
40:
448:{\displaystyle x^{4}+4x^{3}+10x^{2}+15x+5xy+15y+10y^{2}+4y^{3}+y^{4}.}
689:
Ingleton, A. W.; Main, R. A. (1975), "Non-algebraic matroids exist",
567:
Ingleton, A. W. (1959), "A note on independence functions and rank",
68:
667:
117:
that the matroids on eight or fewer elements were all representable.
799:
Simonis, Juriaan; Ashikhmin, Alexei (1998), "Almost affine codes",
91:, meaning that all of its circuits have size at least equal to its
968:
215:
The Vámos matroid is not algebraic. That is, there do not exist a
164:
has five or more elements. However, it is not possible to test in
18:
78:, and a four-element circuit for each edge of the diamond graph.
64:
55:, who first described it in an unpublished manuscript in 1968.
844:(3): 363–365, correction, ibid. 17 (1974), no. 4, 623,
285:
The Vámos matroid has no adjoint. This means that the
834:
Cheung, Alan L. C. (1974), "Adjoints of a geometry",
652:(1982), "Complexity of matroid property algorithms",
324:
252:
224:
194:
174:
150:
130:
619:; Walton, P. N. (1981), "Detecting matroid minors",
447:
258:
238:
200:
180:
156:
136:
476:On the representation of independence structures
297:into another geometric lattice of the same rank.
8:
124:for the matroids representable over a field
43:over a set of eight elements that cannot be
692:Bulletin of the London Mathematical Society
622:Journal of the London Mathematical Society
570:Journal of the London Mathematical Society
51:. It is named after English mathematician
967:
934:
895:
849:
783:
744:
541:Comptes rendus de l'Académie des sciences
436:
423:
407:
361:
345:
329:
323:
251:
228:
223:
193:
173:
168:whether it is a minor of a given matroid
149:
129:
487:
485:
466:
98:The Vámos matroid is isomorphic to its
729:(1992), "On secret-sharing matroids",
304:. In oriented matroids, a form of the
960:The Tutte polynomial of some matroids
880:(1978), "Orientability of matroids",
603:
533:
521:
16:Matroid with no linear representation
7:
14:
883:Journal of Combinatorial Theory
801:Designs, Codes and Cryptography
732:Journal of Combinatorial Theory
293:of the Vámos matroid cannot be
246:and a set of eight elements of
837:Canadian Mathematical Bulletin
1:
936:10.1016/0012-365X(88)90006-4
897:10.1016/0095-8956(78)90080-1
746:10.1016/0095-8956(92)90007-K
1014:
495:(2006), "Example 2.1.22",
655:SIAM Journal on Computing
300:The Vámos matroid can be
635:10.1112/jlms/s2-23.2.193
316:of the Vámos matroid is
813:10.1023/A:1008244215660
583:10.1112/jlms/s1-34.1.49
120:The Vámos matroid is a
87:The Vámos matroid is a
45:represented as a matrix
851:10.4153/CMB-1974-066-5
449:
260:
240:
202:
182:
158:
138:
24:
771:Journal of Cryptology
450:
261:
241:
203:
183:
159:
139:
22:
922:Discrete Mathematics
705:10.1112/blms/7.2.144
322:
268:transcendence degree
250:
222:
192:
172:
148:
128:
978:2012arXiv1203.0090M
878:Las Vergnas, Michel
306:Hahn–Banach theorem
239:{\displaystyle L/K}
210:independence oracle
111:linear independence
785:10.1007/BF00196772
474:Vámos, P. (1968),
445:
256:
236:
198:
188:, given access to
178:
154:
134:
25:
625:, Second Series,
573:, Second Series,
291:geometric lattice
259:{\displaystyle L}
201:{\displaystyle M}
181:{\displaystyle M}
157:{\displaystyle F}
137:{\displaystyle F}
1005:
982:
980:
971:
955:
949:
947:
938:
916:
910:
908:
899:
874:Bland, Robert G.
870:
864:
862:
853:
831:
825:
823:
796:
790:
788:
787:
765:
759:
757:
748:
723:
717:
715:
686:
680:
678:
648:Jensen, Per M.;
645:
613:
607:
601:
595:
593:
564:
558:
556:
531:
525:
519:
513:
511:
489:
480:
478:
471:
454:
452:
451:
446:
441:
440:
428:
427:
412:
411:
366:
365:
350:
349:
334:
333:
314:Tutte polynomial
278:applications in
266:, such that the
265:
263:
262:
257:
245:
243:
242:
237:
232:
207:
205:
204:
199:
187:
185:
184:
179:
163:
161:
160:
155:
143:
141:
140:
135:
1013:
1012:
1008:
1007:
1006:
1004:
1003:
1002:
988:
987:
986:
985:
957:
956:
952:
918:
917:
913:
872:
871:
867:
833:
832:
828:
798:
797:
793:
767:
766:
762:
725:
724:
720:
688:
687:
683:
668:10.1137/0211014
650:Korte, Bernhard
647:
615:
614:
610:
602:
598:
566:
565:
561:
537:
532:
528:
520:
516:
509:
493:Oxley, James G.
491:
490:
483:
473:
472:
468:
463:
432:
419:
403:
357:
341:
325:
320:
319:
248:
247:
220:
219:
217:field extension
190:
189:
170:
169:
166:polynomial time
146:
145:
126:
125:
122:forbidden minor
84:
61:
17:
12:
11:
5:
1011:
1009:
1001:
1000:
998:Matroid theory
990:
989:
984:
983:
950:
929:(3): 303–310,
911:
865:
826:
807:(2): 179–197,
791:
778:(2): 123–134,
760:
727:Seymour, P. D.
718:
681:
662:(1): 184–190,
629:(2): 193–203,
617:Seymour, P. D.
608:
596:
559:
526:
524:, pp. 170–172.
514:
507:
498:Matroid Theory
481:
465:
464:
462:
459:
458:
457:
456:
455:
444:
439:
435:
431:
426:
422:
418:
415:
410:
406:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
364:
360:
356:
353:
348:
344:
340:
337:
332:
328:
310:
298:
295:order-embedded
283:
275:secret sharing
271:
255:
235:
231:
227:
213:
197:
177:
153:
133:
118:
103:
96:
89:paving matroid
83:
80:
60:
57:
15:
13:
10:
9:
6:
4:
3:
2:
1010:
999:
996:
995:
993:
979:
975:
970:
965:
961:
954:
951:
946:
942:
937:
932:
928:
924:
923:
915:
912:
907:
903:
898:
893:
890:(1): 94–123,
889:
885:
884:
879:
875:
869:
866:
861:
857:
852:
847:
843:
839:
838:
830:
827:
822:
818:
814:
810:
806:
802:
795:
792:
786:
781:
777:
773:
772:
764:
761:
756:
752:
747:
742:
738:
734:
733:
728:
722:
719:
714:
710:
706:
702:
698:
694:
693:
685:
682:
677:
673:
669:
665:
661:
657:
656:
651:
644:
640:
636:
632:
628:
624:
623:
618:
612:
609:
605:
600:
597:
592:
588:
584:
580:
576:
572:
571:
563:
560:
555:
551:
548:: A810–A813,
547:
543:
542:
535:
530:
527:
523:
518:
515:
510:
508:9780199202508
504:
500:
499:
494:
488:
486:
482:
477:
470:
467:
460:
442:
437:
433:
429:
424:
420:
416:
413:
408:
404:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
362:
358:
354:
351:
346:
342:
338:
335:
330:
326:
318:
317:
315:
311:
307:
303:
299:
296:
292:
288:
284:
281:
280:coding theory
276:
272:
269:
253:
233:
229:
225:
218:
214:
211:
195:
175:
167:
151:
131:
123:
119:
116:
112:
108:
104:
101:
97:
94:
90:
86:
85:
81:
79:
77:
76:diamond graph
72:
70:
66:
58:
56:
54:
50:
46:
42:
38:
34:
33:Vámos matroid
30:
21:
959:
953:
926:
920:
914:
887:
886:, Series B,
881:
868:
841:
835:
829:
804:
800:
794:
775:
769:
763:
739:(1): 69–73,
736:
735:, Series B,
730:
721:
696:
690:
684:
659:
653:
626:
620:
611:
604:Oxley (2006)
599:
574:
568:
562:
545:
544:, Sér. A-B,
539:
534:Oxley (2006)
529:
522:Oxley (2006)
517:
497:
475:
469:
287:dual lattice
107:vector space
100:dual matroid
73:
62:
36:
32:
26:
699:: 144–146,
208:through an
144:, whenever
53:Peter Vámos
29:mathematics
461:References
82:Properties
59:Definition
37:Vámos cube
969:1203.0090
606:, p. 511.
577:: 49–56,
47:over any
992:Category
302:oriented
115:Ingleton
974:Bibcode
945:0955127
906:0485461
860:0373976
821:1614357
755:1182458
713:0369110
676:0646772
643:0609098
591:0101848
554:0263665
289:of the
41:matroid
943:
904:
858:
819:
753:
711:
674:
641:
589:
552:
505:
309:holds.
69:cuboid
31:, the
964:arXiv
49:field
39:is a
503:ISBN
312:The
93:rank
65:cube
931:doi
892:doi
846:doi
809:doi
780:doi
741:doi
701:doi
664:doi
631:doi
579:doi
546:270
67:or
35:or
27:In
994::
972:,
962:,
941:MR
939:,
927:70
925:,
902:MR
900:,
888:24
876:;
856:MR
854:,
842:17
840:,
817:MR
815:,
805:14
803:,
774:,
751:MR
749:,
737:56
709:MR
707:,
695:,
672:MR
670:,
660:11
658:,
646:.
639:MR
637:,
627:23
587:MR
585:,
575:34
550:MR
484:^
401:10
392:15
371:15
355:10
981:.
976::
966::
948:.
933::
909:.
894::
863:.
848::
824:.
811::
789:.
782::
776:4
758:.
743::
716:.
703::
697:7
679:.
666::
633::
594:.
581::
557:.
512:.
479:.
443:.
438:4
434:y
430:+
425:3
421:y
417:4
414:+
409:2
405:y
398:+
395:y
389:+
386:y
383:x
380:5
377:+
374:x
368:+
363:2
359:x
352:+
347:3
343:x
339:4
336:+
331:4
327:x
282:.
254:L
234:K
230:/
226:L
212:.
196:M
176:M
152:F
132:F
95:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
