{"data":{"id":"10.48550/arxiv.1903.11988","type":"dois","attributes":{"doi":"10.48550/arxiv.1903.11988","prefix":"10.48550","suffix":"arxiv.1903.11988","identifiers":[{"identifier":"1903.11988","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1903.11988"}],"creators":[{"name":"DeVos, Matt","nameType":"Personal","givenName":"Matt","familyName":"DeVos","affiliation":[],"nameIdentifiers":[]},{"name":"Kwon, O-joung","nameType":"Personal","givenName":"O-joung","familyName":"Kwon","affiliation":[],"nameIdentifiers":[]},{"name":"Oum, Sang-il","nameType":"Personal","givenName":"Sang-il","familyName":"Oum","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Branch-depth: Generalizing tree-depth of graphs"}],"publisher":"arXiv","container":{},"publicationYear":2019,"subjects":[{"lang":"en","subject":"Combinatorics (math.CO)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"05C75","subjectScheme":"MSC"}],"contributors":[],"dates":[{"date":"2019-03-28T14:11:54Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2019-03-29T00:18:01Z","dateType":"Updated","dateInformation":"v1"},{"date":"2020-11-04T08:34:56Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2020-11-05T01:14:17Z","dateType":"Updated","dateInformation":"v2"},{"date":"2019-03","dateType":"Available","dateInformation":"v1"},{"date":"2019","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1016/j.ejc.2020.103186","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G = (V,E)$ and a subset $A $ of $E$ we let $λ_G (A)$ be the number of vertices incident with an edge in $A$ and an edge in $E \\setminus A$. For a subset $X$ of $V$, let $ρ_G(X)$ be the rank of the adjacency matrix between $X$ and $V \\setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions $λ_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions $ρ_G$ has bounded branch-depth, which we call the rank-depth of graphs. Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by the restriction.","descriptionType":"Abstract"},{"description":"36 pages, 2 figures. Final version","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xOTAzLjExOTg4PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTkwMy4xMTk4ODwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5EZVZvcywgTWF0dDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+TWF0dDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5EZVZvczwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Ld29uLCBPLWpvdW5nPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5PLWpvdW5nPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkt3b248L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+T3VtLCBTYW5nLWlsPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5TYW5nLWlsPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPk91bTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QnJhbmNoLWRlcHRoOiBHZW5lcmFsaXppbmcgdHJlZS1kZXB0aCBvZiBncmFwaHM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTk8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5Db21iaW5hdG9yaWNzIChtYXRoLkNPKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJNU0MiPjA1Qzc1PC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOS0wMy0yOFQxNDoxMTo1NFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOS0wMy0yOVQwMDoxODowMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIwLTExLTA0VDA4OjM0OjU2WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIwLTExLTA1VDAxOjE0OjE3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTktMDM8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4xMDE2L2ouZWpjLjIwMjAuMTAzMTg2PC9yZWxhdGVkSWRlbnRpZmllcj4KICA8L3JlbGF0ZWRJZGVudGlmaWVycz4KICA8dmVyc2lvbj4yPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9hcnhpdi5vcmcvbGljZW5zZXMvbm9uZXhjbHVzaXZlLWRpc3RyaWIvMS4wLyI+YXJYaXYub3JnIHBlcnBldHVhbCwgbm9uLWV4Y2x1c2l2ZSBsaWNlbnNlPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+V2UgcHJlc2VudCBhIGNvbmNlcHQgY2FsbGVkIHRoZSBicmFuY2gtZGVwdGggb2YgYSBjb25uZWN0aXZpdHkgZnVuY3Rpb24sIHRoYXQgZ2VuZXJhbGl6ZXMgdGhlIHRyZWUtZGVwdGggb2YgZ3JhcGhzLiBUaGVuIHdlIHByb3ZlIHR3byB0aGVvcmVtcyBzaG93aW5nIHRoYXQgdGhpcyBjb25jZXB0IGFsaWducyBjbG9zZWx5IHdpdGggdGhlIG5vdGlvbnMgb2YgdHJlZS1kZXB0aCBhbmQgc2hydWItZGVwdGggb2YgZ3JhcGhzIGFzIGZvbGxvd3MuIEZvciBhIGdyYXBoICRHID0gKFYsRSkkIGFuZCBhIHN1YnNldCAkQSAkIG9mICRFJCB3ZSBsZXQgJM67X0cgKEEpJCBiZSB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluY2lkZW50IHdpdGggYW4gZWRnZSBpbiAkQSQgYW5kIGFuIGVkZ2UgaW4gJEUgXHNldG1pbnVzIEEkLiBGb3IgYSBzdWJzZXQgJFgkIG9mICRWJCwgbGV0ICTPgV9HKFgpJCBiZSB0aGUgcmFuayBvZiB0aGUgYWRqYWNlbmN5IG1hdHJpeCBiZXR3ZWVuICRYJCBhbmQgJFYgXHNldG1pbnVzIFgkIG92ZXIgdGhlIGJpbmFyeSBmaWVsZC4gV2UgcHJvdmUgdGhhdCBhIGNsYXNzIG9mIGdyYXBocyBoYXMgYm91bmRlZCB0cmVlLWRlcHRoIGlmIGFuZCBvbmx5IGlmIHRoZSBjb3JyZXNwb25kaW5nIGNsYXNzIG9mIGZ1bmN0aW9ucyAkzrtfRyQgaGFzIGJvdW5kZWQgYnJhbmNoLWRlcHRoIGFuZCBzaW1pbGFybHkgYSBjbGFzcyBvZiBncmFwaHMgaGFzIGJvdW5kZWQgc2hydWItZGVwdGggaWYgYW5kIG9ubHkgaWYgdGhlIGNvcnJlc3BvbmRpbmcgY2xhc3Mgb2YgZnVuY3Rpb25zICTPgV9HJCBoYXMgYm91bmRlZCBicmFuY2gtZGVwdGgsIHdoaWNoIHdlIGNhbGwgdGhlIHJhbmstZGVwdGggb2YgZ3JhcGhzLgogIEZ1cnRoZXJtb3JlIHdlIGludmVzdGlnYXRlIHZhcmlvdXMgcG90ZW50aWFsIGdlbmVyYWxpemF0aW9ucyBvZiB0cmVlLWRlcHRoIHRvIG1hdHJvaWRzIGFuZCBwcm92ZSB0aGF0IG1hdHJvaWRzIHJlcHJlc2VudGFibGUgb3ZlciBhIGZpeGVkIGZpbml0ZSBmaWVsZCBoYXZpbmcgbm8gbGFyZ2UgY2lyY3VpdHMgYXJlIHdlbGwtcXVhc2ktb3JkZXJlZCBieSB0aGUgcmVzdHJpY3Rpb24uPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj4zNiBwYWdlcywgMiBmaWd1cmVzLiBGaW5hbCB2ZXJzaW9uPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/1903.11988","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-01T00:28:02.000Z","registered":"2022-03-01T00:28:03.000Z","published":"2019","updated":"2022-03-01T00:28:03.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1903.11988","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}