Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
12
votes
0answers
347 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 ...
12
votes
5answers
747 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 ...
5
votes
2answers
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 ...
5
votes
2answers
4k views

Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $...
4
votes
1answer
282 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 ...
2
votes
1answer
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 ...
27
votes
5answers
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 ...
3
votes
0answers
105 views

Delocalization of eigenvectors in Expanding Graphs

Given an adjacency matrix $A$, can we say something about whether the eigenvectors corresponding to its highest (or second-highest) eigenvalues are de-localized ? By de-localization I mean that ...
0
votes
0answers
57 views

Regrouping a collection of sets based on constraint

(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.) Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The ...
5
votes
0answers
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$ ...
4
votes
0answers
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 ...
29
votes
8answers
5k views

What is the minimum number of bits required to store a sudoku puzzle?

Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved ...
8
votes
3answers
290 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 ...
48
votes
11answers
3k views

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a ...
3
votes
1answer
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 ...
4
votes
2answers
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. ...
2
votes
0answers
114 views

What is the most "unbalanced" vector between two given vectors of numbers?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ the product ordering on $\mathbb{R}_+^m$. That is, $\leq_m$ is the partial ordering on $\mathbb{R}...
4
votes
1answer
162 views

Addding edges to spanning tree without destroying planarity

Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ ...
20
votes
0answers
497 views

Model-checking for three-variable logics and restricted structures

Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem $MC(L,C)...
3
votes
2answers
244 views

computing maximal bit density over a FSM

let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("...
1
vote
0answers
118 views

Does this problem have a name? Finding a subset intersecting all subsets of a family

I am pretty sure this problem has a name, or it can be reworded so it does. We are given a set $X$ and a family $\mathcal F$ of subsets of $X$, the problem is to find a subset $B$ such that $B\cap A\...
3
votes
1answer
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 ...
5
votes
2answers
538 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 ...
1
vote
0answers
135 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}}$?
2
votes
0answers
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 ...
-1
votes
1answer
3k views

Minimal perfect hash function from sets of integers to integers

I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$. $m$ will probably be 32 because $|\mathcal{P}(S)| = 2^m$ and i want to use a variable with 32 bits to store this ...
3
votes
1answer
143 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 ...
55
votes
13answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
8
votes
0answers
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 ...
8
votes
1answer
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 ...
12
votes
1answer
2k views

Efficient algorithm for existence of permutation with differences sequence?

This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations. A differences sequence $a_1, ...
2
votes
0answers
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)?
2
votes
1answer
125 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 ...
5
votes
0answers
442 views

lower bound for difference between max cut and min cut

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\}\...
6
votes
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 ...
28
votes
4answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
27
votes
1answer
902 views

Coloring complexity of graphs

Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
14
votes
0answers
312 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\}$, ...
-1
votes
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$ ...
14
votes
4answers
1k views

Throwing Balls into Bins, estimate a lowerbound of its probability

This is not a homework, though it looks like. Any reference is welcome. :-) Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is ...
7
votes
3answers
1k views

Order of drawing colored balls from a bag

We're looking for an upper bound on (or a method to compute) probabilities of the following type: Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag. Then I start ...
38
votes
17answers
4k views

Conjectures implying Four Color Theorem

Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
2
votes
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)$. ...
11
votes
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$. ...
6
votes
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 \...
10
votes
4answers
3k views

The number of cliques in a graph: the Moon and Moser 1965 result

I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
9
votes
1answer
295 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)$ ...
13
votes
3answers
641 views

The Dracula game

Background This question is motivated by a board game called 'Dracula'. In this game there is one vampire and four hunters, the purpose of the hunters is to catch the vampire. The game takes place in ...
31
votes
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 ...

1
3 4
5
6 7
13