Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

0
votes
1answer
125 views

Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
1
vote
2answers
2k views

What's the relation between the dominating set and vertex cover?

I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?
1
vote
2answers
94 views

Monomial decomposition as product of smaller monomials

Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ? For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on. For a monomial in one ...
12
votes
1answer
1k 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, ...
6
votes
2answers
170 views

Difference Sets

Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
2
votes
1answer
164 views

Dual/complement of independence system

An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that: $\emptyset \in \mathcal{I}$, and $I_1 \...
3
votes
0answers
66 views

Estimating the average contiguous sequence length of a balanced boolean function

Given a balanced Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, is there a sampling strategy that needs less than $O(2^n)$ samples to estimate the average length of contiguous sequences of 1's? ...
5
votes
1answer
194 views

Inherent limitation of Switching Lemma for finer lower bounds

The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits. The Switching Lemma claims that we can get a ...
3
votes
1answer
162 views

Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$

I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$. Given $p$, I am looking for a ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
2
votes
0answers
96 views

Optimal additive basis for decomposing/partitioning an integer as a sum of two integers

I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$. A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ ...
3
votes
0answers
171 views

Natural Proofs and methods for polylog depth circuit lower bounds

I have a question about the following question and its answer. Status on circuit lower bounds for polylog-bounded depth circuits In the above question, it is asked about methods to prove lower ...
2
votes
0answers
87 views

Helly's number from biconvex functions [closed]

Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq \...
-9
votes
2answers
270 views

A question on the very essence of “theoretical computer science” [closed]

What is the point of the study? Why would anyone want to just make a career, passion, or otherwise interest or hobby in something that purports itself as theories for computational systems in general? ...
12
votes
1answer
329 views

Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack ...
3
votes
1answer
76 views

Zero Obstructed vertex induced subgraphs

Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties: It has no isolated vertices. It is possible to ...
2
votes
0answers
147 views

Graph has several MST what does it mean combinatorically?

This question is not theoretical, it's about combinatorial meaning. In graph theory there is a notion of complexity of a graph, which is equal to the number of spanning trees in a graph, which ...
1
vote
1answer
363 views

combinatorical embedding

I have a problem with the following statement : Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G What does this mean ? OK in a spanning tree there ...
0
votes
1answer
209 views

Various conjectures which is similar to Log Rank conjecture

Log rank conjecture is one of the most famous open problems in the area of communication compleixty. Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , ...
7
votes
1answer
312 views

Number of edge induced subgraphs with given vertex parity

Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices. Questions How hard is to compute $O$? How hard is to compute the parity of $...
3
votes
0answers
62 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}}...
7
votes
2answers
193 views

Hyperplanes not intersecting points on a cube

Consider the set of points in $\mathbb{R}^n$ with coordinates in $\{-1, 0, 1\}$. Find a hyperplane passing through the origin that contains no points in the set besides the origin. This is simple if ...
8
votes
0answers
188 views

Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)

I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
3
votes
0answers
98 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 ...
12
votes
2answers
1k views

Small graph with gap between chromatic and vector chromatic number?

I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$. ($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
3
votes
2answers
299 views

Generalization of independent set

I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices. How about if you allow no more than $k$ pairs of adjacent vertices? ...
3
votes
0answers
336 views

Streaming Algorithm Lower Bounds by Communication Complexity

I am learning the methods for proving lower bounds on streaming algorithms using communication complexity. My question is about a basic technique to prove lower bounds on streaming models using the ...
1
vote
0answers
115 views

Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

If we want a specific example, then how about the Erdos-Renyi random graph?
0
votes
0answers
70 views

Nonnegative Permanent and Ellipsoidal Method

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. This was based on the Ellipsoidal Method. Finding a Max Cut is the same for Bipartite Graphs as ...
6
votes
1answer
231 views

Canonical labeling of special classes of DAGs

Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known. What are some special classes of DAGs that can be ...
6
votes
0answers
277 views

Bipartite vertex separator

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...
9
votes
1answer
274 views

Increasing the capacity to maximize the min cut

Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time. Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging ...
8
votes
1answer
346 views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
9
votes
1answer
407 views

Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
1
vote
1answer
94 views

PCVRP with prizes reduced over time

Hej guys, I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows: The set of customers does not change over time, but their respective prizes ...
0
votes
0answers
82 views

Bound for the spectral norm of a boolean function [duplicate]

As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$. Is it possible to improve this bound..? Can somebody provide me an example of a Boolean ...
9
votes
2answers
733 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
6
votes
2answers
593 views

Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function. The Fourier expansion of $f$ is $$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers ...
3
votes
1answer
187 views

How can we derive this lower bound of a special cut in a graph?

I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
0
votes
0answers
112 views

Complexity of the packing

Let $(A, \leq)$ be a totally ordered alphabet. The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, ...
10
votes
2answers
2k views

Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
23
votes
5answers
2k views

Good seating arrangements for sequence of meals and tables of size k for a group of people

Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that ...
2
votes
0answers
122 views

Complexity of the standardization

Let $(A, \leq)$ be a totally ordered alphabet. The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an ...
17
votes
1answer
640 views

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$. Define $A_k$ to be the number of permutations ...
2
votes
0answers
376 views

How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied: $x_1 \oplus x_2 \oplus \...
8
votes
1answer
347 views

Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
-5
votes
1answer
2k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
11
votes
4answers
12k views

Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to ...
4
votes
1answer
177 views

Nearly-Eulerian Tours

The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-...
22
votes
0answers
524 views

Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...