7 papers · 1 filter
Expected cost in Combinatorial Optimization under color constraints
Patrick Bennett, Alan Frieze, Wesley Pegden
We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a comp…
Binomial Random Matroids
Patrick Bennett, Alan Frieze
Let be a random collection of -subsets of where each possible set is present independently with probability . Let …
On Minimum Cost Rainbow Structures
Patrick Bennett, Quentin Dubroff, Alan Frieze +1
We discuss the expected minimum cost of rainbow spanning trees and Hamilton cycles in randomly edge colored random graphs.
Some Maker-Breaker games on hypergraphs
Patrick Bennett, Alan Frieze, Wesley Pegden
We consider some biased Maker-Breaker games. Starting with the complete -uniform hypergraph on vertices, at each turn Maker claims one edge, and then Breaker claims edge…
The intersection of a random geometric graph with an Erdős-Rényi graph
Patrick Bennett, Alan Frieze, Wesley Pegden
We study the intersection of a random geometric graph with an Erdős-Rényi graph. Specifically, we generate the random geometric graph by choosing points uniformly at…
Some online Maker-Breaker games
Patrick Bennett, Alan Frieze
We consider some Maker-Breaker games of the following flavor. We have some set of items for purchase. Maker's goal is to purchase some member of a given family $\cH$ of subsets…
Weighted tree games
Patrick Bennett, Alan Frieze
We consider a variation on Maker-Breaker games on graphs or digraphs where the edges have random costs. We assume that Maker wishes to choose the edges of a spanning tree, but wish…