Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

768 questions
Filter by
Sorted by
Tagged with
92 views

Expected Entropy of the Empirical Distribution

Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$. Let's suppose I sample from ...
• 141
15 views

Analysis of LRU algorithm with uniformly random access

Consider the following model of LRU: The cache can hold $k$ pages. The memory has $n$ pages. In each $t \in \{1, 2, \dotsc, T\}$ the program selects a random page to access independently (i.e. each ...
43 views

Binary subset rank and unrank

Let there be "N" bits. We want to rank and unrank a specific subset of bit combinations based on the following criteria - ...
• 25
56 views

Number of graphs that almost contain a $k$-clique

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$...
• 1,696
88 views

The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions. In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its ...
1 vote
I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...