# Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

152 questions
Filter by
Sorted by
Tagged with
34 views

### The linear embedding complexity of subsets of $0/1$ cube

We say $\pi$ is a subset of the $0/1$ integer points in $t$ dimensions represented by coordinates $(x_1,\dots,x_t)$ of complexity $\log^ct$ if there is an $A$ of $2^{\log^ct}\times2^{\log^ct}$ ...
422 views

### Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...
18 views

### Inequality between union-closed families of sets and corresponding upward-closed families

This question is about an inequality for union-closed families of sets related to Frankl's conjecture and a result by Reimer. It relates the union-closed families and corresponding upward-closed ...
45 views

### Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
48 views

### Schur Complement and depermuting an algorithm for determinant modulo $2$

Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square. Through the determinant ...
28 views

### On a $(k,l)$-monochromatic Hamming distance in $\mathbb F_2$?

A $(k,l)$-monochromatic edit on a matrix $M\in\mathbb F_2^{n\times n}$ is the operation $$M+A$$ where $A\in\mathbb F_2^{n\times n}$ is of rank $1$ and number of $1$'s in $A$ is $kl$ and there are $l$ ...
122 views

### Maximum number of subsets in which people co-exist with their friends

Let $P = \{1,\dots,p\}$ be a set of people. Consider partitioning $P$ into two disjoint sets, $A$ (of cardinality $a$) and $A^c = P-A$. Let us index $A$ as $A = \{A_1,\dots,A_a\}$. Each person in $A$ ...
75 views

### Good source for understanding shifting techniques in combinatorics

There are many theorems in extremal combinatorics (e.g. the Erdos-Ko-Rado theorem, the Kruskal-Katona theorem) that can be proved via "shifting" arguments. See for example the following ...
171 views

214 views

### Permutation function based on subsets

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$ in $\sigma$ ...
145 views

### Minimum number of independent pairs in a matroid

Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$...
108 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$ ...
141 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 ...
92 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 ...
62 views

### Computation of cyclic van der Waerden numbers

Van der Waerden's theorem gives us a finite number $W(k,r)$ defined as the smallest positive integer $N$ such that for any $n\geq N$, any $r$-coloring of $[n]=\{1,\dots,n\}$ admits a monochromatic $k$-...
66 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 ...
172 views

### Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
82 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 ...
85 views

### Schur triples question

So I've been reading through On the number of monochromatic Schur triples by Datrovsky on finding the minimal number of Schur triples. This means you're trying to 2-colour the set of the smallest n ...
246 views

For $n\ge 1$ we write $[n]$ to denote the set $\{0,1,\ldots,n-1\}$. Let $2^{[n]}$ be the set of all functions from $[n]$ to $\{0,1\}$. Let $\mathcal{F}$ and $\mathcal{G}$ be two nonempty subsets of $2^... 0answers 47 views ### 4-cycles vs eigenvalue information on quasi-random graphs My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ... 1answer 52 views ### Maximal families of equal length intervals consist of equilateral triangles My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post. Let$\ n\ $be a ... 1answer 70 views ### What is the minimal possible size of a subset of this semigroup satisfying the following conditions? Suppose$A$is some set. Let's define a pair semigroup over$A$as$P[A] = (A\times A \cup \{0\}, \circ)$, where the$\circ$operation is defined by the following two identities:$\forall a \in P[A]$... 0answers 45 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\... 1answer 152 views ### Complementing the red and blue boolean cube? Given a boolean 0/1 cube in n dimensions with 2^{n-1} red and 2^{n-1} blue points can we complement the cube (blue becomes red and vice versa) in \operatorname{poly}(n) transformations? ... 0answers 36 views ### Partition complexity measure of the boolean cube? Given n points p_1,\dots,p_n in \{0,1\}^d my goal is to find m index sets \mathcal I_1,\dots,\mathcal I_m on the condition that each index set is a subset of \{1,\dots,n\} on the ... 0answers 81 views ### Maximum number of ways of splitting a set of points with an hyperplane Given a set S of n points in \mathbb{R}^d, let D_S be the set \{\mathbf{v}=|\mathbf{u}-\mathbf{u'}|: \mathbf{u},\mathbf{u'}\in S\} (where \forall i=1,2,\ldots, d, \mathbf{v}_i=|\mathbf{u}... 0answers 182 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 ... 0answers 20 views ### Do small subsets of S_n subgroups cover almost all permutation configurations of S_n? Given integer m\in[1,n] fix a set \mathcal T of permutations in S_n. Then there are subgroups G_1,\dots,G_m of S_n so that \mathcal T is covered by cosets of G_1,\dots,G_m. For ... 0answers 91 views ### Are almost all permutation configurations from S_n covered by small subsets subgroups of S_n? Given integer m\in[1,n] fix a set \mathcal T of permutations in S_n. Then there are subgroups G_1,\dots,G_m of S_n so that \mathcal T is covered by cosets of G_1,\dots,G_m. Do we have ... 4answers 1k views ### Dividing a cake between n-1, n, or n+1 guests A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be n-1, n, or n+1. What is the minimal number f(n) of pieces the cake ... 2answers 792 views ### Cardinality of certain subsets in vector spaces over finite fields Assume that you have an n-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and F is a subset of this vector space which contains m ... 0answers 59 views ### Polytopes that can be efficiently described and efficiently covered by cubes or simplices? Is there a bounded convex polytope \mathcal P\subseteq\mathbb R^n with m vertices, whose vertex vectors span \mathbb R^n (so m is \Omega(n)) and just O(poly(\log n)) half-plane ... 0answers 63 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 ... 0answers 139 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 ... 1answer 225 views ### An inequality for rearrangement-style sums The following is a holdover from my math contest days that I never got around to solve. We will use the notation \left[ k\right] for the set \left\{ 1,2,\ldots,k\right\} whenever k is a ... 1answer 379 views ### A proper definition of connectivity for hypergraphs For usual graphs on n vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has n-1 edges. I would like to know whether ... 1answer 107 views ### The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles Let c(n,k) be the least integer such that if G is a simple graph on n vertices with n + c(n,k) - 1 edges then G has k edge-disjoint cycles. Clearly, c(n, 1) = 1 and it not very hard to ... 0answers 88 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\... 0answers 96 views ### Number of b-separated Sidon sets with pairwise difference set intersection bounds Given two integers integers 0<b<p and a real \alpha\in(0,1) call a set of m integers a_1<\dots<a_m in the interval (p^\alpha,p-p^\alpha) to be b-separated Sidon if: a_i-a_j\... 2answers 358 views ### An extremal combinatorics problem Given two integers integers 0<b<p and a real \alpha\in(0,1) what is the largest m we have such that in the interval (p^\alpha,p-p^\alpha) there are m integers a_1<\dots<a_m ... 0answers 50 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 ... 1answer 119 views ### Distinguishing points by sets of given size The problem is: Given a finite set X with size x and let B denote a family of k-element subsets of X, called blocks. What is the smallest possible number n of blocks such that every ... 0answers 89 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 ... 0answers 375 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, ... 2answers 161 views ### Extremal density of a graph without a non-backtracking 2k-cycle The current best bound for the maximum possible density of an n-node graph with girth (shortest cycle length) >2k is of the form$$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$while the ... 1answer 261 views ### A generalization of Erdős-Ko-Rado theorem Is there any result known about the following generalization of the Erdős-Ko-Rado theorem? Let$n, k, r, s$be positive integers. We call a family$\mathcal{F}$of$k$-element subsets of$\{1,\ldots, ...
Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements ...
Let $\mathcal{F} \subseteq \binom{[n]}{4}$ be a collection of size-4 subsets of $\{1,\ldots,n\}$, i.e., a 4-uniform set family. Let $\mathcal{F'}$ be the collection of size-3 sets for which a ...