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 [extremal-combinatorics]

Extremal combinatorics studies how large or how small a collection of finite objects (numbers, graphs, vectors, sets, etc.) can be, if it has to satisfy certain restrictions.

9
votes
0answers
97 views

Graphs with minimal-size induced subgraphs

I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
0
votes
0answers
56 views

On covering number and real rank

Let $f$ be boolean function, $M_f$ be it communication matrix, $t(f)$ be covering number of $M_f$ and $\chi(f)$ be partition number of $M_f$. We know that there is an $f$ such that $\chi(f)=2^{(\log ...
4
votes
0answers
95 views

How to construct an $(n,m,k)$ ``separating set''?

This problem is probably known under some other name, if anyone has seen it before, a reference will be great. Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary ...
6
votes
0answers
103 views

Constructing a large bit-vector set with the following property

I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property: $$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$ In ...
8
votes
2answers
333 views

A Combinatorial Problem on Extremal Set Theory

Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist? (i) $\forall S\in \mathcal{F}$, $|S|=a$....
1
vote
1answer
92 views

reference request- property of subset of rows in a matrix

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
3
votes
0answers
105 views

On number of disjoint sets with small stack depth in a set of permutations

Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]), What is ...
7
votes
3answers
519 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
2answers
533 views

Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
6
votes
0answers
91 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \...
5
votes
0answers
101 views

What is the smallest deterministic construction of an ordered perfect hashing family?

A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$. ...
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 ...
3
votes
0answers
167 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
242 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])$, ...
5
votes
1answer
196 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 ...
8
votes
2answers
265 views

Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$. If $n=|V|$, then what is the smallest number of $V(H)$? The number is at most $3n/4$: consider a set of disjoint $4$-holes. Can ...