Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

79 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
21 votes
0 answers
425 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
Lviv Scottish Book's user avatar
10 votes
0 answers
183 views

Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
abacaba's user avatar
  • 344
8 votes
0 answers
214 views

A variation of necklace splitting

Our problem is the following: Let $n$ and $k$ be integers. We are given two (unclasped) necklaces, each with $n$ colored stones: a top necklace which has $k$ colors and a bottom necklace which has 2 ...
Sam King's user avatar
8 votes
0 answers
1k 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 ...
WangYao's user avatar
  • 393
7 votes
0 answers
169 views

Szemerédi's regularity lemma for binary operations

Szemerédi's regularity lemma is an approximate structure theorem for all large graphs (symmetric binary relations). There are versions for multicolored graphs and directed graphs. Is there an ...
Richard Stanley's user avatar
7 votes
0 answers
108 views

A question related to the union-closed sets conjecture

Let $f(n)$ denote the maximum possible cardinality of a collection $\mathcal F$ of nonempty sets which is closed under unions ($X,Y\in\mathcal F\implies X\cup Y\in\mathcal F$) and is such that no ...
bof's user avatar
  • 11.5k
5 votes
0 answers
129 views

Exponential bound for very weak sunflowers?

Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them. A family of sets is r-diverse if any $r$ of its members are diverse. Is there for every $r\ge 3$ ...
domotorp's user avatar
  • 18.3k
5 votes
0 answers
171 views

Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
JSE's user avatar
  • 19.1k
5 votes
0 answers
104 views

Minimum number of balanced partitions

For any multiset $x_1,x_2,\ldots,x_{2n}$ of positive real numbers, a partition into two nonempty subsets $(A,B)$ is called "balanced" if $\text{sum}(A)\geq\text{sum}(B)-\max(B)$ and $\text{sum}(B)\geq\...
Karo's user avatar
  • 247
5 votes
0 answers
161 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$....
Zihan Tan's user avatar
  • 151
5 votes
0 answers
234 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 ...
user avatar
5 votes
0 answers
179 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$, ...
Ratio Bound's user avatar
5 votes
0 answers
226 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 ...
Robin Houston's user avatar
4 votes
0 answers
96 views

What properties do graphs avoiding large regular subgraphs have?

Fix a positive integer $r$ and real $\delta \in (0,1)$. Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
Naysh's user avatar
  • 455
4 votes
0 answers
219 views

Weight transfer proof of Turán’s theorem

Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...
Martin Leshko's user avatar
4 votes
0 answers
80 views

Bounding the Betti numbers of Čech complexes in Euclidean space

Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \ge 2$. Then let $C=C(S)$ denote the union of closed balls of radius $1$ centered at points of $S$. For $0 \le j \le d-1$, how large can the ...
Matthew Kahle's user avatar
4 votes
0 answers
158 views

Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?

This is not a concrete question, just some thoughts. The Komlos Conjecture is as follows- There exists an absolute constant $C>0$, such that the following holds: For all $d$ and any set of vectors ...
Sudipta Roy's user avatar
4 votes
0 answers
103 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
Antoine Labelle's user avatar
4 votes
0 answers
93 views

Are extremal tournament matrices always circulant or 'almost circulant'?

Define an antisymmetric 1-x-matrix as an $n\times n$ matrix $M=(m_{ij})$ with $m_{ii}=0$ and $\{m_{ij},m_{ji}\}=\{1,x\}$ for all $1\le i<j\le n$. Call their set $\mathcal A_n$. The setup is as ...
Wolfgang's user avatar
  • 13.2k
4 votes
0 answers
82 views

Cases of equality in Daykin's theorem

Let $A$ and $B$ be sets of subsets of $\{1, \dots, n\}$, and let $A \wedge B = \{a \cap b : a\in A, b\in B\}$, $A\vee B=\{a\cup b: a\in A, b\in B\}$. Then $$ |A \wedge B| |A\vee B| \geq |A||B|, $$ as ...
crestmods's user avatar
  • 141
4 votes
0 answers
114 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 ...
Seva's user avatar
  • 22.8k
3 votes
0 answers
110 views

Minimum number of couples of sets with non-empty intersection in a union closed family

Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element ...
Fabius Wiesner's user avatar
3 votes
0 answers
86 views

Harper's theorem on the general Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is $$ \min_{S\subseteq ...
Or Meir's user avatar
  • 419
3 votes
0 answers
92 views

Minimum number of partitions of a set such that the same pair must occur in a block in at least half of them

For positive integers $k$ and $n$, let ${S} = \{1,\dots,k\ n\}$. Consider $\ell \ge 3$ partitions $P_1,\dots,P_\ell$ of ${S}$, where each $P_i$ splits ${S}$ into $n$ blocks all of size $k$. Question: ...
Arun's user avatar
  • 31
3 votes
0 answers
70 views

Boundary differences in two graphs

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
H A Helfgott's user avatar
  • 19.3k
3 votes
0 answers
108 views

chromatic number of plane using Cairo pentagonal tiling

Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...
Michael Ruxton's user avatar
3 votes
0 answers
101 views

Szemeredi-Trotter bounds when the lines are implicitly described by a point set

Recall: Theorem (Szemeredi-Trotter): Given $n$ distinct points and $\ell$ distinct lines in $\mathbb{R}^2$, the number of point-line incidences is $O(n + \ell + (n \ell)^{2/3})$. Now, instead of $\...
GMB's user avatar
  • 1,379
3 votes
0 answers
106 views

How many positions of a tile can occur in a periodic tiling?

In my recent question about polygonal tilings where tiles can occur in infinitely many positions, both constructions given as solutions are of self-similar nature. This means in particular that there ...
Wolfgang's user avatar
  • 13.2k
3 votes
0 answers
103 views

Rank relation to maximum subpermanent and subdeterminant?

Given a $\pm1$ matrix $M$ of rank $r$ let the largest subdeterminant be $d$ and let the largest subpermanent be $p$. Are there relations/bounds that connect $r$, $d$ and $p$? Are there geometric and ...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
114 views

Generalization of fisher inequality

What upper bounds are known on the size of a family $\mathcal{S}$ of subsets $S_i \subset [N]$ such that: i) each $S_i$ is of size $pk$. ii) for $i \neq j$, $|S_i \cap S_j| \bmod p \in U$, for some ...
jschnei's user avatar
  • 131
3 votes
0 answers
66 views

An extremal problem in directed path systems

The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$: What is the asymptotically maximum $L = L(n)$ such that ...
GMB's user avatar
  • 1,379
3 votes
0 answers
183 views

Matrices with only two different entries and maximal determinant

Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$. I am interested in how big the determinant of such a matrix can be. For this, we define in a ...
Wolfgang's user avatar
  • 13.2k
3 votes
0 answers
132 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 the ...
Seva's user avatar
  • 22.8k
3 votes
0 answers
236 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 ...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
102 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 ...
JeremyKun's user avatar
  • 726
2 votes
0 answers
78 views

A variant of the social golfer problem and the kirkman schoolgirl problem

I came across the following simple question that seems to be open: Let $U$ be a set of $n$ elements. Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $...
SetFamilyStudent's user avatar
2 votes
0 answers
129 views

How many edges can be in an unbalanced bipartite graph of girth $>6$?

Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$. There is a simple counting argument called the Moore Bounds that gives $$|E| = O\...
GMB's user avatar
  • 1,379
2 votes
0 answers
185 views

The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
nonuser's user avatar
  • 237
2 votes
0 answers
87 views

Restricted Erdos-Ko-Rado theorem reference

Consider a family $\mathfrak{F}$ of $k$ element subsets of $\{1,2,..,n\}$, where $n\geq 2k$, such that any two members of $\mathfrak{F}$ have nonempty intersection. The Erdos-Ko-Rado theorem asserts ...
Chris H's user avatar
  • 1,854
2 votes
0 answers
59 views

Is the finite projective plane stable as an extremal set system?

Let $\Sigma$ be a set of $|\Sigma| = n$ subsets of the universe $[n]$, each of size $k$, with the property that any two of these subsets intersect on at most one element. It is easy to see that the ...
GMB's user avatar
  • 1,379
2 votes
0 answers
120 views

Number of distinct rows and columns in a matrix with bounded number of entries

How many distinct rows and columns a real square matrix can have (at least in symmetric case) such that rank of matrix is $r$ and entries: are from $\{-b,-b+1,\dots,0,\dots,b-1,b\}$? are from $\{-b,-...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
99 views

On a random matrix construction

Given a symmetric matrix $M\in\Bbb Z^{n\times n}$ or rank $r$ with absolute value of any entry bound by $2^{b^2-1}-1$ and maximum eigenvalue at most $\lambda$. We consider the set $\mathcal T_b$ of $\...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
58 views

Totally distance non-preserving transformations

JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
83 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 $n\...
Wolfgang's user avatar
  • 13.2k
2 votes
0 answers
95 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 ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
437 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 ...
ASF's user avatar
  • 21
1 vote
0 answers
44 views

How small must partitions be to ensure overlapping blocks?

Consider the set family $F$ of all $t$-element subsets of $[n]$, for some positive integer $n$. Let $P_1$ be a partition of $F$ into $k$ blocks. Let $P_2 \ne P_1$ be another partition of $F$ into $k$ ...
SetFamilyStudent's user avatar
1 vote
0 answers
107 views

Improved conjecture about partitions of the powerset without the empty set

This conjecture is similar to the previously disproved one, but more difficult. For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without the empty set element $\...
Fabius Wiesner's user avatar
1 vote
0 answers
60 views

Lower bound for the minimum of the maximum frequency of an element - with restrictions

Consider a family $\mathcal{F}$ of non-empty sets, with $n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$. It is known that of the $\binom{n}{2}$ ways ...
Fabius Wiesner's user avatar
1 vote
0 answers
95 views

cone structure of complement of hyperplanes

I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes: \begin{cases} (1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\ gy-\sum_{i\in I}x_i+\...
tota's user avatar
  • 585