All Questions
Tagged with machine-learning co.combinatorics
12
questions
3
votes
0
answers
109
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
- 24.4k
5
votes
0
answers
118
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
- 24.4k
3
votes
0
answers
87
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 24.4k
1
vote
0
answers
161
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.4k
22
votes
4
answers
2k
views
Open problems which might benefit from computational experiments
Question: I wonder what are the open problems , where computational experiments might me helpful? (Setting some bounds, excluding some cases, shaping some expectations ).
Grant program: The context of ...
9
votes
1
answer
785
views
Sufficient condition for linear separability of a boolean function on $n$ variables
This is a cross-post of two recent questions at math.stackexchange without answers: Q1 and Q2.
A boolean function on an $n$-dimensional hypercube is linearly separable when the convex hulls of the ...
- 814
7
votes
2
answers
448
views
Upper bound on VC-dimension of partitioned class
Fix $n,k\in \mathbb{N}_+$.
Let $\mathcal{H}$ be a set of functions from $\mathbb{R}^n$ to $\mathbb{R}$ with finite VC-dimension $d\in \mathbb{N}$. Let $\mathcal{H}_k$ denote the set of maps of the ...
- 362
0
votes
0
answers
77
views
Shattering of a set of binary classifiers
Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$.
Here is what ...
- 143
1
vote
1
answer
546
views
Upper bounding VC dimension of an indicator function class
I would like to upper bound the VC dimension of the function class $ F$ defined as follows:
$$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q ...
- 11
5
votes
1
answer
244
views
Generating function for lattice paths making aribitrary (i,j)-up-right move in one step and fitting rectangular (m,n)?
There is the following beautiful formula (see Qiaochu Yuan excellent blog):
$$ \sum_{\lambda \in Young~diagrams~fitting~rectangle~m~n} q^{Box~count(="area~under~the~curve")~of~\lambda} = \binom{n+m}{...
- 24.4k
0
votes
3
answers
255
views
Clustering on tree
I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...
- 237
1
vote
0
answers
400
views
On proof of Sauer's lemma
Let $X$ be a (possibly infinite) set. We consider a subset $H$ of the set $\{0,1\}^X$ of functions $X\to\{0,1\}$. Given a finite subset $B\subset X$, we denote by $H_B$ the set of restrictions to $B$ ...
user123139