Submodular functions and rooted trees

DOI10.1007/s00224-022-10092-xzbMath1504.05206OpenAlexW4288489074MaRDI QIDQ2095463

Yinfeng Zhu, Yaokun Wu

Publication date: 16 November 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10092-x

zbMATH Keywords

weighted hypergraphpseudorandom graphanticore\((\alpha, \beta)\) down-setBBT spanning tree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorics of partially ordered sets (06A07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Set functions, games and capacities in decision making
• The size Ramsey number of a directed path
• A simple proof for the convexity of the Choquet integral
• Arithmetic for rooted trees
• Partial probabilistic information
• Algebraic duality theorems for infinite LP problems
• A new class of convex games on \(\sigma\)-algebras and the optimal partitioning of measurable spaces
• Connectivity functions and polymatroids
• Extreme points of a set of contents majorized by a submodular set function
• Convex games with an infinite number of players and sequencing situations
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Homomorphisms and Ramsey properties of antimatroids
• Combinatorial representation and convex dimension of convex geometries
• The sigma-core of a cooperative game
• Uncertainty relation for multidimensional discrete signals
• Decomposing a balanced game: a necessary and sufficient condition for the nonemptiness of the core
• Phylogenetic flexibility via Hall-type inequalities and submodularity
• Representation of lattices via set-colored posets
• The sigma-core of convex games and the problem of measure extension
• Trees as semilattices
• Last passage percolation on the complete graph
• Order- and graph-theoretic investigation of dimensions of finite topological spaces and Alexandroff spaces
• The concept of duality in convex analysis, and the characterization of the Legendre transform
• Blocking duality for \(p\)-modulus on networks and applications
• A note on weighted rooted trees
• Countably additive measures in cores of games
• Cores of convex games
• A characterization of perfect graphs
• Cores of exact games. I
• A decomposition theorem for partially ordered sets
• Theory of capacities
• The Erdös--Hajnal Conjecture for Long Holes and Antiholes
• A double look at duality
• Polymatroidal dependence structure of a set of random variables
• Discrete Convex Analysis
• Gomory‐Hu trees of infinite graphs with finite total weight
• The Generic Chaining
• Extremal Problems for Finite Sets
• Weighted Rooted Trees: Fat or Tall?
• History of Banach Spaces and Linear Operators
• A new notion of convexity in digraphs with an application to Bayesian networks
• Nombre chromatique et plus longs chemins d'un graphe
• Wurzelbäume und unendliche Wege in Graphen
• A Dual of Dilworth's Decomposition Theorem
• Finitely Additive Measures
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• Maharam's problem