# Tagged Questions

Questions related to combinatorics and discrete mathematical structures

96 views

### Can the “mutual independence” condition in the Lovász local lemma be weakened?

The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows. Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is ...
27 views

### How to Estimate Sizes of Native Pictures Based on Matrix Presentations? [closed]

Condition: estimate the theoretical size of native resolution in picture Goal: quality assurance of plotted data Pseudocode in Matlab where imagesc(x,y,Z) specifies ...
59 views

### On the size of residue classes

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$ ...
156 views

### Structured set of binary words

Definitions: Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$. For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that: Every element $e$ ...
47 views

### Individualization of two Subgraphs

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
84 views

### The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
216 views

177 views

174 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
51 views

### Approximations for the Stable Fixtures Problem

I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
36 views

### Complexity of fixed fractional relaxations

I recently stumbled upon a curious relaxation of a combinatorial problem that was restricted to a fixed subset of fractional solutions. I am now wondering if the complexity of such constrained ...
2k views

### Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
89 views

### A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...
3k views

### Math talk: Theorem about git revision control system?

I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry. For example, the HoTT (Homotopy Type ...
681 views

### Permutations with forbidden subsequences

Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition. Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a ...
288 views