The extremal-combinatorics tag has no usage guidance.

**3**

votes

**4**answers

213 views

### How small can a set system containing a large subset of every set be?

Fix $1>c>0$. Consider the set $[n]=\{1,2,\ldots,n\}$ and the set of all subsets of this set which we'll denote as $2^{[n]}$. Let $S \subseteq 2^{[n]}$ be a set system such that for every ...

**10**

votes

**2**answers

275 views

### Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?
Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = ...

**0**

votes

**0**answers

133 views

### Shortest distance on a combinatorial chess board

Consider a random $n\times n$ combinatorial $0/1$ square matrix over field $\Bbb F$ of rank $r$ with every row distinct and every column distinct as a chess board.
Definition of combinatorial ...

**0**

votes

**0**answers

25 views

### A class of unimodular parametrization

Is there a parametrization of set of matrices $\mathcal M\subseteq\Bbb Z[x_1,\dots,x_{m}]^{n\times n}$ such that $\forall f:\{-1,+1\}^{m}\rightarrow\{-1,+1\}$ $\exists M\in\mathcal M$ such that ...

**0**

votes

**0**answers

49 views

### An extremal combinatorics problem

What is the minimum rank $r$ of an $n\times n$ square positive integer matrix such that sum of entries of every $\sqrt r\times\sqrt r$ submatrix is distinct and such that difference between minimum ...

**2**

votes

**0**answers

75 views

### Kruskal-Katona for multisets?

Following Fedor Petrov's remarks, here is a "set-theoretic version" of the
question I asked a while ago.
For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite)
multisets with ...

**5**

votes

**0**answers

199 views

### A combinatorial problem

What is the largest $m\times m$ $0/1$ matrix of real rank $n$ with every square submatrix sized at least ${n^{\gamma}}\times{n^{\gamma}}$ distinct for some fixed $\gamma>0$?
Upper Bounds: Number ...

**2**

votes

**1**answer

118 views

### Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem
(see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...

**4**

votes

**0**answers

95 views

### A $0/1$ matrix problem

What is the largest $m\times m$ $0/1$ square matrix of rank $2n$ over $\Bbb R$ we can have such that every submatrix sized at least $n\times n$ has rank at least $\sqrt{n}$?

**3**

votes

**0**answers

163 views

### Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time.
(1) Is there any ...

**27**

votes

**7**answers

1k views

### List of proofs where existence through probabilistic method has not been constructivised

Probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object. What are some of the most important objects for which we can show existence but ...

**4**

votes

**0**answers

76 views

### Kruskal-Katona for homocyclic groups?

I need a version of the Kruskal-Katona theorem (better still, of the Lovasz "approximate" version thereof) for the elementary abelian / homocyclic groups, in the following spirit:
What is the ...

**6**

votes

**2**answers

262 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**6**

votes

**1**answer

197 views

### Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...

**2**

votes

**1**answer

117 views

### Combinatorics-the maximum number of subsets with a given property

Let $X$ be a set with $n$ elements. I would like to know the maximum number of subsets of $X$ such that the number of elements in the symmetric difference between any two of these subsets is at most ...

**3**

votes

**0**answers

61 views

### What is the maximal number of partitions with this maximal intersection property?

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...

**12**

votes

**2**answers

306 views

### What is the maximum size of a set system where the intersection of any two incomparable members is not in the set?

Let the set $\mathcal{F}$ consist of subsets of $[n]$. Suppose that for any incomparable $A$ and $B$ in $\mathcal{F}$, we have $A \cap B \notin \mathcal{F}$. What is the largest possible size of ...

**16**

votes

**1**answer

258 views

### Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others

What are known estimates for maximal $M$ for which their exists subsets $A_1,\dots,A_M$ in $\{1,\dots,n\}$ such that there do not exist different indexes $i,j,k$ for which $A_i\subset A_j\cup A_k$?
...

**0**

votes

**2**answers

350 views

### Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...

**3**

votes

**1**answer

201 views

### Largest symmetric matrix given rank

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.
What is minimum ...

**0**

votes

**0**answers

69 views

### Minimum rank of certain matrices

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in ...

**2**

votes

**0**answers

64 views

### Euclidean minimum spanning trees intersecting each unit square

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an ...

**34**

votes

**2**answers

1k views

### Random sequence of integers in $\{1, 2, \dots, n \}$ which is “everywhere probably increasing” - how long can it be?

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r ...

**3**

votes

**1**answer

120 views

### Minimal family of k-sets containing all t-sets

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member ...

**3**

votes

**2**answers

224 views

### Number of subsum of a given set of integers

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural:
Given n integers $(e_i)$ chosen ...

**3**

votes

**1**answer

239 views

### Rank changes with matrix edits

Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric).
Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix.
Case $1$: $M+W\in\{0,1\}^{n\times n}$.
Could ...

**1**

vote

**1**answer

202 views

### Probabilistic statement on matrix ranks

Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.
Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.
Does
...

**2**

votes

**0**answers

88 views

### On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...

**6**

votes

**1**answer

117 views

### Measuring how closely a missing projective plane can be approached by an equivalent structure

It is well known that for a number of structures, their existence is equivalent to the existence of a projective plane for a given order. Some of them depend on more than one parameters, which means ...

**5**

votes

**0**answers

106 views

### Families of Sets with Two Intersection Numbers

Let $k$ and $n$ be natural numbers. Let $I$ be a set of natural numbers. Let $\mathcal{F}$ be a family of $k$-element subsets of $\{ 1, \ldots, n\}$ such that $A, B \in \mathcal{F}$, $A \neq B$, ...

**12**

votes

**1**answer

790 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...

**13**

votes

**1**answer

403 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**2**

votes

**0**answers

169 views

### combinatorial rectangles

Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.
Is there ...

**2**

votes

**2**answers

166 views

### Choosing subsets to cover larger sets

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ ...

**4**

votes

**2**answers

150 views

### open question on intersecting rectangles - reference request

In the now-inactive (and very nice) "Tricki" website that describes various proof techniques, there is an article (written I think by Timothy Gowers) that describes the following Ramsey-type problem:
...

**7**

votes

**2**answers

128 views

### Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take ...

**13**

votes

**1**answer

472 views

### A method for making a graph bipartite

Given any graph $G$, can we find a bipartite subgraph of $G$ with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$) by sequentially deleting the edge belonging to the most number of odd ...

**5**

votes

**2**answers

263 views

### A bound on a set

Let $x_1,\cdots , x_n$ be a sequence of real number such that $x_i\geq 1$ for all $1\leq i\leq n$, $S=\{\alpha_1x_1+\cdots +\alpha_nx_n | \alpha_i\in\{0,+1,-1\}\}$ and $I=[a,b)$ be a Interval with ...

**12**

votes

**2**answers

315 views

### Set system with different differences

What is the maximal number of sets in a set system $\mathcal{A}$ of subsets of an $n$ element set such that for every $i \neq j $ and $A_i,A_j \in \mathcal{A}$ the difference $A_i \setminus A_j$ is ...

**0**

votes

**1**answer

110 views

### Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...

**4**

votes

**3**answers

461 views

### Number of binary vectors of a given Hamming weight in a subspace of the Hypercube

Let $n$ be a natural number.
Let $U \subseteq \mathbb{F}_2^n$ be a linear subspace of dimension $k$.
What is the maximum number of vectors in $U$ of Hamming weight $\ell$?
The case I am specifically ...

**17**

votes

**0**answers

886 views

### What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...

**2**

votes

**1**answer

139 views

### Hitting sets (aka covers aka transversals) of Steiner triple systems

Does there exist a constant $c$ so that the lines of every Steiner
triple system on $v$ points can be covered by $cv$ points?
That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...

**0**

votes

**1**answer

118 views

### 2-neighborhood of a simplex

Let $\Delta$ be an $n-1$-simplex in ${\mathbb R}^{n-1}$. For each vertex $v$ of $\Delta$ let $H_v$ be the hyperplane through $v$ and parallel to the opposite facet. By 2-neighborhood of a simplex I ...

**4**

votes

**1**answer

298 views

### Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...

**16**

votes

**1**answer

660 views

### Infinite desert with waterpoints

UPDATE: I created a simple web-application, that allows the user to move waterpoints around, then automatically calculates a maximum set of interior-disjoint squares between the points (the algorithm ...

**0**

votes

**2**answers

468 views

### An extremal combinatorics problem over Finite Rings

Cross Posting from: http://math.stackexchange.com/questions/462016/a-combinatorics-problem-over-finite-rings
Consider the set $S$ of all non-zero vectors over $\Bbb Z_{q}$ of length $r$ whose ...

**5**

votes

**0**answers

167 views

### Diameter of subset sum graph

We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...

**5**

votes

**4**answers

304 views

### Better bounds for exact-intersection Erdős–Ko–Rado system?

What is the largest possible number of subsets of a $4n$-element set $X$, such that each subset contains precisely $2n$ elements, and such that each of the pairwise intersections of the subsets has ...

**9**

votes

**2**answers

434 views

### Largest number of k-arithmetic progressions without a (k+1)-arithmetic progression

Suppose $A \subseteq \{1,\dots,n\}$ does not contain any arithmetic progressions of length $k+1$. What is the largest number of $k$-term arithmetic progressions that $A$ can have? (one may also wish ...