A. Frieze

activity

20242026

collaborators

Showing math.COShow all

10 papers · 1 filter

math.CO2026

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…

math.CO2026

Coloring powers of random graphs

Alan Frieze, Ross Kang, Aditya Raut +2

Given a graph $G$ and an integer $r \geq 1$ , the $r$ th power $G^{r}$ of $G$ is the graph obtained from $G$ by adding edges for all pairs of distinct vertices at distance at most $r$ fr…

math.CO2026

Edge disjoint Hamilton cycles in random digraphs of constant minimum degree

Colin Cooper, Alan Frieze

We study the existence of directed Hamilton cycles in random digraphs with $m$ edges where we condition on minimum in- and out-degree $\d \ge k+1$, where $k \geq 1$ . Denote such a r…

math.CO2026

Binomial Random Matroids

Patrick Bennett, Alan Frieze

Let $B = B_{k, n, p}$ be a random collection of $k$ -subsets of $[n]$ where each possible set is present independently with probability $p$ . Let $E_{B}$ …

math.CO2025

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.

math.CO2025

Some Maker-Breaker games on hypergraphs

Patrick Bennett, Alan Frieze, Wesley Pegden

We consider some biased Maker-Breaker games. Starting with the complete $k$ -uniform hypergraph on $n$ vertices, at each turn Maker claims one edge, and then Breaker claims $b$ edge…

math.CO2025

Loose paths in random ordered hypergraphs

Andrzej Dudek, Alan Frieze, Wesley Pegden

We consider the length of {\em ordered loose paths} in the random $r$ -uniform hypergraph $H = H^{(r)} (n, p)$ . A ordered loose path is a sequence of edges $E_{1}, E_{2}, \dots, E_{ℓ}$ wher…

math.CO2024

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 $G (n, r)$ by choosing $n$ points uniformly at…

math.CO2024

Some online Maker-Breaker games

Patrick Bennett, Alan Frieze

We consider some Maker-Breaker games of the following flavor. We have some set $V$ of items for purchase. Maker's goal is to purchase some member of a given family $\cH$ of subsets…

math.CO2024

The maximum degree of the $r$ th power of a sparse random graph

Alan Frieze, Aditya Raut

Let $G_{n, p}^{r}$ denote the $r$ th power of the random graph $G_{n, p}$ , where $p = c / n$ for a positive constant $c$ . We prove that w.h.p. the maximum degree $Δ\left(G^r_{n,p}\right)\si…

Expected cost in Combinatorial Optimization under color constraints

Coloring powers of random graphs

Edge disjoint Hamilton cycles in random digraphs of constant minimum degree

Binomial Random Matroids

On Minimum Cost Rainbow Structures

Some Maker-Breaker games on hypergraphs

Loose paths in random ordered hypergraphs

The intersection of a random geometric graph with an Erdős-Rényi graph

Some online Maker-Breaker games

The maximum degree of the rth power of a sparse random graph

The maximum degree of the $r$ th power of a sparse random graph