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

10
votes
0answers
283 views

A bijection between ordered lambda terms and rooted planar maps?

Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{...
2
votes
1answer
96 views

Upper bound to number of closed itemsets

Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper ...
8
votes
1answer
191 views

Multidimensional arithmetic progression variant

For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e. $Q(\vec{d} = \{...
6
votes
3answers
197 views

Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

Consider the set of $n^2 - n$ pairs $\{(i, j)\ |\ i \neq j \leq n\}$. Call a partition $(P_1,\ldots,P_r)$ of this set valid if for each $P_t$, the sets $\{i\ |\ \exists k: (i,k) \in P_t\}$ and $\{j\...
0
votes
0answers
136 views

Edges in a graph with girth greater than 4

According to the following paper by Füredi, the maximum number of edges for a graph with $n$ vertices is upper bounded by $O(n^{\frac{3}{2}})$, where the leading co-efficient of the term $n^{\frac{3}{...
1
vote
1answer
171 views

More questions about permutations

I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically. the skew-...
5
votes
0answers
93 views

Upper bound on Euler characteristic of downward closed family

(Definition: $\mathcal{F}$ is called downward closed if for any $A \in \mathcal{F}$ and $B \subseteq A$ it holds that $B \in \mathcal{F}.$) Let $\mathcal{F}$ be a downward closed family of subsets of ...
2
votes
1answer
164 views

Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
16
votes
0answers
328 views

Sylver Coinage Game

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the loser....
1
vote
0answers
86 views

Restoring symmetry in certain combinatorial bijections?

I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an $n$...
2
votes
0answers
123 views

Existence of bijective proofs involving Yamanouchi words?

The following notion comes from algebraic combinatorics and might have some connections to language/permutation theory. Fix an integer $k$. Let us call a $k$-Yamanouchi word a sequence $u$ of integers ...
2
votes
1answer
305 views

Upperbound the order of P3-free partition of P4-free graphs

A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free ...
7
votes
3answers
209 views

On the size of P4-transversals of graphs

A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices. ...
1
vote
1answer
255 views

Is there an analogy of a vertex separator for hypergraphs?

Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs. Is there some survey or book or lecture notes about ...
23
votes
3answers
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\...
8
votes
1answer
557 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
21
votes
2answers
914 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
5
votes
1answer
235 views

Worst case ratio between minimum clique cover and maximum independent set

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
3
votes
0answers
168 views

Building a “balanced” universal set

A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
4
votes
0answers
97 views

Constructing a small (n,k)-Covering Matrices family

Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$. We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {...
6
votes
1answer
249 views

Constructing a k-perfect permutations family

I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, ...
1
vote
0answers
82 views

Upper bound on the number of vertex-transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?
26
votes
1answer
580 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 ...
3
votes
0answers
113 views

Concentration of Stationary Distribution on Random Directed Graphs

We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
9
votes
0answers
120 views

Computing weighted sums of binomial coefficients

This question is a reformulation of Complexity for computing weighted number of paths on integer lattice Is there any way to compute in $o(n^2)$ all $n$ sums $\sum_{0\leq i \leq j} a_i\binom{j}{i}$ ...
3
votes
0answers
139 views

An identity about the Majority function?

Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \...
1
vote
0answers
91 views

Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

Definitions: Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $...
0
votes
1answer
124 views

Counting subsets with large sum

Suppose that you have a multiset of positive integers $I$. $I$ is not given, but it is known that the sum over all elements of $I$ = $k$. (e.g. if $I$={2,5,7} then k=14 is given, but I is unknown). ...
17
votes
3answers
8k views

Counting the Number of Simple Paths in Undirected Graph

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths. Recall that a simple path is a path with no ...
3
votes
1answer
578 views

Subset of a bipartite graph with maximal number of minimal unmatched vertices

Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all $(...
1
vote
0answers
92 views

Complexity for computing weighted number of paths on integer lattice

Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. We wish to compute the value of all upper and rightmost cells $...
2
votes
2answers
128 views

Polynomial time construction of families of pairwise nonhomomorphic graphs

Is it true that for all $n$ there are $n$ pairwise nonhomomorphic graphs with $poly(n)$ vertices? Is there a polynomial time algorithm for constructing such families of graphs?
2
votes
1answer
161 views

Dividing users with certain files into 2 equal groups

I am framing a particular combinatorial question using users and files for better understanding. Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, u_{...
5
votes
1answer
198 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
0
votes
0answers
53 views

Different estimators for uniform convergence of means/averages to expectations

In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the ...
2
votes
0answers
101 views

Geometry on a space of polynomial functions

I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references. Let $P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow \...
5
votes
0answers
182 views

Lemma about intersecting sets

I use the following Lemma and I wonder whether it is known in literature. If you look at the proof it feels like it should be known from combinatorics or extremal graph theory. Lemma. Let $A$ be an $...
7
votes
1answer
201 views

Maintain mex with efficient union

Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations: Given $S[A],$ calculate minimal ...
6
votes
0answers
173 views

Local Hamiltonian and combinatorial search problems

I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...
4
votes
1answer
269 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 ...
3
votes
1answer
156 views

Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

This question was originally posted on mathoverflow. Having obtained no answers after one month, I've decided to cross-post it here. Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n =...
7
votes
1answer
280 views

Erdos conjecture, number of cliques, Turan`s graph

Erdos&Stone conjectured in 1946-08 that there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$ whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's $T(|V|,k)$, i.e., $|E|= 1+\lfloor {(k-1)|...
-1
votes
1answer
144 views

Representation suitable for reconstruction of a tree with bounded degree

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
4
votes
0answers
82 views

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
14
votes
1answer
422 views

Beigel-Tarui transformation of ACC cricuits

I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf One of the key lemmas is a ...
17
votes
0answers
720 views

Tiling a rectangle with the fewest squares

Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares. Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best ...
11
votes
2answers
3k views

Find all pairs of values that are close under Hamming distance

I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid. ...
6
votes
1answer
244 views

correlation in an almost independent set of random variables

Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that ...
-1
votes
2answers
413 views

Intersection between sets

Assume that we have $p$ sets, with given sizes: $m_1,m_2,...,m_p$. The (distinct) elements in each set are taken from $N$ elements (where $m_1,m_2,...,m_p \le N$). A combination is defined as an ...
6
votes
2answers
158 views

Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points. Let $D$ be the distance matrix between ...