Questions related to combinatorics and discrete mathematical structures
15
votes
1answer
243 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$ ...
1
vote
0answers
19 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$ ...
2
votes
0answers
97 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 ...
3
votes
0answers
68 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 ...
-1
votes
0answers
56 views
Finding a winning strategy for toads and frogs [closed]
Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm ...
-7
votes
2answers
79 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? ...
-3
votes
0answers
48 views
finite collection of polygons [closed]
Let $P$ be a finite set of disjoint convex polygons in the plane with all sides of length 1. Assign each polygon edge an arbitrary orientation. Now consider the space $S$ obtained by identifying ...
10
votes
1answer
213 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
59 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 ...
0
votes
0answers
76 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 ...
-4
votes
0answers
77 views
8 queen puzzle and 2057 [migrated]
In 8 queen puzzle, to reduce the search space, we use the incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc, avoiding the slots that are ...
1
vote
1answer
77 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 ...
-1
votes
1answer
76 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$ , ...
6
votes
1answer
139 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 ...
2
votes
0answers
35 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| = ...
7
votes
2answers
124 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 ...
7
votes
0answers
125 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
48 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 delocalized ? By delocalization I mean that every ...
11
votes
2answers
802 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
163 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
128 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
69 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
56 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 ...
5
votes
1answer
119 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 ...
4
votes
0answers
101 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 ...
6
votes
0answers
80 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 ...
7
votes
1answer
137 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.
...
1
vote
0answers
52 views
Generalization of hyperbolicity of graphs
Given a graph G together with the usual shortest-path metric defined on it, dG : V (G) × V (G) -> {0, 1, 2, 3, . . .}, we can associate Gromov hyperbolicity as a measure of tree-likeness. Practically ...
10
votes
1answer
330 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
78 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
70 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 ...
8
votes
2answers
147 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 ...
4
votes
1answer
311 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
142 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
101 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$, ...
8
votes
2answers
385 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
586 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 ...
1
vote
0answers
106 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 ...
16
votes
1answer
320 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 ...
1
vote
0answers
231 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 ...
7
votes
1answer
233 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
272 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 ...
-1
votes
3answers
701 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
104 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 ...
19
votes
0answers
222 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 ...
1
vote
0answers
69 views
Equivalence relations on strongly regular graphs with same parameters
Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter
$(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set?
My motivation is to approach ...
13
votes
3answers
506 views
0-1 Linear Programming: computing the Optimal Formulation
Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
11
votes
1answer
205 views
The state of art for sunflower system
I am interesting in the sunflower system and its applications in computer science.
Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...
2
votes
1answer
122 views
Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?
Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ complete $k_i$-partite graphs, where $p$ is finite (of course) and each vertex appears at most a constant number of ...
1
vote
1answer
113 views
Is there any special property the resulting graph G' has?
Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. That is, each block pair ...
