# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

628 questions
Filter by
Sorted by
Tagged with
247 views

### Lemma needed for my machine learning research [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...
765 views

### Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
50 views

### Hardness of Covering Arrays with $v=t=6$

A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the ...
209 views

### Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$. There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$. There are $462! \approx 1.419 × 10^{1032}$ possible ...
353 views

### How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
189 views

### Book Embedding Duality of Graphs

The definition of Book Embedding on Wikipedia: "A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as ...
368 views

### Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
284 views

### Special properties of bipartite expanders

It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. However, I am curious if there are any special properties of ...
5k views

### Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
246 views

### Hereditary Discrepancy

It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets. In general if it is so hopeless ...
140 views

### Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
97 views

### Thresholds for overlapping sets

A common scenario is that one has a well-ordered universe, and one wishes to answer queries of the form "how many elements are at most x?". If one has d elements, then one can pick logd thresholds in ...
749 views

### Additive combinatorics applications in algorithm design

I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if ...
56 views

### Emptiness of complement of subspace arrangement

Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem? P.S.: It seems that this can be ...
312 views

### On the notion of positive rank

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
378 views

### Weird claim of graphclasses about complexity of domination

EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org. ...
114 views

315 views

### Scheduling to maximize idle time

In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due ...
141 views

### Generalization of Beck's theorem

Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of ...
135 views

### What is the standard name for the function which inflates a string by duplicating each of its characters?

Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters. For ...
549 views

### Is there notation for converting a multi-set to a set?

Suppose we have a multi-set $S$. For example, $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is ...
140 views

### Discrepancy of Hadamard type matrix

Let $H$ be $\{-1,+1\}$ Hadamard matrix of size $2$ and $J$ be the same size all $1$ matrix. Let $W$ be $\frac{H+J}{2}$. Is the discrepancy of $W^{\otimes k}$ atmost $\sqrt{k^{-1}}$?
236 views

### Recent insights on algorithms for 1D bin packing

This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
146 views

### Number of different longest common substrings

Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
291 views

### How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE). In other words, a ...
107 views

### Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
220 views

### A curious asymmetry in good characterizations

There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing ...
53 views

### Minimizing a general submodular pseudo boolean function

Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?
126 views

### Weighted furthest point voronoi diagrams

I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that. But I could not find anything on Weighted furthest point voronoi diagrams !! But ...
450 views

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. $$M^+=\max\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\... 0answers 275 views ### Is this graph polynomial known? Can it be efficiently computed? Consider a connected simple graph G with n vertices and m edges. View each edge \ell as a transposition t_{\ell} acting on the set of vertices. [To be more explicit, given an edge \ell ... 0answers 122 views ### General Results for Complicated Constraint Satisfaction Problem Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ... 0answers 317 views ### Sign patterns for Fourier coefficients of Boolean functions Given a sequence of real numbers (a_i), the sign-pattern sequence (s_i) is defined by s_i = + if a_i \geq 0 and s_i = - otherwise. For a boolean function f: \{0,1\}^n \to \{0,1\}, ... 2answers 83 views ### Arrangements of Objects Suppose there are n bins each having k objects. Assume that capacity of each bin is also k. Now we want to rearrange the objects such that each bin contains k objects but this time if x,y ... 0answers 85 views ### Name for the "stronger submodularity" property in cut function Let f:2^V \rightarrow \mathbb{R} be a set function over V that satisfies the following: f(A \cap B) + f(A \cup B) \le f(A) + f(B) f(A \backslash B) + f(B \backslash A) \le f(A) + f(B). ... 0answers 145 views ### Is RAMSEY COLORING in NC? Say that a function f is a RAMSEY COLORING if on unary input n, it returns a complete graph on n vertices with its edges colored red and blue without a monochromatic clique of size 10\log n. ... 0answers 94 views ### Perfect hashing family variation - injectivity on r disjoint sets We denote by [t] the set \{1,2,\ldots,t\}. A (n,k)-perfect hashing family is a set of functions H=\{h_i:[n]\to[k]\} such that for every set S\subset [n], |S|\leq k, there exists some h_S \... 4answers 2k views ### What is simplest polynomial algorithm for PLANARITY? There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ... 2answers 3k views ### Sum of products of all combinations? We are given a list S containing n numbers S=(s_1,\ldots, s_n). Let S \choose k be the set of all possible k-combinations from S (i.e. size k subsets of S). We want to compute the ... 4answers 711 views ### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs Crossposted from MO. Let C be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems that ... 2answers 138 views ### Determining the distribution of results of a simple algorithm Setting Consider repeating the following process on the numbers N=\{1, 2, 3, \ldots, n\}: Pick an integer k \in N, uniformly at random. Pick a subset of k elements from N, uniformly at random.... 0answers 105 views ### What is the smallest deterministic construction of an ordered perfect hashing family? A (n,k)-perfect hashing family is a family of functions H=\{h_i:[n]\to[k]\} such that for every set S\subset [n], |S|\leq k, there exists some h_S \in H such that H_S is injective on S. ... 1answer 296 views ### Random restrictions and the connection to total influence of Boolean functions Say we have a Boolean function f:\{-1,1\}^n\rightarrow \{-1,1\} and we apply \delta-random restriction on f. In addition, say that the decision tree T that computes f shrinks to size O(1) ... 0answers 865 views ### Time-inhomogeneous Markov Chains I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ... 1answer 235 views ### Literature for Generalized Load Balancing i am looking for literature on this kind of problem.$$ \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{...
Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper ...