# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

585 questions
Filter by
Sorted by
Tagged with
0answers
12 views

### Knapsack Variant

I’m looking for algorithms to solve the following Knapsack variant: Given: A Knapsack of fixed size; A set of K item types. Item size within each type may be chosen/selected/solved-for between two ...
1answer
186 views

### The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows: $$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$ Apparently, Knuth was able to prove that ...
0answers
76 views

### Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
1answer
84 views

### Placing color boxes on a colored image such that color consistency is maximized

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem. Given an image with black background that contains blobs whose ...
0answers
58 views

0answers
72 views

### Linear optimization over intersection of totally unimodular matrices

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...
0answers
100 views

### Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
1answer
118 views

2answers
225 views

### Is perfect matching for bipartite graph with no cycles unique?

Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching. My question is if the balanced bipartite graph is also ...
0answers
140 views

### How to represent boolean tree + algorithm as a mathematical formula

In programming say you have a boolean tree like this: ...
1answer
147 views

### Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
0answers
74 views

### Nim-game variant - weird ending condition

the game is structured like this: two players the players alternate moves 4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$ at each move, the player can either remove one or two elements from ...
2answers
288 views

### NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
2answers
3k views

1answer
1k views

### Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
1answer
201 views

### Finding subgraphs with high treewidth and constant degree

I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
2answers
146 views

### Does the first order theory of a finite structure have bounded quantifier rank?

Let $\mathfrak{A}$ be any finite structure. Does its first order theory $\mathfrak{T} := \mathfrak{TH}(\mathfrak{A})$ have bounded quantifier rank, in the sense that there is a $q\in\mathbb{N}$ ...
1answer
67 views