Struct TuranDensityComputer 

pub struct TuranDensityComputer {
    pub forbidden_clique: usize,
    pub bounds: Vec<(usize, u64)>,
}

Computes Turán densities and exact Turán numbers for small graphs.

Fields

forbidden_clique: usize

The forbidden graph (number of vertices in K_{r+1}).

bounds: Vec<(usize, u64)>

Precomputed upper bounds for various n.

Implementations

impl TuranDensityComputer

pub fn new(r: usize) -> Self

Create a Turán density computer forbidding K_{r+1}.

pub fn turan_edges(&self, n: usize) -> u64

Compute ex(n, K_{r+1}) = number of edges in the Turán graph T(n,r).

T(n,r) has n vertices partitioned into r equal parts with all edges between parts. |E(T(n,r))| = (r-1)/(2r) * n² (asymptotically).

pub fn density(&self) -> (usize, usize)

Compute the Turán density π(K_{r+1}) = (r-1)/r.

Returns the numerator and denominator.

pub fn cache_bound(&mut self, n: usize, bound: u64)

Cache a precomputed bound ex(n, K_{r+1}) = bound.

Trait Implementations

impl Clone for TuranDensityComputer

fn clone(&self) -> TuranDensityComputer

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TuranDensityComputer

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.