Objective functions with redundant domains

Journal article

Affif Chaouche, F., Rutherford, C. and Whitty, R. (2012). Objective functions with redundant domains. Journal of Combinatorial Optimization. 26, pp. 372-384. https://doi.org/10.1007/s10878-012-9468-9
AuthorsAffif Chaouche, F., Rutherford, C. and Whitty, R.

Let (E,A) be a set system consisting of a finite collection A of subsets of a ground set E, and suppose that we have a function ϕ which maps A into some set S. Now removing a subset K from E gives a restriction A(K¯) to those sets of A disjoint from K, and we have a corresponding restriction ϕ|A(K¯) of our function ϕ. If the removal of K does not affect the image set of ϕ, that is Im(ϕ|A(X¯))=Im(ϕ), then we will say that K is a kernel set of A with respect to ϕ. Such sets are potentially useful in optimisation problems defined in terms of ϕ. We will call the set of all subsets of E that are kernel sets with respect to ϕ a kernel system and denote it by Kerϕ(A). Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if A is the collection of forests in a graph G with coloured edges and ϕ counts how many edges of each colour occurs in a forest then Kerϕ(A) is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if A is the power set of a set of positive integers, and ϕ is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that Kerϕ(A) is essentially never a matroid.

KeywordsMatroid, Optimization, Objective function, Duality, Turán-type problems
JournalJournal of Combinatorial Optimization
Journal citation26, pp. 372-384
Digital Object Identifier (DOI)https://doi.org/10.1007/s10878-012-9468-9
Web address (URL)https://doi.org/10.1007/s10878-012-9468-9
Publication dates
PrintAug 2013
Online17 Mar 2012
Publication process dates
Deposited15 Feb 2022
Accepted author manuscript
File Access Level
Permalink -


Download files

Accepted author manuscript
License: CC BY 4.0
File access level: Open

  • 32
    total views
  • 81
    total downloads
  • 1
    views this month
  • 5
    downloads this month

Export as

Related outputs

Generalized pentagonal geometries
Forbes, A. and Rutherford, C. G. (2021). Generalized pentagonal geometries. Journal of Combinatorial Designs. https://doi.org/10.1002/jcd.21811
Some results on the structure and spectra of matrix-products
Banaji, M. and Rutherford, C. G. (2015). Some results on the structure and spectra of matrix-products. Linear Algebra and Its Applications. 474, pp. 192-212. https://doi.org/10.1016/j.laa.2015.02.008
Pancyclicity when each cycle must pass exactly k Hamilton cycle chords.
Chaouche, FA, Rutherford, CG and Whitty, R (2015). Pancyclicity when each cycle must pass exactly k Hamilton cycle chords. Discussiones Mathematicae Graph Theory. 35 (3), pp. 533-539. https://doi.org/10.7151/dmgt.1818
P-matrices and signed digraphs
Banaji, M and Rutherford, CG (2010). P-matrices and signed digraphs. Discrete Mathematics. 311 (4), pp. 295-301. https://doi.org/10.1016/j.disc.2010.10.018
Covering radii are not matroid invariants
Britz, T. and Rutherford, C. (2005). Covering radii are not matroid invariants. 296 (1), pp. 117-120. https://doi.org/10.1016/j.disc.2005.03.002