The extremal-combinatorics tag has no wiki summary.

**7**

votes

**2**answers

102 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

307 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

245 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 ...

**0**

votes

**1**answer

78 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

256 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 ...

**13**

votes

**0**answers

535 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

101 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 ...

**1**

vote

**1**answer

108 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 ...

**5**

votes

**1**answer

215 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 ...

**0**

votes

**2**answers

452 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

142 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

234 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

366 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 ...

**1**

vote

**0**answers

72 views

### What are the minimal numbers of $(2\ 2)$-tetrahedra?

This time my question is related to Ramsey number $R(4\ 4; 3) = 13$.
DEFINITIONS: Functions $c : \binom X3\rightarrow \{0\ 1\}$ are called 2-colorings of triangles in ...

**4**

votes

**2**answers

110 views

### $2$-colorings of triangles, resulting in $(2\ 2)$-colorings of all tetrahedra

DEFINITIONS: Functions $c : \binom X3\rightarrow \{0\ 1\}$ are called 2-colorings of triangles in $X$. The $4$-element subsets $A\subseteq X$ are ...

**3**

votes

**0**answers

420 views

### The state of art of the sunflower lemma

I am interesting in the sunflower system and its applications in computer science.
Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...

**34**

votes

**0**answers

720 views

### Intersecting Family of Triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let ...

**1**

vote

**0**answers

70 views

### min max intersections of finte sets

Let $X=\{1,2,\cdots,n\}$ and $\mathcal{F} \subset 2^X$ so that $\mathcal{F}$ contains sets of given cardinality $k_1,k_2,\cdots, k_N$
(here $|\mathcal{F}| = N)$. Let $\delta(\mathcal{F})$ be the ...

**2**

votes

**1**answer

378 views

### Popular elements in cross-intersecting families

Let $\mathcal{T}$ and $\mathcal{S}$ be two families of subsets of $[n]$ such that for all $T_i\in \mathcal{T}$ and $S_j\in \mathcal{S}$,
$|T_i \cap S_j| \neq\emptyset$
$|T_i| , |S_j| \leq t = ...

**1**

vote

**0**answers

249 views

### An Pure intriguing counting problem of index sets

Hi Guys. The problem here seems like a homework, but I think that it is not that easy.It comes from a theorem I recently proved.The content of the theorem is not important, the issue is that I have no ...

**1**

vote

**1**answer

203 views

### Lower bound of the size of a collection of subsets with a intersecting property

The following question is a open question related to coding theory : What is the maximal size of a collection of $(\frac{n}{2} + 1)$-elements subsets of an n-element set such that each pair of subsets ...

**1**

vote

**2**answers

201 views

### small sums of entries in submatrices - strange phenomenon

Suppose that $x \in \mathbb{R}^{n}$ is a vector of small positive fractions, i.e. $x_{i} \approx \frac{1}{n}$. The exact values are unknown. I form the matrix $M=diag(x)-\frac{xx^{T}}{2}$ which is a ...

**6**

votes

**1**answer

303 views

### Upper bound for the size of a $k$-uniform $s$-wise $t$-intersecting set system

Given integers $n \geq k \geq t \geq 1$ and an integer $s$, let $m(n,k,s,t)$ denote the maximum size of a family $\mathcal F$ of $k$-subsets of $[n]$, i.e. $\mathcal F \subseteq \binom{[n]}{k}$, such ...