PageSourceSearch

https://matroidunion.org/

html matroidunion.org collected 2026-10-02 14:42:05 UTC 81,063 bytes, 816 lines download raw bytes

1<!DOCTYPE html>
2<!--[if IE 6]>
3<html id="ie6" lang="en-US">
4<![endif]-->
5<!--[if IE 7]>
6<html id="ie7" lang="en-US">
7<![endif]-->
8<!--[if IE 8]>
9<html id="ie8" lang="en-US">
10<![endif]-->
11<!--[if !(IE 6) & !(IE 7) & !(IE 8)]><!-->
12<html lang="en-US">
13<!--<![endif]-->
14<head>
15<meta charset="UTF-8" />
16<meta name="viewport" content="width=device-width" />
17<title>The Matroid Union | A blog for and by the matroid community</title>
18<link rel="profile" href="http://gmpg.org/xfn/11" />
19<link rel="stylesheet" type="text/css" media="all" href="https://matroidunion.org/wp-content/themes/twentyeleven-child/style.css" />
20<link rel="pingback" href="https://matroidunion.org/xmlrpc.php" />
21<!--[if lt IE 9]>
22<script src="https://matroidunion.org/wp-content/themes/twentyeleven/js/html5.js" type="text/javascript"></script>
22
23<![endif]-->
24<meta name='robots' content='max-image-preview:large' />
25	<style>img:is([sizes="auto" i], [sizes^="auto," i]) { contain-intrinsic-size: 3000px 1500px }</style>
26	
27<script>
28MathJax = {
29  tex: {
30    inlineMath: [['$','$'],['\\(','\\)']], 
31    processEscapes: true
32  },
33  options: {
34    ignoreHtmlClass: 'tex2jax_ignore|editor-rich-text'
35  }
36};
37
38</script>
38
39<link rel='dns-prefetch' href='//cdn.jsdelivr.net' />
40<link rel="alternate" type="application/rss+xml" title="The Matroid Union &raquo; Feed" href="https://matroidunion.org/?feed=rss2" />
41<link rel="alternate" type="application/rss+xml" title="The Matroid Union &raquo; Comments Feed" href="https://matroidunion.org/?feed=comments-rss2" />
42<script type="text/javascript">
43/* <![CDATA[ */
44window._wpemojiSettings = {"baseUrl":"https:\/\/s.w.org\/images\/core\/emoji\/16.0.1\/72x72\/","ext":".png","svgUrl":"https:\/\/s.w.org\/images\/core\/emoji\/16.0.1\/svg\/","svgExt":".svg","source":{"concatemoji":"https:\/\/matroidunion.org\/wp-includes\/js\/wp-emoji-release.min.js?ver=6.8.10"}};
45/*! This file is auto-generated */
46!function(s,n){var o,i,e;function c(e){try{var t={supportTests:e,timestamp:(new Date).valueOf()};sessionStorage.setItem(o,JSON.stringify(t))}catch(e){}}function p(e,t,n){e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(t,0,0);var t=new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data),a=(e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(n,0,0),new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data));return t.every(function(e,t){return e===a[t]})}function u(e,t){e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(t,0,0);for(var n=e.getImageData(16,16,1,1),a=0;a<n.data.length;a++)if(0!==n.data[a])return!1;return!0}function f(e,t,n,a){switch(t){case"flag":return n(e,"\ud83c\udff3\ufe0f\u200d\u26a7\ufe0f","\ud83c\udff3\ufe0f\u200b\u26a7\ufe0f")?!1:!n(e,"\ud83c\udde8\ud83c\uddf6","\ud83c\udde8\u200b\ud83c\uddf6")&&!n(e,"\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc65\udb40\udc6e\udb40\udc67\udb40\udc7f","\ud83c\udff4\u200b\udb40\udc67\u200b\udb40\udc62\u200b\udb40\udc65\u200b\udb40\udc6e\u200b\udb40\udc67\u200b\udb40\udc7f");case"emoji":return!a(e,"\ud83e\udedf")}return!1}function g(e,t,n,a){var r="undefined"!=typeof WorkerGlobalScope&&self instanceof WorkerGlobalScope?new OffscreenCanvas(300,150):s.createElement("canvas"),o=r.getContext("2d",{willReadFrequently:!0}),i=(o.textBaseline="top",o.font="600 32px Arial",{});return e.forEach(function(e){i[e]=t(o,e,n,a)}),i}function t(e){var t=s.createElement("script");t.src=e,t.defer=!0,s.head.appendChild(t)}"undefined"!=typeof Promise&&(o="wpEmojiSettingsSupports",i=["flag","emoji"],n.supports={everything:!0,everythingExceptFlag:!0},e=new Promise(function(e){s.addEventListener("DOMContentLoaded",e,{once:!0})}),new Promise(function(t){var n=function(){try{var e=JSON.parse(sessionStorage.getItem(o));if("object"==typeof e&&"number"==typeof e.timestamp&&(new Date).valueOf()<e.timestamp+604800&&"object"==typeof e.supportTests)return e.supportTests}catch(e){}return null}();if(!n){if("undefined"!=typeof Worker&&"undefined"!=typeof OffscreenCanvas&&"undefined"!=typeof URL&&URL.createObjectURL&&"undefined"!=typeof Blob)try{var e="postMessage("+g.toString()+"("+[JSON.stringify(i),f.toString(),p.toString(),u.toString()].join(",")+"));",a=new Blob([e],{type:"text/javascript"}),r=new Worker(URL.createObjectURL(a),{name:"wpTestEmojiSupports"});return void(r.onmessage=function(e){c(n=e.data),r.terminate(),t(n)})}catch(e){}c(n=g(i,f,p,u))}t(n)}).then(function(e){for(var t in e)n.supports[t]=e[t],n.supports.everything=n.supports.everything&&n.supports[t],"flag"!==t&&(n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&n.supports[t]);n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&!n.supports.flag,n.DOMReady=!1,n.readyCallback=function(){n.DOMReady=!0}}).then(function(){return e}).then(function(){var e;n.supports.everything||(n.readyCallback(),(e=n.source||{}).concatemoji?t(e.concatemoji):e.wpemoji&&e.twemoji&&(t(e.twemoji),t(e.wpemoji)))}))}((window,document),window._wpemojiSettings);
47/* ]]> */
48</script>
48
49<style id='wp-emoji-styles-inline-css' type='text/css'>
50
51	img.wp-smiley, img.emoji {
52		display: inline !important;
53		border: none !important;
54		box-shadow: none !important;
55		height: 1em !important;
56		width: 1em !important;
57		margin: 0 0.07em !important;
58		vertical-align: -0.1em !important;
59		background: none !important;
60		padding: 0 !important;
61	}
62</style>
63<link rel='stylesheet' id='wp-block-library-css' href='https://matroidunion.org/wp-includes/css/dist/block-library/style.min.css?ver=6.8.10' type='text/css' media='all' />
64<style id='wp-block-library-theme-inline-css' type='text/css'>
65.wp-block-audio :where(figcaption){color:#555;font-size:13px;text-align:center}.is-dark-theme .wp-block-audio :where(figcaption){color:#ffffffa6}.wp-block-audio{margin:0 0 1em}.wp-block-code{border:1px solid #ccc;border-radius:4px;font-family:Menlo,Consolas,monaco,monospace;padding:.8em 1em}.wp-block-embed :where(figcaption){color:#555;font-size:13px;text-align:center}.is-dark-theme .wp-block-embed :where(figcaption){color:#ffffffa6}.wp-block-embed{margin:0 0 1em}.blocks-gallery-caption{color:#555;font-size:13px;text-align:center}.is-dark-theme .blocks-gallery-caption{color:#ffffffa6}:root :where(.wp-block-image figcaption){color:#555;font-size:13px;text-align:center}.is-dark-theme :root :where(.wp-block-image figcaption){color:#ffffffa6}.wp-block-image{margin:0 0 1em}.wp-block-pullquote{border-bottom:4px solid;border-top:4px solid;color:currentColor;margin-bottom:1.75em}.wp-block-pullquote cite,.wp-block-pullquote footer,.wp-block-pullquote__citation{color:currentColor;font-size:.8125em;font-style:normal;text-transform:uppercase}.wp-block-quote{border-left:.25em solid;margin:0 0 1.75em;padding-left:1em}.wp-block-quote cite,.wp-block-quote footer{color:currentColor;font-size:.8125em;font-style:normal;position:relative}.wp-block-quote:where(.has-text-align-right){border-left:none;border-right:.25em solid;padding-left:0;padding-right:1em}.wp-block-quote:where(.has-text-align-center){border:none;padding-left:0}.wp-block-quote.is-large,.wp-block-quote.is-style-large,.wp-block-quote:where(.is-style-plain){border:none}.wp-block-search .wp-block-search__label{font-weight:700}.wp-block-search__button{border:1px solid #ccc;padding:.375em .625em}:where(.wp-block-group.has-background){padding:1.25em 2.375em}.wp-block-separator.has-css-opacity{opacity:.4}.wp-block-separator{border:none;border-bottom:2px solid;margin-left:auto;margin-right:auto}.wp-block-separator.has-alpha-channel-opacity{opacity:1}.wp-block-separator:not(.is-style-wide):not(.is-style-dots){width:100px}.wp-block-separator.has-background:not(.is-style-dots){border-bottom:none;height:1px}.wp-block-separator.has-background:not(.is-style-wide):not(.is-style-dots){height:2px}.wp-block-table{margin:0 0 1em}.wp-block-table td,.wp-block-table th{word-break:normal}.wp-block-table :where(figcaption){color:#555;font-size:13px;text-align:center}.is-dark-theme .wp-block-table :where(figcaption){color:#ffffffa6}.wp-block-video :where(figcaption){color:#555;font-size:13px;text-align:center}.is-dark-theme .wp-block-video :where(figcaption){color:#ffffffa6}.wp-block-video{margin:0 0 1em}:root :where(.wp-block-template-part.has-background){margin-bottom:0;margin-top:0;padding:1.25em 2.375em}
66</style>
67<style id='classic-theme-styles-inline-css' type='text/css'>
68/*! This file is auto-generated */
69.wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none}
70</style>
71<style id='global-styles-inline-css' type='text/css'>
72:root{--wp--preset--aspect-ratio--square: 1;--wp--preset--aspect-ratio--4-3: 4/3;--wp--preset--aspect-ratio--3-4: 3/4;--wp--preset--aspect-ratio--3-2: 3/2;--wp--preset--aspect-ratio--2-3: 2/3;--wp--preset--aspect-ratio--16-9: 16/9;--wp--preset--aspect-ratio--9-16: 9/16;--wp--preset--color--black: #000;--wp--preset--color--cyan-bluish-gray: #abb8c3;--wp--preset--color--white: #fff;--wp--preset--color--pale-pink: #f78da7;--wp--preset--color--vivid-red: #cf2e2e;--wp--preset--color--luminous-vivid-orange: #ff6900;--wp--preset--color--luminous-vivid-amber: #fcb900;--wp--preset--color--light-green-cyan: #7bdcb5;--wp--preset--color--vivid-green-cyan: #00d084;--wp--preset--color--pale-cyan-blue: #8ed1fc;--wp--preset--color--vivid-cyan-blue: #0693e3;--wp--preset--color--vivid-purple: #9b51e0;--wp--preset--color--blue: #1982d1;--wp--preset--color--dark-gray: #373737;--wp--preset--color--medium-gray: #666;--wp--preset--color--light-gray: #e2e2e2;--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple: linear-gradient(135deg,rgba(6,147,227,1) 0%,rgb(155,81,224) 100%);--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan: linear-gradient(135deg,rgb(122,220,180) 0%,rgb(0,208,130) 100%);--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange: linear-gradient(135deg,rgba(252,185,
720,1) 0%,rgba(255,105,0,1) 100%);--wp--preset--gradient--luminous-vivid-orange-to-vivid-red: linear-gradient(135deg,rgba(255,105,0,1) 0%,rgb(207,46,46) 100%);--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray: linear-gradient(135deg,rgb(238,238,238) 0%,rgb(169,184,195) 100%);--wp--preset--gradient--cool-to-warm-spectrum: linear-gradient(135deg,rgb(74,234,220) 0%,rgb(151,120,209) 20%,rgb(207,42,186) 40%,rgb(238,44,130) 60%,rgb(251,105,98) 80%,rgb(254,248,76) 100%);--wp--preset--gradient--blush-light-purple: linear-gradient(135deg,rgb(255,206,236) 0%,rgb(152,150,240) 100%);--wp--preset--gradient--blush-bordeaux: linear-gradient(135deg,rgb(254,205,165) 0%,rgb(254,45,45) 50%,rgb(107,0,62) 100%);--wp--preset--gradient--luminous-dusk: linear-gradient(135deg,rgb(255,203,112) 0%,rgb(199,81,192) 50%,rgb(65,88,208) 100%);--wp--preset--gradient--pale-ocean: linear-gradient(135deg,rgb(255,245,203) 0%,rgb(182,227,212) 50%,rgb(51,167,181) 100%);--wp--preset--gradient--electric-grass: linear-gradient(135deg,rgb(202,248,128) 0%,rgb(113,206,126) 100%);--wp--preset--gradient--midnight: linear-gradient(135deg,rgb(2,3,129) 0%,rgb(40,116,252) 100%);--wp--preset--font-size--small: 13px;--wp--preset--font-size--medium: 20px;--wp--preset--font-size--large: 36px;--wp--preset--font-size--x-large: 42px;--wp--preset--spacing--20: 0.44rem;--wp--preset--spacing--30: 0.67rem;--wp--preset--spacing--40: 1rem;--wp--preset--spacing--50: 1.5rem;--wp--preset--spacing--60: 2.25rem;--wp--preset--spacing--70: 3.38rem;--wp--preset--spacing--80: 5.06rem;--wp--preset--shadow--natural: 6px 6px 9px rgba(0, 0, 0, 0.2);--wp--preset--shadow--deep: 12px 12px 50px rgba(0, 0, 0, 0.4);--wp--preset--shadow--sharp: 6px 6px 0px rgba(0, 0, 0, 0.2);--wp--preset--shadow--outlined: 6px 6px 0px -3px rgba(255, 255, 255, 1), 6px 6px rgba(0, 0, 0, 1);--wp--preset--shadow--crisp: 6px 6px 0px rgba(0, 0, 0, 1);}:where(.is-layout-flex){gap: 0.5em;}:where(.is-layout-grid){gap: 0.5em;}body .is-layout-flex{display: flex;}.is-layout-flex{flex-wrap: wrap;align-items: center;}.is-layout-flex > :is(*, div){margin: 0;}body .is-layout-grid{display: grid;}.is-layout-grid > :is(*, div){margin: 0;}:where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;}:where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;}.has-black-color{color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-color{color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-color{color: var(--wp--preset--color--white) !important;}.has-pale-pink-color{color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-color{color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-color{color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-color{color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-color{color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-color{color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-color{color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-color{color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-color{color: var(--wp--preset--color--vivid-purple) !important;}.has-black-background-color{background-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-background-color{background-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-background-color{background-color: var(--wp--preset--color--white) !important;}.has-pale-pink-background-color{background-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-background-color{background-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-background-color{background-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-background-color{background-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-background-color{background-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-background-color{background-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-background-color{background-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-background-color{background-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-background-color{background-color: var(--wp--preset--color--vivid-purple) !important;}.has-black-border-color{border-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-border-color{border-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-border-color{border-color: var(--wp--preset--color--white) !important;}.has-pale-pink-border-color{border-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-border-color{border-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-border-color{border-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-border-color{border-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-border-color{border-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-border-color{border-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-border-color{border-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-border-color{border-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-border-color{border-color: var(--wp--preset--color--vivid-purple) !important;}.has-vivid-cyan-blue-to-vivid-purple-gradient-background{background: var(--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple) !important;}.has-light-green-cyan-to-vivid-green-cyan-gradient-background{background: var(--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan) !important;}.has-luminous-vivid-amber-to-luminous-vivid-orange-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange) !important;}.has-luminous-vivid-orange-to-vivid-red-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-orange-to-vivid-red) !important;}
72.has-very-light-gray-to-cyan-bluish-gray-gradient-background{background: var(--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray) !important;}.has-cool-to-warm-spectrum-gradient-background{background: var(--wp--preset--gradient--cool-to-warm-spectrum) !important;}.has-blush-light-purple-gradient-background{background: var(--wp--preset--gradient--blush-light-purple) !important;}.has-blush-bordeaux-gradient-background{background: var(--wp--preset--gradient--blush-bordeaux) !important;}.has-luminous-dusk-gradient-background{background: var(--wp--preset--gradient--luminous-dusk) !important;}.has-pale-ocean-gradient-background{background: var(--wp--preset--gradient--pale-ocean) !important;}.has-electric-grass-gradient-background{background: var(--wp--preset--gradient--electric-grass) !important;}.has-midnight-gradient-background{background: var(--wp--preset--gradient--midnight) !important;}.has-small-font-size{font-size: var(--wp--preset--font-size--small) !important;}.has-medium-font-size{font-size: var(--wp--preset--font-size--medium) !important;}.has-large-font-size{font-size: var(--wp--preset--font-size--large) !important;}.has-x-large-font-size{font-size: var(--wp--preset--font-size--x-large) !important;}
73:where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;}
74:where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;}
75:root :where(.wp-block-pullquote){font-size: 1.5em;line-height: 1.6;}
76</style>
77<link rel='stylesheet' id='twentyeleven-block-style-css' href='https://matroidunion.org/wp-content/themes/twentyeleven/blocks.css?ver=20240703' type='text/css' media='all' />
78<link rel="https://api.w.org/" href="https://matroidunion.org/index.php?rest_route=/" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="https://matroidunion.org/xmlrpc.php?rsd" />
79<meta name="generator" content="WordPress 6.8.10" />
80<style type="text/css">.recentcomments a{display:inline !important;padding:0 !important;margin:0 !important;}</style>
81<script src="https://sagecell.sagemath.org/static/jquery.min.js"></script>
vendor: 1 bytes, line 81
81
82<script src="https://sagecell.sagemath.org/static/embedded_sagecell.js"></script>
vendor: 1 bytes, line 82
82
83<script>jQuery(function () {
84    // Make any element of class 'sage' a Sage cell.
85    sagecell.makeSagecell({inputLocation:  '.sage'});
86    // Make any element of class 'sage1' a Sage cell, linked to the others in class 'sage1'.
87    sagecell.makeSagecell({inputLocation: '.sage1',
88			   linked:        true});
89    // Make any element of class 'sage2' a Sage cell, linked to the others in class 'sage2'.
90    sagecell.makeSagecell({inputLocation: '.sage2',
91			   linked:        true});
92    // Make any element of class 'sage3' a Sage cell, linked to the others in class 'sage3'.
93    sagecell.makeSagecell({inputLocation: '.sage3',
94			   linked:        true});
95    // Make any element of class 'sage4' a Sage cell, linked to the others in class 'sage4'.
96    sagecell.makeSagecell({inputLocation: '.sage4',
97			   linked:        true});
98    // Make any element of class 'sage5' a Sage cell, linked to the others in class 'sage5'.
99    sagecell.makeSagecell({inputLocation: '.sage5',
100			   linked:        true});
101    });
102</script>
102
103</head>
104
105<body class="home blog wp-embed-responsive wp-theme-twentyeleven wp-child-theme-twentyeleven-child two-column right-sidebar">
106<div id="page" class="hfeed">
107	<header id="branding" role="banner">
108			<hgroup>
109				<h1 id="site-title"><span><a href="https://matroidunion.org/" rel="home">The Matroid Union</a></span></h1>
110				<h2 id="site-description">A blog for and by the matroid community</h2>
111			</hgroup>
112
113						<a href="https://matroidunion.org/">
114									<img src="https://matroidunion.org/wp-content/uploads/2013/08/header-0245.jpg" width="868" height="250" alt="" />
115							</a>
116			
117								<form method="get" id="searchform" action="https://matroidunion.org/">
118		<label for="s" class="assistive-text">Search</label>
119		<input type="text" class="field" name="s" id="s" placeholder="Search" />
120		<input type="submit" class="submit" name="submit" id="searchsubmit" value="Search" />
121	</form>
122			
123			<nav id="access" role="navigation">
124				<h3 class="assistive-text">Main menu</h3>
125								<div class="skip-link"><a class="assistive-text" href="#content">Skip to primary content</a></div>
126									<div class="skip-link"><a class="assistive-text" href="#secondary">Skip to secondary content</a></div>
127												<div class="menu-pages-container"><ul id="menu-pages" class="menu"><li id="menu-item-35" class="menu-item menu-item-type-custom menu-item-object-custom current-menu-item current_page_item menu-item-home menu-item-35"><a href="http://matroidunion.org/" aria-current="page">Home</a></li>
128<li id="menu-item-34" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-34"><a href="https://matroidunion.org/?page_id=21">About</a></li>
129<li id="menu-item-2481" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-2481"><a href="https://matroidunion.org/?page_id=2477">Talks</a></li>
130<li id="menu-item-1392" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-1392"><a href="https://matroidunion.org/?page_id=1388">Meetings</a></li>
131<li id="menu-item-2438" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-2438"><a href="https://matroidunion.org/?page_id=2435">Q&#038;A</a></li>
132</ul></div>			</nav><!-- #access -->
133	</header><!-- #branding -->
134
135
136	<div id="main">
137
138		<div id="primary">
139			<div id="content" role="main">
140
141			
142							<nav id="nav-above">
143				<h3 class="assistive-text">Post navigation</h3>
144									<div class="nav-previous"><a href="https://matroidunion.org/?paged=2" ><span class="meta-nav">&larr;</span> Older posts</a></div>
145				
146							</nav><!-- #nav-above -->
147			
148				
149					
150	<article id="post-6280" class="post-6280 post type-post status-publish format-standard hentry category-matroids">
151		<header class="entry-header">
152						<h1 class="entry-title"><a href="https://matroidunion.org/?p=6280" rel="bookmark">Representable Matroid Lifts</a></h1>
153			
154						<div class="entry-meta">
155				<span class="sep">Posted on </span><a href="https://matroidunion.org/?p=6280" title="3:16 pm" rel="bookmark"><time class="entry-date" datetime="2026-09-07T15:16:55-04:00">September 7, 2026</time></a><span class="by-author"> <span class="sep"> by </span> <span class="author vcard"><a class="url fn n" href="https://matroidunion.org/?author=22" title="View all posts by Daniel Bernstein" rel="author">Daniel Bernstein</a></span></span>			</div><!-- .entry-meta -->
156			
157						<div class="comments-link">
158				<a href="https://matroidunion.org/?p=6280#respond"><span class="leave-reply">Reply</span></a>			</div>
159					</header><!-- .entry-header -->
160
161				<div class="entry-content">
162			
163<p>In this blog post, I&#8217;m going to discuss a part of a paper I wrote with Zach Walsh a few years back called &#8220;Matroid lifts and representability.&#8221; We&#8217;ll start by motivating the idea of a<em> </em>matroid <em>lift.</em></p>
164<p>Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ be matrices such that $A$ is a row-submatrix of $B$. Let $E$ denote the column set of $B$, which also naturally indexes the column set of $A$. Let $M_A$ and $M_B$ denote the matroids on ground set $E$ defined by linear independence in $A$ and $B$, respectively. Since $A$ is a row-submatrix of $B$, there is a special relationship between $M_A$ and $M_B$. In particular, every flat of $M_A$ is a flat of $M_B$. This motivates the following definition: given two matroids $M_1$ and $M_2$ on a common ground set $E$, one says that $M_2$ is a <em>lift</em> of $M_1$ if every flat of $M_1$ is a flat of $M_2$.</p>
165<h1>An Example</h1>
166<p>Recall that $U_{r,n}
166$ denotes the uniform matroid of rank $r$ on $n$ elements. One can check that $U_{2,3}$ is a lift of $U_{1,3}$. One can check this by noting that the flats of $U_{1,3}$ are the empty set, the full ground set, and each singleton set and that each of these are also flats of $U_{2,3}$. Alternatively, one can consider the following $\mathbb{Q}$-matrix</p>
167<p style="text-align: center">$\begin{pmatrix} 1 &amp; 1 &amp; 1 \\ 0 &amp; 1 &amp; 2 \end{pmatrix}$</p>
168<p>and note that the matroid of the top row is $U_{1,3}$ and the matroid of the whole matrix is $U_{2,3}$. One interesting thing to note is that even though $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{F}_2$-representable, there is no $2\times 3$ $\mathbb{F}_2$ matrix $B$ that represents $U_{2,3}$, whose top row represents $U_{1,3}$.</p>
169<h1>Notational Remark</h1>
170<p>For any matroid $Q$, I will use the notation $r_Q$ and ${\rm cl}_Q$ to denote the rank function and closure operator in $Q$.</p>
171<h1>Elementary lifts</h1>
172<p>If $M_2$ is a lift of $M_1$, then the rank of $M_2$ is greater than or equal to that of $M_1$. When $M_2$ is a lift of $M_1$ whose rank is exactly one greater than that of $M_1$, one says that $M_2$ is an <em>elementary</em> lift of $M_1$. I will now describe a classical theorem of Brylawski, the dual version of which was previously stated by Crapo, that gives an elegant combinatorial characterization of all elementary lifts of a matroid $M$.</p>
173<p>Let $M$ be a matroid on ground set $E$. A <em>linear class of $M$</em> is a collection $\mathcal{L}$ of circuits of $M$ such that if $C_1,C_2 \in \mathcal{L}$ satisfy</p>
174<p style="text-align: center">$|C_1 \cup C_2| &#8211; r_M(C_1 \cup C_2) = 2$</p>
175<p>then if $C_3$ is a circuit of $M$ contained in $C_1 \cup C_2$, then $C_3 \in \mathcal{L}$. For each such linear class, one can define a function $r_\mathcal{L}: 2^{E} \rightarrow \mathbb{N}$ as follows</p>
176<p style="text-align: center">$r_\mathcal{L}(X) = \begin{cases}r_M(X) &amp; \textnormal{if each circuit of } M|X \textnormal{ is in } \mathcal{L} \\ r_M(X) + 1 &amp; {\rm otherwise}.\end{cases}$</p>
177<p>For each linear class $\mathcal{L}$ of $M$, $r_\mathcal{L}$ is the rank function of a matroid $L$ such that $L$ is an elementary lift of $M$. What is even more interesting is that for <em>every</em> elementary lift $L$ of $M$, there exists a linear class $\mathcal{L}$ of circuits of $M$ such that the rank function of $L$ is $r_{\mathcal{L}}$.</p>
178<h1>Higher-rank lifts</h1>
179<p>I became aware of Zach&#8217;s existence when his paper &#8220;A new matroid lift construction and an application to group-labeled graphs&#8221; hit the arXiv. It gave a method for constructing non-elementary lifts of matroids in a way that generalized Brylawski&#8217;s construction. At the time, I was on the prowl for matroid theory tools that could be useful in rigidity theory, and matroid lifts had recently played a key role in a groundbreaking paper of Clinch, Jackson, and Tanigawa called &#8220;Abstract 3-Rigidity and Bivariate C12-Splines II: Combinatorial Characterization.&#8221; So I was very intrigued by Zach&#8217;s construction, which is given in the following theorem. </p>
180<p><strong>Theorem (Walsh): </strong>Let $M$ be a matroid on ground set $E$ with circuit set $\mathcal{C}$. Let $N$ be a matroid on ground set $\mathcal{C}$ such that if $|C_1 \cup C_2| &#8211; r_M(C_1 \cup C_2) = 2$, then each $C \in \mathcal{C}$ such that $C \subset C_1 \cup C_2$ satisfies $C \in {\rm cl}_N(\{C_1 \cup C_2\})$. Then the function $\rho_N: 2^E \rightarrow \mathbb{N}$ defined as follows is the rank function of a lift of $M$ of rank $r_M(E) + r_N(\mathcal{C})$</p>
181<p style="text-align: center">$\rho_N(X) = r_M(X) + r_N(\{C : C \textnormal{ is a circuit of } M|X\}).$</p>
182<p>Zach&#8217;s construction generalizes Brylawski&#8217;s construction in the sense that when $r_N(\mathcal{C}) = 1$, the rank-zero flat of $N$ is a linear class $\mathcal{L}$ of circuits of $M$, and that $r_\mathcal{L} = \rho_N$. Zach had hoped that this construction would completely generalize Brylawski&#8217;s result in that every lift of a matroid $M$ would have rank function of the form $\rho_N$ for some matroid $N$ on the circuit set of $M$. As we will see, this is not the case. However, it <em>does</em> hold for matroid lifts that arise from taking the matroid of a matrix, and a row-submatrix. This gives us a way to test that a given lift is &#8220;representable&#8221; as a lift, and can even be turned into a test for matroid representability.</p>
183<p><strong>Theorem (B-Walsh): </strong>Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ such that $A$ is a row-submatrix of $B$. Let $M_A,M_B$ respectively denote the column matroids of $A$ and $B$ and let $\mathcal{C}$ denote the set of circuits of $A$. Then there exists a matroid $N$ on ground set $\mathcal{C}$ such that $\rho_N$ is the rank function of $M_B$.</p>
184<p>Here is a sketch of the proof. Since $A$ is a row-submatrix of $B$ we may without loss of generality assume that $B$ has the following form for some matrix $C$</p>
185<p style="text-align: center">$B = \binom{A}{C}$.</p>
186<p>For each circuit $C$ of $M_A$ let $x_C$ be a fixed element of $\mathbb{F}^n$ such that $Ax = 0$. Then $Bx_C$ can be written in the following form for some $x_C&#8217; \in \mathbb{F}^{r_2-r_1}$</p>
187<p style="text-align: center">$Bx_C = \binom{0}{x_C&#8217;}$.</p>
188<p>This enables us to define a matroid $N$ on the circuit set $\mathcal{C}
188$ of $A$ by asserting that $\{C_1,\dots,C_k\}$ is independent in $N$ if and only if the set of vectors $\{x_{C_1}&#8217;,\dots,x_{C_k}&#8217;\}$ is linearly independent in $\mathbb{F}^{r_2-r_1}$. Then, the rank function of $M_B$ is $\rho_N$.</p>
189<h1>Non-representable higher rank lifts</h1>
190<p>The proof of the above theorem heavily depends on access to a linear representation of the higher rank matroid, that has a row-submatrix representing the lower rank matroid. This dependence on a representation cannot be avoided, at least not in full generality. In particular, we can obtain a counterexample from the Vámos matroid.</p>
191<p>Given any matroid $M$ on ground set $E$ and an independent subset $I \subset E$, $M\setminus I$ is always a lift of $M / I$ and the difference in ranks is $|I|$ and all lifts can be obtained in this way. Let $V_8$ be the matroid with ground set $\{1,2,\dots,8\}$ of rank $4$, such that every subset of size four or smaller is independent, with the exceptions of the following four-element subsets</p>
192<p style="text-align: center">$1234,3456,5678,1278,3478.$</p>
193<p>This is known as the <em>Vámos</em> matroid, which is known to not be representable over any field. Then $V_8 \setminus \{7,8\}$ is a lift of $V_8 / \{7,8\}$, and as Zach and I show in our paper, there is no matroid $N$ of rank $2$ on the circuit set of $V_8 / \{7,8\}$ such that the rank function of $V_8 \setminus \{7,8\}$ is $\rho_N$. We generalize this construction to construct a two-parameter infinite antichain (in the minor partial order) of sparse paving matroids that are not representable over any field, that satisfy Ingleton&#8217;s inequality.</p>
194<h1>Concluding remarks</h1>
195<p>As with many papers I&#8217;ve written, the bulk of the time I spent &#8220;writing&#8221; this paper was spent chasing something I wound up being unable to prove. In particular, I was hoping to generalize the theorem about representable lifts of matroids being obtainable via Zach&#8217;s construction to the family of algebraic matroids. Alas, not only was I unable to prove that, I&#8217;m not so sure if it&#8217;s true anymore. But I really don&#8217;t have any reason to make a conjecture either way.</p>
196
197
198
199
200
201
202					</div><!-- .entry-content -->
203		
204		<footer class="entry-meta">
205			
206										<span class="cat-links">
207					<span class="entry-utility-prep entry-utility-prep-cat-links">Posted in</span> <a href="https://matroidunion.org/?cat=1" rel="category">Matroids</a>			</span>
208							
209										
210										<span class="sep"> | </span>
211						<span class="comments-link"><a href="https://matroidunion.org/?p=6280#respond"><span class="leave-reply">Leave a reply</span></a></span>
212			
213					</footer><!-- .entry-meta -->
214	</article><!-- #post-6280 -->
215
216				
217					
218	<article id="post-6262" class="post-6262 post type-post status-publish format-standard hentry category-matroids tag-direct-sum tag-matroid-union tag-q-analogue">
219		<header class="entry-header">
220						<h1 class="entry-title"><a href="https://matroidunion.org/?p=6262" rel="bookmark">Direct sum of q-matroids</a></h1>
221			
222						<div class="entry-meta">
223				<span class="sep">Posted on </span><a href="https://matroidunion.org/?p=6262" title="7:32 am" rel="bookmark"><time class="entry-date" datetime="2026-08-03T07:32:26-04:00">August 3, 2026</time></a><span class="by-author"> <span class="sep"> by </span> <span class="author vcard"><a class="url fn n" href="https://matroidunion.org/?author=17" title="View all posts by Relinde Jurrius" rel="author">Relinde Jurrius</a></span></span>			</div><!-- .entry-meta -->
224			
225						<div class="comments-link">
226				<a href="https://matroidunion.org/?p=6262#comments">2</a>			</div>
227					</header><!-- .entry-header -->
228
229				<div class="entry-content">
230			
231<p>One of the most straightforward operations you can do when you want to make a new matroid out of old ones, is taking the direct sum. The direct sum of the matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$ is the matroid $M$ on ground set $E=E_1\sqcup E_2$ with for all $A\subseteq E$,<br>\[ r(A)=r_1(A\cap E_1)+r_2(A\cap E_2). \]Alternatively, its independent sets are the unions of an independent set in $M_1$ and an independent set in $M_2$. The third equivalent way to define the direct sum is by saying that $M=M_1\oplus M_2$ is precisely the matroid such that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$.</p>
232
233
234
235<p>In this post, we will discuss the <em>q</em>-analogue of this concept. The <em>q</em>-analogues of matroids, called <em>q</em>-matroids, have been introduced <a href="https://matroidunion.org/?p=3518">here</a>. Instead of considering a matroid on a finite ground set, where every subset has a rank that satisfies certain axioms, we take a <em>q</em>-matroid on a finite dimensional vector space where every subspace has a rank, again satisfying certain axioms. A good intuition is to think about matroids as a bicolouring of the Boolean lattice, and <em>q</em>-matroids as a bicolouring of the subspace lattice.</p>
236
237
238
239<p>If we take the direct sum of two <em>q</em>-matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$, it makes sense for $M=M_1\oplus M_2$ to have as a ground space the direct sum of vector spaces $E_1\oplus E_2$. It is also reasonable to ask that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. But then it gets difficult. Where for sets, we can write any subset $A\subseteq E_1\sqcup E_2$ as $(A\cap E_1)\sqcup(A\cap E_2)$, such a thing is not true for vector spaces. Suppose for example $E_1=\langle100\rangle$ and $E_2=\langle010,001\rangle$ (over my favourite finite field $\mathbb{F}_2$) such that $E_1\oplus E_2$ is a 3-dimensional space. Then the space $A=\langle111\rangle$ does not intersect $E_1$ nor $E_2$. What is its rank going to be?</p>
240
241
242
243<p>One could hope that maybe the rank axioms of <em>q</em>-matroids take care of this. Look for example at the direct sum of $U_{1,1}$ and $U_{1,2}$ over $\mathbb{F}_2$.</p>
244
245
246
247<figure class="wp-block-image size-large"><a href="https://matroidunion.org/wp-content/uploads/2026/08/U11U12half.png"><img fetchpriority="high" decoding="async" width="1024" height="514" src="https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-1024x514.png" alt="" class="wp-image-6269" srcset="https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-1024x514.png 1024w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-300x151.png 300w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-768x386.png 768w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-1536x772.png 1536w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-2048x1029.png 2048w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12half-500x251.png 500w" sizes="(max-width: 1024px) 100vw, 1024px" /></a></figure>
248
249
250
251<p>We see that the interval between $0$ and $\langle100\rangle$ and the interval between $\langle010,001\rangle$ and $E$ are coloured as $U_{1,1}$, showing $M|_{E_1}=M/E_2=M_1$. On the other hand, the interval between $0$ and $\langle010,001\rangle$ and the interval between $\langle100\rangle$ and $E$ are coloured as $U_{1,2}$, showing that $M|_{E_2}=M/E_1=M_2$. There is now only one way to colour the rest of the lattice:</p>
252
253
254
255<figure class="wp-block-image size-large"><a href="https://matroidunion.org/wp-content/uploads/2026/08/U11U12full.png"><img decoding="async" width="1024" height="514" src="https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-1024x514.png" alt="" class="wp-image-6270" srcset="https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-1024x514.png 1024w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-300x151.png 300w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-768x386.png 768w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-1536x772.png 1536w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-2048x1029.png 2048w, https://matroidunion.org/wp-content/uploads/2026/08/U11U12full-500x251.png 500w" sizes="(max-width: 1024px) 100vw, 1024px" /></a></figure>
256
257
258
259<p>Unfortunately, this construction becomes not unique already in dimension 4. If we try to make the direct sum $U_{1,2}\oplus U_{1,2}$, semimodularity of the rank function gives that all 1-dimensional spaces have rank 1 and all 3-dimensional spaces have rank 2. Any 2-dimensional space intersecting $E_1$ or $E_2$ is a basis. But there are 2-dimensional spaces that intersect neither $E_1$ nor $E_2$ (over $\mathbb{F}_2$, there are three of them) and those can be either a basis or a circuit. Any choice will produce another <em>q</em>-matroid.</p>
260
261
262
263<p>The solution to this problem is to write the direct sum in a very convoluted way that is not helpful for matroids over sets, but that does have a nice <em>q</em>-analogue. This is the following. As mentioned, let $E=E_1\oplus E_2$. Make a matroid $M_1&#8217;$ by adding loops to $M_1$ until its groud space is $E$: $M_1&#8217;$ is the <em>q</em>-matroid on $E$ such that $M_1&#8217;|_{E_1}=M_1$ and $M_1&#8217;|_{E_2}$ consists of only loops. Similarly, let $M_2&#8217;$ be the <em>q</em>-matroid on $E$ such that $M_2&#8217;|_{E_2}=M_2$ and $M_2&#8217;|_{E_1}$ consists of only loops. Now the direct sum $M_1\oplus M_2$ is defined as the matroid union $M_1&#8217;\vee M_2&#8217;$.</p>
264
265
266
267<p>It turns out that adding loops is, inductively, possible in the <em>q</em>-analogue. Also matroid union (as an honour to the name of this blog, surely!) has a well-defined <em>q</em>-analogue: this operation is defined for matroids on the same ground set, and can thus be generalised to <em>q</em>-matroids with the same ground space without the troubles that come with the direct sum of vector spaces. The rank function of the direct sum of two <em>q</em>-matroids is \[ r_{M_1\oplus M_2}(A)=\min_{X\subseteq A}\{r_{M_1&#8242;}(X)+r_{M_2&#8242;}(X)+\dim A-\dim X\}. \]</p>
268
269
270
271<p>An equivalent way to phrase this definition of the direct sum of <em>q</em>-matroids, is by requiring the direct sum to to be the &#8220;most independent&#8221; <em>q</em>-matroid satisfying $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. This can be made precise in category theory language.</p>
272
273
274
275<p>It is unclear what the independent spaces of the direct sum of two <em>q</em>-matroids are. The vector space sum of an independent space in $M_1$ and an independent space in $M_2$ is independent in the direct sum. But there are many more independent spaces. Many other properties of the direct sum of matroids fail to have a nice <em>q</em>-analogue. What does work in the <em>q</em>-analogue, is that the cyclic flats of the direct sum are exactly the sums of the cyclic flats of $M_1$ and $M_2$.</p>
276
277
278
279<p>You might have guessed that if $M_1$ and $M_2$ are <em>q</em>-matroids represented by matrices $G_1$ and $G_2$ (I&#8217;m going to use this notion without a formal definition), then their direct sum is <em>not</em> necessarily represented by the matrix \[ \left[ \begin{array}{cc} G_1 &amp; 0 \\ 0 &amp; G_2 \end{array} \right]. \] Interestingly, the question about representability can be translated to the language of <em>linear sets</em> in finite geometry, making it possible to use several results in finite geometry for <em>q</em>-matroids.</p>
280
281
282
283<h3 class="wp-block-heading">References</h3>
284
285
286
287<p><p>[<a href="https://doi.org/10.5070/C66165691">AJNZ26</a>] Gianira Alfarano, Relinde Jurrius, Alessandro Neri and Ferdinando Zullo. <em>Representability of the direct sum of uniform q-matroids.</em> Combinatorial Theory, 6 (2026).</p><p>[<a href="https://doi.org/10.1007/s10801-023-01283-x">CJ24</a>] Michela Ceria and Relinde Jurrius. <em>The direct sum of q-matroids.</em>
287 Journal of Algebraic Combinatorics, 59, pp. 291-330 (2024).</p><p>[<a href="https://doi.org/10.1016/j.ejc.2023.103733">GLJ23</a>] Heide Gluesing-Luerssen and Benjamin Jany. <em>Coproducts in categories of q-matroids.</em> European Journal of Combinatorics 112, 103733 (2023).</p><p>[<a href="https://doi.org/10.1137/23M156358X">GLJ24</a>] Heide Gluesing-Luerssen and Benjamin Jany. <em>Decomposition of q-matroids using cyclic flats.</em> SIAM Journal on Discrete Mathematics 38, pp 2940&#8211;2970 (2024).</p><p>[<a href="https://doi.org/10.1007/s10801-025-01438-y">GLJ25</a>] Heide Gluesing-Luerssen and Benjamin Jany. <em>Representability of the direct sum of q-matroids.</em> Journal of Algebraic Combinatorics 61, 51 (2025).</p></p>
288					</div><!-- .entry-content -->
289		
290		<footer class="entry-meta">
291			
292										<span class="cat-links">
293					<span class="entry-utility-prep entry-utility-prep-cat-links">Posted in</span> <a href="https://matroidunion.org/?cat=1" rel="category">Matroids</a>			</span>
294							
295										<span class="sep"> | </span>
296								<span class="tag-links">
297					<span class="entry-utility-prep entry-utility-prep-tag-links">Tagged</span> <a href="https://matroidunion.org/?tag=direct-sum" rel="tag">direct sum</a>, <a href="https://matroidunion.org/?tag=matroid-union" rel="tag">matroid union</a>, <a href="https://matroidunion.org/?tag=q-analogue" rel="tag">q-analogue</a>			</span>
298							
299										<span class="sep"> | </span>
300						<span class="comments-link"><a href="https://matroidunion.org/?p=6262#comments"><b>2</b> Replies</a></span>
301			
302					</footer><!-- .entry-meta -->
303	</article><!-- #post-6262 -->
304
305				
306					
307	<article id="post-6255" class="post-6255 post type-post status-publish format-standard hentry category-matroids tag-cycle-double-cover tag-embedded-graph">
308		<header class="entry-header">
309						<h1 class="entry-title"><a href="https://matroidunion.org/?p=6255" rel="bookmark">The cycle double cover theorem</a></h1>
310			
311						<div class="entry-meta">
312				<span class="sep">Posted on </span><a href="https://matroidunion.org/?p=6255" title="3:06 pm" rel="bookmark"><time class="entry-date" datetime="2026-07-21T15:06:08-04:00">July 21, 2026</time></a><span class="by-author"> <span class="sep"> by </span> <span class="author vcard"><a class="url fn n" href="https://matroidunion.org/?author=7" title="View all posts by Guest Contributor" rel="author">Guest Contributor</a></span></span>			</div><!-- .entry-meta -->
313			
314						<div class="comments-link">
315				<a href="https://matroidunion.org/?p=6255#respond"><span class="leave-reply">Reply</span></a>			</div>
316					</header><!-- .entry-header -->
317
318				<div class="entry-content">
319			
320<p><em>This is a guest post by <a href="https://j-carmesin.github.io">Johannes Carmesin</a>.</em></p>
321
322
323
324<p>You have probably all heard that OpenAI announced a <a href="https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf">fully automated proof of the cycle double cover conjecture</a>, which was conjectured independently by Tutte, Itai and Rodeh, Szekeres, and Seymour about fifty years ago.</p>
325
326
327
328<p>First, to answer the most immediate question: <em>yes, the proof is correct</em>.</p>
329
330
331
332<p>Here, I would like to do two things:</p>
333<ol>
334<li>explain the statement of the theorem; and</li>
335<li>give an overview of how the proof has been verified.</li>
336</ol>
337
338
339
340<h2 class="wp-block-heading">Statement of the theorem</h2>
341
342
343
344<p>The theorem has a particularly appealing topological formulation: every bridgeless multigraph can be embedded in a <em>pseudosurface</em> in such a way that every face is a disc. In particular, every edge occurs exactly twice among the boundary walks of the faces. Here, a pseudosurface is a topological space obtained from a closed surface (possibly disconnected) by identifying finitely many points.</p>
345
346
347
348<p>The use of pseudosurfaces is very natural in this context: embeddings of different blocks can be glued together at their common cut-vertices. An example that pseudosurfaces are genuinely necessary is given below.</p>
349
350
351
352
353
354<figure class="wp-block-image aligncenter size-full"><a href="https://matroidunion.org/wp-content/uploads/2026/07/bowtie.png"><img decoding="async" width="800" height="415" src="https://matroidunion.org/wp-content/uploads/2026/07/bowtie.png" alt="The bowtie graph, consisting of two triangles glued together at a single vertex.
355It has a unique cycle double cover. It contains each triangle twice.
356The corresponding embedding has four disc faces and lies naturally in two spheres identified at the common vertex. This shows that pseudosurfaces are genuinely necessary in the topological formulation of the problem." class="wp-image-6257" srcset="https://matroidunion.org/wp-content/uploads/2026/07/bowtie.png 800w, https://matroidunion.org/wp-content/uploads/2026/07/bowtie-300x156.png 300w, https://matroidunion.org/wp-content/uploads/2026/07/bowtie-768x398.png 768w, https://matroidunion.org/wp-content/uploads/2026/07/bowtie-500x259.png 500w" sizes="(max-width: 800px) 100v
356w, 800px" /></a><figcaption class="wp-element-caption">The bowtie graph, consisting of two triangles glued together at a single vertex.<br>It has a unique cycle double cover. It contains each triangle twice.<br>The corresponding embedding has four disc faces and lies naturally in two spheres identified at the common vertex. This shows that pseudosurfaces are genuinely necessary in the topological formulation of the problem.</figcaption></figure>
357
358
359
360<p>The algebraic counterpart of this topological statement is the following equivalent formulation: every bridgeless multigraph $G$ has a cycle double cover. That is, there exists a family $\{C_i\mid i\in I\}$ of cycles of $G$ such that every edge belongs to exactly two of the cycles $C_i$.</p>
361
362
363
364<p>To see the connection, suppose first that such a cycle double cover is given. For every cycle $C_i$, take a disc and glue its boundary to the corresponding cycle in the graph. Since every edge occurs in exactly two cycles of the family, every edge is incident with two such discs. The resulting space is a pseudosurface in which the original graph is embedded and the added discs are precisely its faces.</p>
365
366
367
368<p>For a simple example showing that pseudosurfaces are genuinely necessary in the above topological formulation of the cycle double cover conjecture, see the figure below.</p>
369
370
371
372<p>Conversely, given such an embedding in a pseudosurface, the family $\{C_i\mid i\in I\}$ consists of the boundary walks $C_i$ of the faces of the embedding, which are cycles. Taken over all faces, these cycles form a cycle double cover, because every edge occurs exactly twice among the boundary walks of the faces.</p>
373
374
375
376<p>The assumption that the graph is bridgeless is necessary. Indeed, a bridge is a cocircuit-singleton and thus cannot belong to any cycle and therefore cannot be covered even once by a cycle, let alone exactly twice.</p>
377
378
379
380<h2 class="wp-block-heading">About the proof</h2>
381
382
383
384<p>The proof by OpenAI establishes the second, algebraic formulation. In a nutshell, it begins with a nowhere-zero $\mathbb{F}_2^3$-flow $f$ on $G$; that is, an assignment of a nonzero vector in $\mathbb{F}_2^3$ to each edge such that, at every vertex, the values on the incident edges sum to zero. The existence of this flow follows from Seymour&#8217;s <a href="https://www.sciencedirect.com/science/article/pii/0095895681900587">nowhere-zero six flow theorem</a> (see also the recent <a href="https://doi.org/10.37236/14483">short proof by DeVos and Nurse</a>).</p>
385
386
387
388<p>Roughly speaking, this flow is not quite a cycle double cover. The paper studies how one locally needs to modify the flow at each vertex so that it becomes a cycle double cover, and then there is a compatibility condition that needs to hold between adjacent vertices.</p>
389
390
391
392<p>The compatibility conditions between the local modifications, and the equations for the local modifications give rise to a system of linear equations over $\mathbb{F}_2$, with one vector variable in $\mathbb{F}_2^3$ for each vertex and one scalar variable in $\mathbb{F}_2$ for each edge. OpenAI then uses duality to prove that this system always has a solution. The entire proof occupies only two pages.</p>
393
394
395
396<p>Sang-il Oum gave an excellent talk on the proof and provides a <a href="https://sangil.dimag.kr/2026/cdc/">much more detailed explanation</a>. Jim Geelen (<a href="https://arxiv.org/abs/2607.15399">link</a>) and Sang-il Oum (<a href="https://arxiv.org/abs/2607.16356">link</a>) independently wrote short notes giving the complete proof in a different presentation, which I both find particularly pleasant to read and the latter additionally contains open questions.</p>
397
398
399
400<p>Finally, the proof has already been formalised independently several times in Lean 4. Krystal Guo produced one formalisation of the core argument (personal communication), while <a href="https://j-carmesin.github.io/publications/Cycle_double_cover.pdf">Vaibhav Bajpai, Utku Okur, and I produced another</a>, and <a href="https://github.com/openai/cdc-lean">one by OpenAI</a> (see also <a href="https://leanprover.zulipchat.com/#narrow/channel/583339-AI-authored-projects/topic/OpenAI.27s.20Cycle.20Double.20Cover.20Conjecture.20Proof.20Claim/with/609608245">
400this discussion in the AI-authored projects channel</a> of the Lean Zulip community).</p>
401					</div><!-- .entry-content -->
402		
403		<footer class="entry-meta">
404			
405										<span class="cat-links">
406					<span class="entry-utility-prep entry-utility-prep-cat-links">Posted in</span> <a href="https://matroidunion.org/?cat=1" rel="category">Matroids</a>			</span>
407							
408										<span class="sep"> | </span>
409								<span class="tag-links">
410					<span class="entry-utility-prep entry-utility-prep-tag-links">Tagged</span> <a href="https://matroidunion.org/?tag=cycle-double-cover" rel="tag">cycle double cover</a>, <a href="https://matroidunion.org/?tag=embedded-graph" rel="tag">embedded graph</a>			</span>
411							
412										<span class="sep"> | </span>
413						<span class="comments-link"><a href="https://matroidunion.org/?p=6255#respond"><span class="leave-reply">Leave a reply</span></a></span>
414			
415					</footer><!-- .entry-meta -->
416	</article><!-- #post-6255 -->
417
418				
419					
420	<article id="post-6246" class="post-6246 post type-post status-publish format-standard hentry category-matroids tag-ambient-space tag-dowling-geometry tag-variety">
421		<header class="entry-header">
422						<h1 class="entry-title"><a href="https://matroidunion.org/?p=6246" rel="bookmark">Matroid varieties</a></h1>
423			
424						<div class="entry-meta">
425				<span class="sep">Posted on </span><a href="https://matroidunion.org/?p=6246" title="5:54 pm" rel="bookmark"><time class="entry-date" datetime="2026-07-06T17:54:27-04:00">July 6, 2026</time></a><span class="by-author"> <span class="sep"> by </span> <span class="author vcard"><a class="url fn n" href="https://matroidunion.org/?author=18" title="View all posts by Jorn van der Pol" rel="author">Jorn van der Pol</a></span></span>			</div><!-- .entry-meta -->
426			
427						<div class="comments-link">
428				<a href="https://matroidunion.org/?p=6246#comments">1</a>			</div>
429					</header><!-- .entry-header -->
430
431				<div class="entry-content">
432			
433<h2 class="wp-block-heading">Universal models for graphic and representable matroids</h2>
434
435
436
437<p>Graphs have the useful property that each of them is a restriction of a complete graph on the same set of vertices. This property makes it easy, for example, to generate a random graph: simply flip a coin for each edge in the complete graph, and include the edge if the coin turns up heads. In matroidal terms, the property is that every rank-$n$ simple graphic matroid is a restriction of $M(K_{n+1})$.</p>
438
439
440
441<p>There is another well known class of matroids for which a similar observation holds: those representable over a fixed finite field, in which case the projective geometry of a given rank serves as a &#8220;universal model&#8221;, in the sense that every simple rank-$n$ matroid that is representable over the finite field $\mathbb{F}_q$ can be obtained from $\text{PG}(n-1,\mathbb{F}_q)$ by restriction.</p>
442
443
444
445<p>On the other hand, the same is not true for the class of all matroids. Even for matroids of rank 2, there is no universal model $M$ such that each such matroid is a restriction of $M$.</p>
446
447
448
449<h2 class="wp-block-heading">Dowling geometries</h2>
450
451
452
453<p>The class of graphic matroids is only one member of a family of classes with the same property: the Dowling matroids. <a href="https://matroidunion.org/?p=161">These have been discussed before on the blog</a> in the context of biased graphs, but let&#8217;s briefly recall their definition.</p>
454
455
456
457<p>The rank-$n$ Dowling geometry $\text{DG}(n, \Gamma)$ is determined by a finite group $\Gamma$, similar to how projective geometries are determined by a field, and a Dowling matroid is simply any matroid that can be obtained by restricting $\text{DG}(n, \Gamma)$. Let&#8217;s assume that the operation in $\Gamma$ is multiplication. A $\Gamma$-gain graph is a graph $G$, together with an orientation of the edges of $G$ and a gain function $\varphi\colon E(G)\to\Gamma$. For a cycle $C$ of $G$, we pick a starting point an an orientation of $C$, which gives us an order of the edges of $C$, say $C = e_1e_2\ldots e_k$. Define $\varphi(C) = \varphi(e_1)^{s_1} \varphi(e_2)^{s_2} \ldots \varphi(e_k)^{s_k}$, where $s_i = 1$ if the orientation of $e_i$ agrees with the orientation of $C$, and $s_i = -1$ otherwise. The cycle $C$ is called &#8220;balanced&#8221; if $\varphi(C)$ is the identity in the group; it is a straightforward exercise to check that balance of $C$ does not depend on the orientation or starting point of $C$.</p>
458
459
460<div class="wp-block-image">
461<figure class="aligncenter size-full"><a href="https://matroidunion.org/wp-content/uploads/2026/07/matroid-union-theta.png"><img loading="lazy" decoding="async" width="303" height="92" src="https://matroidunion.org/wp-content/uploads/2026/07/matroid-union-theta.png" alt="" class="wp-image-6252" srcset="https://matroidunion.org/wp-content/uploads/2026/07/matroid-union-theta.png 303w, https://matroidunion.org/wp-content/uploads/2026/07/matroid-union-theta-300x91.png 300w" sizes="auto, (max-width: 303px) 100vw, 303px" /></a><figcaption class="wp-element-caption">Two $\mathbb{Z}_3$-gain graphs. In the theta-graph on the left, all cycles are balanced; in the theta-graph on the right, only one cycle is balanced. Group elements are written additively.</figcaption></figure></div>
462
463
464<p>A $\Gamma$-gain graph $G$ gives rise to a matroid on $E(G)$ whose circuits are the balanced cycles of $G$, as well as the theta-subgraphs with three unbalanced cycles, and subgraphs formed by two edge-disjoint unbalanced cycles connected by a (possibly empty) path that is disjoint from the two cycles except for its first and last vertex.</p>
465
466
467
468<p>We can now define the Dowling geometry $\text{DG}(n,\Gamma)$ as the matroid obtained from the biased graph $K_n^\Gamma$ whose vertices are labelled $1, 2, \ldots, n$, which has one (unbalanced) loop attached at each vertex, and which has $|\Gamma|$ edges between vertices $i$ and $j$ (directed in towards the largest label, say), each labelled with a different group element.</p>
469
470
471
472<p>If every (non-loop) edge is labelled by the identity in $\Gamma$, then every cycle is balanced. In particular, $\text{DG}(n,\langle 1\rangle) \cong M(K_{n+1})$, where we write $\langle 1\rangle$ for the trivial group. So, graphic matroids are Dowling matroids.</p>
473
474
475
476<h2 class="wp-block-heading">Varieties</h2>
477
478
479
480<p>Apart from graphic matroids, matroids representable over finite fields, and Dowling matroids, are there any other natural classes of matroids that have a sequence of universal models? It turns out that we have to be a bit careful with our definitions, but a <a href="https://www.jstor.org/stable/pdf/1998894.pdf">beautiful result by Kahn and Kung</a> from 1982 states that the answer is, essentially, no.</p>
481
482
483
484<p>First, we need to define precisely what we mean by a universal model. Let $\mathcal{M}$ be a class of matroids. A sequence $M_1, M_2, M_3, \ldots$ of matroids is called a sequence of universal models for $\mathcal{M}$ if <em>(i)</em> for every $n$, $M_n$ is a rank-$n$ matroid, and <em>(ii)</em> for every $n$, every simple rank-$n$ matroid in $\mathcal{M}$ is isomorphic to a restriction of $M_n$. Thus, $\text{PG}(0,\mathbb{F}_q), \text{PG}(1,\mathbb{F}_q), \text{PG}(2, \mathbb{F}_q), \ldots$ is a sequence of universal models for the $\mathbb{F}_q$-representable matroids, and $\text{DG}(1,\Gamma), \text{DG}(2,\Gamma), \text{DG}(3,\Gamma), \ldots$ is a sequence of universal models for the Dowling matroids over the group $\Gamma$.</p>
485
486
487
488<p>Second, we need to be careful about our definition of &#8220;natural&#8221; class of matroids. A class $\mathcal{M}$ is called a hereditary class if it is closed under isomorphism, as well as under taking minors and direct sums; so, if $M,N \in \mathcal{M}$ and $e$ is an element of $M$, then each of $M\backslash e$, $M/e$, and $M\oplus N$ are in $\mathcal{M}$ as well.</p>
489
490
491
492<p>A variety of matroids is a hereditary class with a sequence of universal models. We are now ready to state Kahn and Kung&#8217;s result.</p>
493
494
495
496<p><strong>Theorem (Kahn–Kung, 1982).</strong> If $\mathcal{M}$ is a variety of matroids, then $\mathcal{M}$ is one of the following classes:</p>
497
498
499
500<ul>
501<li>Matroids representable over a finite field;</li>
502<li>Dowling matroids over a finite group; or</li>
503<li>Matchstick geometries or Origami geometries.</li>
504</ul>
505
506
507
508<p>The classes of matchstick and origami geometries have low connectivity. The universal models for matchstick geometries are $U_{2,n+1}^{\oplus k}$ and $U_{2,n+1}^{\oplus k} \oplus U_{1,1}$, depending on the parity of the rank, while the universal models for origami matroids are obtained from a basis ${b_1, …, b_r}$ by adding $n$ points freely to each of the lines spanned by pairs $\{b_i, b_{i+1}\}$.</p>
509
510
511
512<p>Each of the assumptions (that the class of matroids be minor-closed, closed under direct sum, and have a sequence of universal models) in K
512ahn and Kung&#8217;s theorem is necessary for its conclusion. It is an amusing exercise to come up with classes of matroids that satisfy only a subset of these assumptions but not the others.</p>
513					</div><!-- .entry-content -->
514		
515		<footer class="entry-meta">
516			
517										<span class="cat-links">
518					<span class="entry-utility-prep entry-utility-prep-cat-links">Posted in</span> <a href="https://matroidunion.org/?cat=1" rel="category">Matroids</a>			</span>
519							
520										<span class="sep"> | </span>
521								<span class="tag-links">
522					<span class="entry-utility-prep entry-utility-prep-tag-links">Tagged</span> <a href="https://matroidunion.org/?tag=ambient-space" rel="tag">ambient space</a>, <a href="https://matroidunion.org/?tag=dowling-geometry" rel="tag">dowling geometry</a>, <a href="https://matroidunion.org/?tag=variety" rel="tag">variety</a>			</span>
523							
524										<span class="sep"> | </span>
525						<span class="comments-link"><a href="https://matroidunion.org/?p=6246#comments"><b>1</b> Reply</a></span>
526			
527					</footer><!-- .entry-meta -->
528	</article><!-- #post-6246 -->
529
530				
531							<nav id="nav-below">
532				<h3 class="assistive-text">Post navigation</h3>
533									<div class="nav-previous"><a href="https://matroidunion.org/?paged=2" ><span class="meta-nav">&larr;</span> Older posts</a></div>
534				
535							</nav><!-- #nav-below -->
536			
537			
538			</div><!-- #content -->
539		</div><!-- #primary -->
540
541		<div id="secondary" class="widget-area" role="complementary">
542			<aside id="search-2" class="widget widget_search">	<form method="get" id="searchform" action="https://matroidunion.org/">
543		<label for="s" class="assistive-text">Search</label>
544		<input type="text" class="field" name="s" id="s" placeholder="Search" />
545		<input type="submit" class="submit" name="submit" id="searchsubmit" value="Search" />
546	</form>
547</aside><aside id="text-3" class="widget widget_text"><h3 class="widget-title">Twitter</h3>			<div class="textwidget"><a href="https://twitter.com/matroidunion" class="twitter-follow-button" data-show-count="false" data-lang="en" data-size="large">Follow @matroidunion</a>
548<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src="//platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs");</script>
548</div>
549		</aside><aside id="text-2" class="widget widget_text"><h3 class="widget-title">E-mail subscription</h3>			<div class="textwidget"><style>@import url('https://fonts.googleapis.com/css?family=Montserrat:700');@import url('https://fonts.googleapis.com/css?family=Montserrat:400');
550.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview {
551  display: flex !important;
552  flex-direction: column !important;
553  justify-content: center !important;
554  margin-top: 30px !important;
555  padding: clamp(17px, 5%, 40px) clamp(17px, 7%, 50px) !important;
556  max-width: none !important;
557  border-radius: 6px !important;
558  box-shadow: 0 5px 25px rgba(34, 60, 47, 0.25) !important;
559}
560.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview,
561.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview *{
562  box-sizing: border-box !important;
563}
564.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-heading {
565  width: 100% !important;
566}
567.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-heading h5{
568  margin-top: 0 !important;
569  margin-bottom: 0 !important;
570}
571.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field {
572  margin-top: 20px !important;
573  width: 100% !important;
574}
575.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field input {
576  width: 100% !important;
577  height: 40px !important;
578  border-radius: 6px !important;
579  border: 2px solid #e9e8e8 !important;
580  background-color: #fff !important;
581  outline: none !important;
582}
583.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field input {
584  color: #000000 !important;
585  font-family: "Montserrat" !important;
586  font-size: 14px !important;
587  font-weight: 400 !important;
588  line-height: 20px !important;
589  text-align: center !important;
590}
591.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field input::placeholder {
592  color: #000000 !important;
593  opacity: 1 !important;
594}
595
596.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field input:-ms-input-placeholder {
597  color: #000000 !important;
598}
599
600.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-input-field input::-ms-input-placeholder {
601  color: #000000 !important;
602}
603.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-submit-button {
604  margin-top: 10px !important;
605  width: 100% !important;
606}
607.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-submit-button button {
608  width: 100% !important;
609  height: 40px !important;
610  border: 0 !important;
611  border-radius: 6px !important;
612  line-height: 0px !important;
613}
614.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .form-preview .preview-submit-button button:hover {
615  cursor: pointer !important;
616}
617.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .powered-by-line {
618  color: #231f20 !important;
619  font-family: "Montserrat" !important;
620  font-size: 13px !important;
621  font-weight: 400 !important;
622  line-height: 25px !important;
623  text-align: center !important;
624  text-decoration: none !important;
625  display: flex !important;
626  width: 100% !important;
627  justify-content: center !important;
628  align-items: center !important;
629  margin-top: 10px !important;
630}
631.followit--follow-form-container[attr-a][attr-b][attr-c][attr-d][attr-e][attr-f] .powered-by-line img {
632  margin-left: 10px !important;
633  height: 1.13em !important;
634  max-height: 1.13em !important;
635}
636</style><div class="followit--follow-form-container" attr-a attr-b attr-c attr-d attr-e attr-f><form data-v-2bdb5506="" action="https://api.follow.it/subscription-form/QlMxVHpIcm1hcFVYbm43RlVXYUhtODBaK2hQNk9iSEtWeUpsM1B0L0E4VFFpcE53RTNWNXNGclkrOXREeGhnTTg1dnc4ZVBPeVVpOVZmdkdtS214NnJzOFcwMlVjNTUzOEpobkhVMklqbzRlaUJ0bDJmbnd6d05BQTZhbG44QU18Y3hVRUpsS25TTXZCL0d2a1dx
636RjN6dWhFN1crZGMrb09ER1c2QkJXeEhRcz0=/8" method="post"><div data-v-2bdb5506="" class="form-preview" style="background-color: rgb(255, 255, 255); position: relative;"><div data-v-2bdb5506="" class="preview-heading"><h5 data-v-2bdb5506="" style="text-transform: none !important; font-family: Montserrat; font-weight: bold; color: rgb(0, 0, 0); font-size: 16px; text-align: center;">
637                  Get new posts by email:
638                </h5></div> <div data-v-2bdb5506="" class="preview-input-field"><input data-v-2bdb5506="" type="email" name="email" required="required" placeholder="Enter your email" spellcheck="false" style="text-transform: none !important; font-family: Montserrat; font-weight: normal; color: rgb(0, 0, 0); font-size: 14px; text-align: center; background-color: rgb(255, 255, 255);"></div> <div data-v-2bdb5506="" class="preview-submit-button"><button data-v-2bdb5506="" type="submit" style="text-transform: none !important; font-family: Montserrat; font-weight: bold; color: rgb(255, 255, 255); font-size: 16px; text-align: center; background-color: rgb(0, 0, 0);">
639                  Subscribe
640                </button></div></div></form><a href="https://follow.it" class="powered-by-line">Powered by <img src="https://follow.it/static/img/colored-logo.svg" alt="follow.it" height="17px"/></a></div></div>
641		</aside><aside id="text-4" class="widget widget_text"><h3 class="widget-title">Feedly</h3>			<div class="textwidget"><a href='http://cloud.feedly.com/#subscription%2Ffeed%2Fhttp%3A%2F%2Fmatroidunion.org%2F%3Ffeed%3Drss2'  target='blank'><img id='feedlyFollow' src='http://s3.feedly.com/img/follows/feedly-follow-rectangle-volume-medium_2x.png' alt='follow us in feedly' width='71' height='28'></a></div>
642		</aside>
643		<aside id="recent-posts-2" class="widget widget_recent_entries">
644		<h3 class="widget-title">Recent Posts</h3>
645		<ul>
646											<li>
647					<a href="https://matroidunion.org/?p=6280">Representable Matroid Lifts</a>
648									</li>
649											<li>
650					<a href="https://matroidunion.org/?p=6262">Direct sum of q-matroids</a>
651									</li>
652											<li>
653					<a href="https://matroidunion.org/?p=6255">The cycle double cover theorem</a>
654									</li>
655											<li>
656					<a href="https://matroidunion.org/?p=6246">Matroid varieties</a>
657									</li>
658											<li>
659					<a href="https://matroidunion.org/?p=6233">Trouble with infinite oriented matroids</a>
660									</li>
661					</ul>
662
663		</aside><aside id="recent-comments-2" class="widget widget_recent_comments"><h3 class="widget-title">Recent Comments</h3><ul id="recentcomments"><li class="recentcomments"><span class="comment-author-link"><a href="https://dillon128.github.io/index.html" class="url" rel="ugc external nofollow">Dillon Mayhew</a></span> on <a href="https://matroidunion.org/?p=5320#comment-930002">Algebraic matroids</a></li><li class="recentcomments"><span class="comment-author-link">Relinde Jurrius</span> on <a href="https://matroidunion.org/?p=6262#comment-930001">Direct sum of q-matroids</a></li><li class="recentcomments"><span class="comment-author-link"><a href="http://www.latticetheory.net" class="url" rel="ugc external nofollow">Jonathan Farley</a></span> on <a href="https://matroidunion.org/?p=6262#comment-929999">Direct sum of q-matroids</a></li><li class="recentcomments"><span class="comment-author-link"><a href="http://www.matroidunion.org/stefan/" class="url" rel="ugc external nofollow">Stefan van Zwam</a></span> on <a href="https://matroidunion.org/?p=5320#comment-929998">Algebraic matroids</a></li><li class="recentcomments"><span class="comment-author-link">Daniel Bernstein</span> on <a href="https://matroidunion.org/?p=5320#comment-929997">Algebraic matroids</a></li></ul></aside><aside id="nav_menu-2" class="widget widget_nav_menu"><h3 class="widget-title">Other blogs and links</h3><div class="menu-other-blogs-and-links-container"><ul id="menu-other-blogs-and-links" class="menu"><li id="menu-item-15" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-15"><a href="http://symomega.wordpress.com/">SymOmega</a></li>
664<li id="menu-item-36" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-36"><a href="http://cameroncounts.wordpress.com/">Peter Cameron</a></li>
665<li id="menu-item-37" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-37"><a href="http://gilkalai.wordpress.com/">Gil Kalai</a></li>
666<li id="menu-item-599" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-599"><a href="http://www.openproblemgarden.org/category/matroid_theory">Open Problem Garden</a></li>
667</ul></div></aside>
667<aside id="archives-2" class="widget widget_archive"><h3 class="widget-title">Archives</h3>
668			<ul>
669					<li><a href='https://matroidunion.org/?m=202609'>September 2026</a></li>
670	<li><a href='https://matroidunion.org/?m=202608'>August 2026</a></li>
671	<li><a href='https://matroidunion.org/?m=202607'>July 2026</a></li>
672	<li><a href='https://matroidunion.org/?m=202606'>June 2026</a></li>
673	<li><a href='https://matroidunion.org/?m=202605'>May 2026</a></li>
674	<li><a href='https://matroidunion.org/?m=202604'>April 2026</a></li>
675	<li><a href='https://matroidunion.org/?m=202603'>March 2026</a></li>
676	<li><a href='https://matroidunion.org/?m=202602'>February 2026</a></li>
677	<li><a href='https://matroidunion.org/?m=202512'>December 2025</a></li>
678	<li><a href='https://matroidunion.org/?m=202511'>November 2025</a></li>
679	<li><a href='https://matroidunion.org/?m=202510'>October 2025</a></li>
680	<li><a href='https://matroidunion.org/?m=202506'>June 2025</a></li>
681	<li><a href='https://matroidunion.org/?m=202505'>May 2025</a></li>
682	<li><a href='https://matroidunion.org/?m=202504'>April 2025</a></li>
683	<li><a href='https://matroidunion.org/?m=202502'>February 2025</a></li>
684	<li><a href='https://matroidunion.org/?m=202412'>December 2024</a></li>
685	<li><a href='https://matroidunion.org/?m=202411'>November 2024</a></li>
686	<li><a href='https://matroidunion.org/?m=202410'>October 2024</a></li>
687	<li><a href='https://matroidunion.org/?m=202406'>June 2024</a></li>
688	<li><a href='https://matroidunion.org/?m=202405'>May 2024</a></li>
689	<li><a href='https://matroidunion.org/?m=202404'>April 2024</a></li>
690	<li><a href='https://matroidunion.org/?m=202403'>March 2024</a></li>
691	<li><a href='https://matroidunion.org/?m=202402'>February 2024</a></li>
692	<li><a href='https://matroidunion.org/?m=202401'>January 2024</a></li>
693	<li><a href='https://matroidunion.org/?m=202312'>December 2023</a></li>
694	<li><a href='https://matroidunion.org/?m=202311'>November 2023</a></li>
695	<li><a href='https://matroidunion.org/?m=202310'>October 2023</a></li>
696	<li><a href='https://matroidunion.org/?m=202309'>September 2023</a></li>
697	<li><a href='https://matroidunion.org/?m=202308'>August 2023</a></li>
698	<li><a href='https://matroidunion.org/?m=202307'>July 2023</a></li>
699	<li><a href='https://matroidunion.org/?m=202306'>June 2023</a></li>
700	<li><a href='https://matroidunion.org/?m=202305'>May 2023</a></li>
701	<li><a href='https://matroidunion.org/?m=202304'>April 2023</a></li>
702	<li><a href='https://matroidunion.org/?m=202303'>March 2023</a></li>
703	<li><a href='https://matroidunion.org/?m=202302'>February 2023</a></li>
704	<li><a href='https://matroidunion.org/?m=202301'>January 2023</a></li>
705	<li><a href='https://matroidunion.org/?m=202210'>October 2022</a></li>
706	<li><a href='https://matroidunion.org/?m=202205'>May 2022</a></li>
707	<li><a href='https://matroidunion.org/?m=202204'>April 2022</a></li>
708	<li><a href='https://matroidunion.org/?m=202203'>March 2022</a></li>
709	<li><a href='https://matroidunion.org/?m=202202'>February 2022</a></li>
710	<li><a href='https://matroidunion.org/?m=202201'>January 2022</a></li>
711	<li><a href='https://matroidunion.org/?m=202112'>December 2021</a></li>
712	<li><a href='https://matroidunion.org/?m=202111'>November 2021</a></li>
713	<li><a href='https://matroidunion.org/?m=202110'>October 2021</a></li>
714	<li><a href='https://matroidunion.org/?m=202109'>September 2021</a></li>
715	<li><a href='https://matroidunion.org/?m=202108'>August 2021</a></li>
716	<li><a href='https://matroidunion.org/?m=202107'>July 2021</a></li>
717	<li><a href='https://matroidunion.org/?m=202106'>June 2021</a></li>
718	<li><a href='https://matroidunion.org/?m=202105'>May 2021</a></li>
719	<li><a href='https://matroidunion.org/?m=202104'>April 2021</a></li>
720	<li><a href='https://matroidunion.org/?m=202103'>March 2021</a></li>
721	<li><a href='https://matroidunion.org/?m=202102'>February 2021</a></li>
722	<li><a href='https://matroidunion.org/?m=202101'>January 2021</a></li>
723	<li><a href='https://matroidunion.org/?m=202012'>December 2020</a></li>
724	<li><a href='https://matroidunion.org/?m=202011'>November 2020</a></li>
725	<li><a href='https://matroidunion.org/?m=202010'>October 2020</a></li>
726	<li><a href='https://matroidunion.org/?m=202009'>September 2020</a></li>
727	<li><a href='https://matroidunion.org/?m=202008'>August 2020</a></li>
728	<li><a href='https://matroidunion.org/?m=202007'>July 2020</a></li>
729	<li><a href='https://matroidunion.org/?m=202006'>June 2020</a></li>
730	<li><a href='https://matroidunion.org/?m=202005'>May 2020</a></li>
731	<li><a href='https://matroidunion.org/?m=202004'>April 2020</a></li>
732	<li><a href='https://matroidunion.org/?m=201910'>October 2019</a></li>
733	<li><a href='https://matroidunion.org/?m=201811'>November 2018</a></li>
734	<li><a href='https://matroidunion.org/?m=201810'>October 2018</a></li>
735	<li><a href='https://matroidunion.org/?m=201809'>September 2018</a></li>
736	<li><a href='https://matroidunion.org/?m=201802'>February 2018</a></li>
737	<li><a href='https://matroidunion.org/?m=201711'>November 2017</a></li>
738	<li><a href='https://matroidunion.org/?m=201710'>October 2017</a></li>
739	<li><a href='https://matroidunion.org/?m=201708'>August 2017</a></li>
740	<li><a href='https://matroidunion.org/?m=201706'>June 2017</a></li>
741	<li><a href='https://matroidunion.org/?m=201705'>May 2017</a></li>
742	<li><a href='https://matroidunion.org/?m=201702'>February 2017</a></li>
743	<li><a href='https://matroidunion.org/?m=201701'>January 2017</a></li>
744	<li><a href='https://matroidunion.org/?m=201612'>December 2016</a></li>
745	<li><a href='https://matroidunion.org/?m=201611'>November 2016</a></li>
746	<li><a href='https://matroidunion.org/?m=201609'>September 2016</a></li>
747	<li><a href='https://matroidunion.org/?m=201607'>July 2016</a></li>
748	<li><a href='https://matroidunion.org/?m=201606'>June 2016</a></li>
749	<li><a href='https://matroidunion.org/?m=201605'>May 2016</a></li>
750	<li><a href='https://matroidunion.org/?m=201604'>April 2016</a></li>
751	<li><a href='https://matroidunion.org/?m=201603'>March 2016</a></li>
752	<li><a href='https://matroidunion.org/?m=201602'>February 2016</a></li>
753	<li><a href='https://matroidunion.org/?m=201601'>January 2016</a></li>
754	<li><a href='https://matroidunion.org/?m=201512'>December 2015</a></li>
755	<li><a href='https://matroidunion.org/?m=201510'>October 2015</a></li>
756	<li><a href='https://matroidunion.org/?m=201509'>September 2015</a></li>
757	<li><a href='https://matroidunion.org/?m=201507'>July 2015</a></li>
758	<li><a href='https://matroidunion.org/?m=201506'>June 2015</a></li>
759	<li><a href='https://matroidunion.org/?m=201505'>May 2015</a></li>
760	<li><a href='https://matroidunion.org/?m=201504'>April 2015</a></li>
761	<li><a href='https://matroidunion.org/?m=201503'>March 2015</a></li>
762	<li><a href='https://matroidunion.org/?m=201502'>February 2015</a></li>
763	<li><a href='https://matroidunion.org/?m=201501'>January 2015</a></li>
764	<li><a href='https://matroidunion.org/?m=201412'>December 2014</a></li>
765	<li><a href='https://matroidunion.org/?m=201411'>November 2014</a></li>
766	<li><a href='https://matroidunion.org/?m=201410'>October 2014</a></li>
767	<li><a href='https://matroidunion.org/?m=201408'>August 2014</a></li>
768	<li><a href='https://matroidunion.org/?m=201407'>July 2014</a></li>
769	<li><a href='https://matroidunion.org/?m=201406'>June 2014</a></li>
770	<li><a href='https://matroidunion.org/?m=201405'>May 2014</a></li>
771	<li><a href='https://matroidunion.org/?m=201404'>April 2014</a></li>
772	<li><a href='https://matroidunion.org/?m=201403'>March 2014</a></li>
773	<li><a href='https://matroidunion.org/?m=201402'>February 2014</a></li>
774	<li><a href='https://matroidunion.org/?m=201401'>January 2014</a></li>
775	<li><a href='https://matroidunion.org/?m=201312'>December 2013</a></li>
776	<li><a href='https://matroidunion.org/?m=201311'>November 2013</a></li>
777	<li><a href='https://matroidunion.org/?m=201310'>October 2013</a></li>
778	<li><a href='https://matroidunion.org/?m=201309'>September 2013</a></li>
779	<li><a href='https://matroidunion.org/?m=201308'>August 2013</a></li>
780	<li><a href='https://matroidunion.org/?m=201307'>July 2013</a></li>
781			</ul>
782
783			</aside><aside id="meta-2" class="widget widget_meta"><h3 class="widget-title">Meta</h3>
784		<ul>
785						<li><a href="https://matroidunion.org/wp-login.php">Log in</a></li>
786			<li><a href="https://matroidunion.org/?feed=rss2">Entries feed</a></li>
787			<li><a href="https://matroidunion.org/?feed=comments-rss2">Comments feed</a></li>
788
789			<li><a href="https://wordpress.org/">WordPress.org</a></li>
790		</ul>
791
792		</aside>		</div><!-- #secondary .widget-area -->
793
794	</div><!-- #main -->
795
796	<footer id="colophon">
797
798			
799
800			<div id="site-generator">
801												<a href="https://wordpress.org/" class="imprint" title="Semantic Personal Publishing Platform">
802					Proudly powered by WordPress				</a>
803			</div>
804	</footer><!-- #colophon -->
805</div><!-- #page -->
806
807<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@4/tex-chtml.js?ver=6.8.10" id="mathjax-js"></script>
vendor: 1 bytes, line 807
807
808<script type="text/javascript" id="wp_slimstat-js-extra">
809/* <![CDATA[ */
810var SlimStatParams = {"transport":"ajax","ajaxurl_rest":"https:\/\/matroidunion.org\/index.php?rest_route=\/slimstat\/v1\/hit","ajaxurl_rest_query":"https:\/\/matroidunion.org\/index.php?rest_route=\/slimstat\/v1\/hit","resturl":"https:\/\/matroidunion.org\/index.php?rest_route=\/","ajaxurl_ajax":"https:\/\/matroidunion.org\/wp-admin\/admin-ajax.php","ajaxurl":"https:\/\/matroidunion.org\/wp-admin\/admin-ajax.php","baseurl":"\/","dnt":"noslimstat,ab-item","ci":"eyJjb250ZW50X3R5cGUiOiJob21lIn0-.7bae698d2674a10bd7d19d3b913afeafebb73503c8e3b70be74f91716da3a460","wp_rest_nonce":"e17ccc019d","is_logged_in":"0","wp_consent_integration":"disabled","consent_integration":"","consent_level_integration":"statistics","respect_dnt":"off","gdpr_enabled":"off","anonymous_tracking":"off","anonymize_ip":"no","hash_ip":"on","set_tracker_cookie":"on","use_slimstat_banner":"off"};
811/* ]]> */
812</script>
vendor: 1 bytes, line 812
812
813<script defer type="text/javascript" src="https://cdn.jsdelivr.net/wp/wp-slimstat/tags/5.5.0/wp-slimstat.min.js" id="wp_slimstat-js"></script>
813
814
815</body>
816</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.