BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Attila Joó appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We give a common matroidal generalisation of `A Cantor-Bernstein theorem for paths in graphs' by Diestel and Thomassen and `A Cantor-Bernstein-type theorem for spanning trees in infinite graphs' by ourselves.
Fair division with unequal shares is an intensively studied recourse allocation problem. For $ i\in [n] $, let $ μ_i $ be an atomless probability measure on the measurable space $(C,\mathcal{S}) $ and let $ t_i $ be positive numbers (entitlements) with $ \sum_{i=1}^{n}t_i=1 $. A fair division is a partition of $ C $ into sets $ S_i\in \mathcal{S} $ with $ μ_i(S_i)\geq t_i$ for every $ i\in [n] $. We introduce new algorithms to solve the fair division problem with irrational entitlements. They are based on the classical Last diminisher technique and we believe that they are simpler than the known methods. Then we show that a fair division always exists even for infinitely many players.
The Greene-Magnanti theorem states that if $ M $ is a finite matroid, $ B_0 $ and $ B_1 $ are bases and $ B_0=\bigcup_{i=1}^{n} X_i $ is a partition, then there is a partition $ B_1=\bigcup_{i=1}^{n}Y_i $ such that $ (B_0 \setminus X_i) \cup Y_i $ is a base for every $ i $. The special case where each $ X_i $ is a singleton can be rephrased as the existence of a perfect matching in the base transition graph. Pouzet conjectured that this remains true in infinite dimensional vector spaces. Later he and Aharoni answered this conjecture affirmatively not just for vector spaces but for infinite matroids. We prove two generalisations of their result. On the one hand, we show that `being a singleton' can be relaxed to `being finite' and this is sharp in the sense the exclusion of infinite sets is really necessary. On the other hand, we prove that if $ B_0$ and $ B_1 $ are bases, then there is a bijection $ F $ between their finite subsets such that $ (B_0\setminus I) \cup F(I) $ is a base for every $ I$. In contrast to the approach of Aharoni and Pouzet, our proofs are completely elementary, they do not rely on infinite matching theory.
Nash-Williams proved that for an undirected graph $ G $ the set $ E(G) $ can be partitioned into cycles if and only if every cut has either even or infinite number of edges. Later C. Thomassen gave a simpler proof for this and conjectured the following directed analogue of the theorem: the edge set of a digraph can be partitioned into directed cycles if and only if for each subset of the vertices the cardinality of the ingoing and the outgoing edges are equal. The aim of the paper is to prove this conjecture.
We prove the following conjecture of S. Thomassé: for every (potentially infinite) digraph $ D $ it is possible to iteratively reverse directed cycles in such a way that the dichromatic number of the final reorientation $ D^{*} $ of $ D $ is at most two and each edge is flipped only finitely many times. In addition, we guarantee that in every strong component of $ D^{*} $ all the local edge-connectivities are finite and any edge is reversed at most twice.