The tag has no usage guidance.

learn more… | top users | synonyms

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