Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms (1)

0
votes
0answers
44 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)\}$ ...
1
vote
1answer
139 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$ ...
0
votes
0answers
45 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)}$ ...
1
vote
1answer
82 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 ...
3
votes
1answer
213 views

The maximum number of induced cycles in a simple directed graph

Is the maximum number of induced circuits in a simple directed graph known? I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly $3^{n/3} + \...
8
votes
1answer
146 views

3-color a cubic graph such that a MIS receives only two colors

According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary ...
2
votes
1answer
164 views

Is there any efficient algorithm for computing all semigroups of order n? [closed]

Is there any efficient algorithm for computing all semigroups of order n? I found the following paper which solves a bit different problem. Veronique Froidure and Jean-Eric Pin, "Algorithms for ...
3
votes
0answers
105 views

Fast Approximation Algorithms for Covering Design

The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ ...
9
votes
0answers
311 views

Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$

An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean ...
1
vote
0answers
58 views

Matching of points in two discrete linear sequences with potentially missing points [closed]

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, the ...
5
votes
2answers
169 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
2
votes
0answers
247 views

Computational Complexity of Ramsey Numbers

What is the computational complexity of computing Ramsey numbers $(n,m) \mapsto R(n,m)$? Is it inside PH? Would it be easier to compute $R$ if PH=P?
1
vote
0answers
50 views

Optimal distribution of integer edge weights

I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. ...
3
votes
2answers
185 views

Generate connected induced subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the ...
1
vote
0answers
87 views

Distance between Sum Sets and Another Point

Let $a_1,\cdots,a_n$ and $\theta$ be positive reals, define $A^{k}$ to be: $A^0=\emptyset;\text{ } A^k=A^{k-1}\cup \{\sum_{i\in S}a_i\mid S\subseteq [n], |S|=k\},$ namely the sum set without ...
3
votes
1answer
115 views

Has this form of “kind-of-dual” homomorphisms been studied?

Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs and let $h:V_2\to V_1$ be a map such that, for every edge $(u_1,v_1)\in E_1$, there is an edge $(u_2,v_2)\in E_2$ such that $h(u_2)=u_1$ and $h(v_2)=...
5
votes
2answers
176 views

Voronoi Diagram of Lines

Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(...
3
votes
0answers
78 views

Embedding distortion under group quotient

The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
7
votes
1answer
442 views

Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
3
votes
1answer
129 views

The complexity of decomposing a bi-stochastic matrix

A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by ...
-3
votes
1answer
82 views

Partitions on Integer Permutations

Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows. $P_1$ is the set of all those permutations which have even ...
0
votes
0answers
75 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
2
votes
0answers
136 views

Reconstructing word / permutation

Let $w = a_0 a_1 \ldots a_{n-1}$ be a word from $\{0,1\}^*$ not all $a_i$ equal to $0$. We compute the number $m= \sum_{i=0}^{n-1} a_i \cdot 2^{n-1-i}$ and then we compute the Lehmer-Permutation $\...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
21
votes
2answers
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 ...
-5
votes
1answer
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. ...
17
votes
4answers
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 ...
13
votes
1answer
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 ...
5
votes
2answers
283 views

Constant in Komlos conjecture

Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\...
9
votes
2answers
291 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
2
votes
0answers
134 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
7
votes
1answer
224 views

Combinatorial discrepancy of the system of all cuts

This is a variant of this previous question. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More ...
-2
votes
1answer
171 views

Finding research problem for PhD(TCS)? [closed]

I am a theoratical computer science PhD student. I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...
5
votes
2answers
218 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
20
votes
1answer
500 views

Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

I encountered the following result during my research. $$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$$ where $m=\omega(\sqrt n)$ and $a_1,\...
10
votes
1answer
205 views

Compute lowest dimensional polytope from a given set of sign vectors

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\...
1
vote
0answers
130 views

Algorithm for multiplying multivariate polynomials in a commutative ring

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different ...
5
votes
1answer
238 views

$d$-regular bipartite expander graph

I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is ...
-2
votes
2answers
191 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 ...
25
votes
1answer
630 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 ...
2
votes
0answers
41 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 ...
0
votes
1answer
204 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 ...
11
votes
0answers
251 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 ...
5
votes
2answers
132 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 ...
9
votes
1answer
328 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 ...
4
votes
1answer
161 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 ...
25
votes
5answers
4k 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
1answer
178 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 ...