Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlmost balanced biased graph representations of frame matroids
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a 3-connected biased graph $Omega$ with a balancing vertex, and with frame matroid $F(Omega)$ nongraphic and 3-connected, we determine all biased graphs $Omega$ with $F(Omega) = F(Omega)$. As a consequence, we show that if $M$ is a 4-connected nongraphic frame matroid represented by a biased graph $Omega$ having a balancing vertex, then $Omega$ essentially uniquely represents $M$. More precisely, all biased graphs representing $M$ are obtained from $Omega$ by replacing a subset of the edges incident to its unique balancing vertex with unbalanced loops.
rate research
Read More
Let $M$ be a 3-connected matroid and let $mathbb F$ be a field. Let $A$ be a matrix over $mathbb F$ representing $M$ and let $(G,mathcal B)$ be a biased graph representing $M$. We characterize the relationship between $A$ and $(G,mathcal B)$, settling four conjectures of Zaslavsky. We show that for each matrix representation $A$ and each biased graph representation $(G,mathcal B)$ of $M$, $A$ is projectively equivalent to a canonical matrix representation arising from $G$ as a gain graph over $mathbb F^+$ or $mathbb F^times$. Further, we show that the projective equivalence classes of matrix representations of $M$ are in one-to-one correspondence with the switching equivalence classes of gain graphs arising from $(G,mathcal B)$.
We investigate the set of excluded minors of connectivity 2 for the class of frame matroids. We exhibit a list $mathcal{E}$ of 18 such matroids, and show that if $N$ is such an excluded minor, then either $N in mathcal{E}$ or $N$ is a 2-sum of $U_{2,4}$ and a 3-connected non-binary frame matroid.
Many machine learning algorithms are trained and evaluated by splitting data from a single source into training and test sets. While such focus on in-distribution learning scenarios has led to interesting advancement, it has not been able to tell if models are relying on dataset biases as shortcuts for successful prediction (e.g., using snow cues for recognising snowmobiles), resulting in biased models that fail to generalise when the bias shifts to a different class. The cross-bias generalisation problem has been addressed by de-biasing training data through augmentation or re-sampling, which are often prohibitive due to the data collection cost (e.g., collecting images of a snowmobile on a desert) and the difficulty of quantifying or expressing biases in the first place. In this work, we propose a novel framework to train a de-biased representation by encouraging it to be different from a set of representations that are biased by design. This tactic is feasible in many scenarios where it is much easier to define a set of biased representations than to define and quantify bias. We demonstrate the efficacy of our method across a variety of synthetic and real-world biases; our experiments show that the method discourages models from taking bias shortcuts, resulting in improved generalisation. Source code is available at https://github.com/clovaai/rebias.
It is well known that the coefficients of the matching polynomial are unimodal. Unimodality of the coefficients (or their absolute values) of other graph polynomials have been studied as well. One way to prove unimodality is to prove real-rootedness.` Recently I. Beaton and J. Brown (2020) proved the for almost all graphs the coefficients of the domination polynomial form a unimodal sequence, and C. Barton, J. Brown and D. Pike (2020) proved that the forest polynomial (aka acyclic polynomial) is real-rooted iff $G$ is a forest. Let $mathcal{A}$ be a graph property, and let $a_i(G)$ be the number of induced subgraphs of order $i$ of a graph $G$ which are in $mathcal{A}$. Inspired by their results we prove: {bf Theorem:} If $mathcal{A}$ is the complement of a hereditary property, then for almost all graphs in $G(n,p)$ the sequence $a_i(G)$ is unimodal. {bf Theorem:} If $mathcal{A}$ is a hereditary property which contains a graph which is not a clique or the complement of a clique, then the graph polynomial $P_{mathcal{A}}(G;x) = sum_i a_i(G) x^i$ is real-rooted iff $G in mathcal{A}$.
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
