The tag has no wiki summary.

learn more… | top users | synonyms

7
votes
2answers
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
1answer
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
2answers
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
4answers
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
2answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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 ...