Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
677
questions
2
votes
1
answer
112
views
NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part
Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
11
votes
3
answers
823
views
Applications of sunflower lemma in theoretical computer science
In one lecture by Kewen Wu who is one of the authors of paper
Improved bounds for the sunflower lemma,
it is said that the sunflower lemma can be applied to many fields like
circuit lower bounds
...
2
votes
2
answers
141
views
On the coloring number of small graphs with small cliques
Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i....
0
votes
1
answer
55
views
weights in low density codes
Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
15
votes
5
answers
15k
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 ...
1
vote
1
answer
87
views
Existence of graphs of every order related to Barnette’s conjecture
Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
23
votes
2
answers
841
views
Are shift-chains two-colorable?
For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.
For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.
A $k$-uniform hypergraph ${\...
6
votes
1
answer
295
views
Re-packing of integers into fixed-size bins
We are given a constant $B \geq 3$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$,
and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.
An ...
4
votes
1
answer
282
views
How tight is the XOR lemma?
The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
3
votes
1
answer
221
views
Dual to hypercontractive inequality
Recall the hypercontractive inequality:
Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$
In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the ...
-1
votes
1
answer
76
views
Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]
I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems.
As someone who is somewhat unfamiliar with the language of ...
25
votes
1
answer
822
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 ...
4
votes
2
answers
441
views
Colouring achieving simple discrepancy bound?
Given a hypergraph $H$ with $n$ vertices and $m$ edges,
one of the simplest inequalities on the discrepancy of $H$ is
$\text{disc}(H) \le \sqrt{2n \ln (2m)}$.
This is usually proved by mixing ...
2
votes
0
answers
150
views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
1
vote
0
answers
118
views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
8
votes
1
answer
568
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.
...
6
votes
1
answer
275
views
The asymptotic behavior of a recurrence related to stable matchings
I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:
$$a_1 = 1, a_2 = 2$$
$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$
Apparently, Knuth was able to prove that ...
2
votes
1
answer
87
views
Placing color boxes on a colored image such that color consistency is maximized
I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.
Given an image with black background that contains blobs whose ...
0
votes
0
answers
114
views
Lower bound for permutation generator
I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections.
Given $n$ inputs numbered $1 ......
4
votes
1
answer
299
views
Which (almost) balanced Boolean function has smallest "total" influence
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
1
vote
1
answer
121
views
How to play the following game? (placing balls into bins)
Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$.
The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...
3
votes
1
answer
181
views
Mutually exclusive replacement paths, an existing problem?
A replacement path is a simple path allocated to an edge $e \in G$
that connects the endpoints of $e$ in $G \setminus \{e\}$.
The problem
An undirected graph $G$ is given and the task is to allocate ...
4
votes
2
answers
234
views
Compactness of domino tilings
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
12
votes
0
answers
307
views
Reference request: exponential growth rates of subsequence-closed languages are integers
This question is migrated from MathOverflow, where it did not receive any answers a year ago.
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
3
votes
0
answers
45
views
Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
4
votes
0
answers
82
views
Optimal scheduling with delay constraints
Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-...
8
votes
3
answers
2k
views
Cubic graphs and hamiltonian paths
I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you
12
votes
3
answers
928
views
Edge-partitioning cubic graphs into claws and paths
Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine.
Input: a cubic graph $G=(V,E)$
Question: is there a partition of $E$ into $E_1, E_2, \...
4
votes
0
answers
90
views
Complexity of counting Wang tiles
Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
13
votes
4
answers
4k
views
LP relaxation of independent set
I've tried the following LP relaxation of maximum independent set
$$\max \sum_i x_i$$
$$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$$
$$x_i\ge 0$$
I get $1/2$ for every variable for every cubic ...
1
vote
0
answers
136
views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
70
votes
5
answers
6k
views
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
4
votes
1
answer
143
views
Stable order on binary strings
I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the ...
0
votes
1
answer
186
views
Subset Sum Problem and hard looking instances that are not really hard
I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
4
votes
1
answer
138
views
Applications of Christol theorem
I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
1
vote
1
answer
89
views
Pulling a graph across a partition
I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
10
votes
0
answers
290
views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
2
votes
0
answers
149
views
Smallest disjoint union chain containing a sequence of sets
Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element.
A family $\...
3
votes
0
answers
86
views
Linear optimization over intersection of totally unimodular matrices
I am currently dealing with a problem of the following form
\begin{alignat}{2}
&\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\
&\text{sub to} \hspace{0.05in}&&...
11
votes
1
answer
514
views
Number of equivalence classes in regular languages as a function of DFA size
This question is related to a recent
question
by Janoma.
Background
In constraint programming, a regular global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the
...
8
votes
2
answers
2k
views
Faster pseudo-polynomial time algorithms for PARTITION
I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
4
votes
1
answer
133
views
If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$
I'm searching for a reference for the following property:
Fact. Let $u, v \in A^*$. Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v = w^c$. There are unique words $z, z'$ such ...
1
vote
0
answers
113
views
Growth of random square lattice trees
Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
11
votes
1
answer
895
views
A simple(?) funny combinatorial problem!
Let we fix $0<E<1$ and an integer $t>0$.
for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$
$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \...
6
votes
1
answer
134
views
Average-case analogue of Small-bias Spaces
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-...
4
votes
1
answer
184
views
Probability of a $k$-path in a random graph
Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
27
votes
1
answer
727
views
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
8
votes
3
answers
639
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 $\...
1
vote
1
answer
230
views
Total flow using minimum number of edges on a bipartite network
If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
23
votes
3
answers
1k
views
Representing OR with polynomials
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\...