Binary functions, degeneracy, and alternating dimaps

Research output: Contribution to journalArticleResearchpeer-review

Abstract

This paper continues the study of combinatorial properties of binary functions — that is, functions f:2 E →ℂ such that f(0̸)=1, where E is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements – analogues of loops and coloops – in binary functions, with respect to any set of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte's alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.

Original languageEnglish
Pages (from-to)1510-1519
Number of pages10
JournalDiscrete Mathematics
Volume342
Issue number5
DOIs
Publication statusPublished - 22 Feb 2019

Keywords

  • Alternating dimap
  • Binary function
  • Degeneracy
  • Minor
  • Transform
  • Triality

Cite this

@article{b817ddbfb6a14dd78c7ca95f5337feff,
title = "Binary functions, degeneracy, and alternating dimaps",
abstract = "This paper continues the study of combinatorial properties of binary functions — that is, functions f:2 E →ℂ such that f(0̸)=1, where E is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements – analogues of loops and coloops – in binary functions, with respect to any set of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte's alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.",
keywords = "Alternating dimap, Binary function, Degeneracy, Minor, Transform, Triality",
author = "Farr, {G. E.}",
year = "2019",
month = "2",
day = "22",
doi = "10.1016/j.disc.2019.01.029",
language = "English",
volume = "342",
pages = "1510--1519",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "5",

}

Binary functions, degeneracy, and alternating dimaps. / Farr, G. E.

In: Discrete Mathematics, Vol. 342, No. 5, 22.02.2019, p. 1510-1519.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Binary functions, degeneracy, and alternating dimaps

AU - Farr, G. E.

PY - 2019/2/22

Y1 - 2019/2/22

N2 - This paper continues the study of combinatorial properties of binary functions — that is, functions f:2 E →ℂ such that f(0̸)=1, where E is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements – analogues of loops and coloops – in binary functions, with respect to any set of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte's alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.

AB - This paper continues the study of combinatorial properties of binary functions — that is, functions f:2 E →ℂ such that f(0̸)=1, where E is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements – analogues of loops and coloops – in binary functions, with respect to any set of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte's alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.

KW - Alternating dimap

KW - Binary function

KW - Degeneracy

KW - Minor

KW - Transform

KW - Triality

UR - http://www.scopus.com/inward/record.url?scp=85061791052&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2019.01.029

DO - 10.1016/j.disc.2019.01.029

M3 - Article

VL - 342

SP - 1510

EP - 1519

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 5

ER -