3
votes
1answer
59 views

Number of edges in graphs having two disjoint cycles of equal length

The question is motivated by this and this two problems. The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the ...
2
votes
3answers
119 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
2
votes
0answers
30 views

Covering the square with “crosses”.

The problem concerns covering the unit square with translates of a specific figure, which I will refer to as a "cross", using as few translates as possible. The difficulty seems to result from the ...
2
votes
1answer
25 views

Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are ...
2
votes
0answers
24 views

Threshold function of the property Sperner set

Someone can to help me in the following problem about the threshold function of the property Sperner set? I don't know where to start. Let $\mathcal{F} \subseteq \mathcal{P}([n])$ be a random ...
2
votes
1answer
92 views

Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $ |f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...
1
vote
0answers
28 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
2
votes
1answer
31 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
2
votes
1answer
151 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
3
votes
1answer
52 views

Minimum boolean lattice containing all poset of fixed size

I need help with the following: What is the minimum $n$ such that the boolean lattice $2^{[n]}$ contains all posets of size $m$? I noticed that it should contain a chain of length $m$, and the ...
1
vote
0answers
63 views

LYM Inequality question

Suppose that $F ⊂ P(n)$ is a set system containing no chain with $k + 1$ sets. Prove that $\sum\limits_{r=1}^n = \frac{|F_{r}|}{n \choose r} ≤ k$, where $F_{i} = F \cap [n]^{(i)}$ for each i . It's ...
1
vote
1answer
66 views

Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
1
vote
1answer
31 views

Balanced independent sets & independent domination number

Let $G=(V,E)$ be a bipartite graph, with partition $V=A \cup B$. Recall that an independent set $I$ of $G$ is a set of vertices sharing no edges. The independent domination number $i(G)$ is defined ...
0
votes
0answers
46 views

Intersecting Set Systems

This a follow up question to an earlier question: "Intersecting set systems and Erdos-Ko-Rado Theorem " that was answered by Sean Eberhad. It asks, what is the largest intersecting family of r-sets ...
5
votes
1answer
112 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
9
votes
3answers
388 views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
1
vote
1answer
56 views

Has this variation of blocking set been studied before?

Given a collection of sets $F$, a set which intersects all sets in the $F$ in at least one element is called a blocking set (or hitting set). The blocking number $τ(F)$ of a family $F$ is the minimum ...
0
votes
0answers
47 views

An extremal combinatorial problem over Finite rings

Let $q$ be an odd number and $g_i = (g_{i1} g_{i2} \dots g_{ir}) \in \Bbb Z_q^r$ a list of vectors with $i\in\{1,\ldots,L\}$. Let each $g_i$ have $0 < k < r$ zero entries. What is the maximum ...
5
votes
1answer
126 views

Show there’s at most $n\choose \left \lfloor\frac{n}{2} \right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that ...
1
vote
1answer
623 views

Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). ...
0
votes
0answers
46 views

Difference Sets

suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
2
votes
1answer
198 views

Maximum number of pairwise intersections

Let $[n]=\{1,2,\ldots,n\}$ and let $S$ consist of subsets of $[n]$ of cardinality $2$. I would like to find the maximum number of pairwise intersections that $k$ distinct elements from $S$ can have. ...
1
vote
1answer
51 views

beads in a string with restrictions

Using the principle of inclusion and exclusion; let $p,q\in \mathbb{N}$, being $p$ odd, there are $pq$ beads of $q$ different colors, with $p$ beads in each color. If the beads of the same colour are ...
0
votes
0answers
32 views

Selecting items to satisfy multiple constraints

I have a problem that goes like this: I need to pick X items from my list of available items. Each item has Y attributes, which are just integers. The distribution of the attributes between items is ...
1
vote
1answer
38 views

Multiples of one number in base-$10$ [duplicate]

How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones? For example, let $n=3$ then, exists al least one number, the ...
3
votes
3answers
300 views

Demonstration using the Pigonhole principle

I was thinking about the following problem: Let $n\in\mathbb N$ be odd. If I have a symmetric matrix in $M_n(\mathbb{N})$, i.e. a square symmetric matrix of size $n$, for which each column and ...
0
votes
1answer
243 views

total number of different mixes

Patient Age Avg Visits / Year <1 year 7.5 1-4 years 3.0 5-14 years 1.8 15-24 years 1.7 25-44 years 2.6 45-64 years ...
0
votes
3answers
67 views

About ascending numbers

I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$ How can I find ...
0
votes
1answer
150 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
0answers
101 views

Problem involving set systems - combinatorics.

The question is as follows: $A \subset \mathbb{P}(X)$ is called a cross-cut if for every $B \subset X$ there exists $A' \in A$ with $B \subset A'$ or $A' \subset B$. Prove that every cross-cut ...
3
votes
1answer
221 views

Intersecting set systems and Erdos-Ko-Rado Theorem

Suppose you have an $n$-element set, where $n$ is finite, and you want to make an intersecting family of $r$-subsets of this set. Each subset has to intersecting each other subset. We may assume $r$ ...
6
votes
2answers
97 views

Two subsets and their union have same color

Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$. Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
0
votes
1answer
111 views

Walks on the Integer Grid

Consider the set of all walks with $2k$-many steps on the integer grid starting from the point $n \in \mathbb{Z}$ and turning back to this specific point. Let each walk is of lenght $\pm 2$ and do not ...
-2
votes
1answer
93 views

question challenge expert math

I have question. this question is need more explain can anyone do if we have $$k_n=a_n+a_{n-1}+a_{n-2}+ \dots+a_1+a_0$$ where $a_n=1$ only $n$ is a multiple of $5$, $0$ otherwise. So $$k_n= ...
0
votes
1answer
68 views

Question in discrete mathematics *

I have question. Can anyone able to explain to me this problem why if we have 5x the generating function $1+x^5+x^{10}+x^{15} + \ldots$ we have 5 is just constant and multiply with $x$ I know that $x$ ...
1
vote
1answer
76 views

question in discrete mathematics

I have questions. Can anyone help me to get the idea or figure out this problem. Find a recurrence relation. If an denote the number of words from the alphabet W={A,B,C} of length n with no two ...
4
votes
1answer
146 views

No induced ordered graph yields large clique/stable set in ordered graph

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
1
vote
1answer
289 views

Ramsey-type result for tournaments

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help. Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
4
votes
0answers
78 views

Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1] For ...
2
votes
0answers
74 views

Does anyone know any specific example of such point set

Does anyone know any specific or explicit example of a set of $256$ points so that no $10$ are the vertices of a convex $10$-gon? Thanks in advance.
2
votes
2answers
117 views

Upper bound for the size of a maximal collection of subsets which, pairwise, have at most one common element

Given a finite set $A$ with $n$ elements, what would be a good upper bound for the size of a largest collection $\mathcal{F}$ of subsets of $A$ which satisfy the following condition: Any two elements ...
14
votes
3answers
1k views

Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.

Let $T(m,n)$ for integers $m,n$ be the least number of integer-sided squares needed to tile an $m\times n$ rectangle. Clearly $T(kx,ky)\leq T(x,y)$. Are there integers $x,y,k\gt 1$, such that ...
3
votes
2answers
352 views

Chess Board and Knights

I can't solve this question. anyone knows how I must solve? You have a 6x3 chess board. How many forms exist to put a Knight in a square and with valid moviments pass in all squares but only one time ...
2
votes
0answers
84 views

Maximum size of a Sperner family containing a set of a given size

Given a set $A$ of $n$ elements and an positive integer $k\le n$, what is the size of the largest Sperner family $\mathcal{F}$ of subsets of $A$ such that $\mathcal{F}$ contains a set $B\subseteq A$ ...
2
votes
0answers
74 views

minimum union of subcubes

Let $B = \{0,1\}^n$ denote the boolean cube containing all $2^n$ binary vectors of size $n$. Let $D_v^s$ be a $d$ dimensional subcube of $B$ where the $d$-coordinates given by $s$ ($s \in [n]^d$) are ...
1
vote
1answer
98 views

How many nodes before k-clique or k-anti-clique?

I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound? I am trying to either find a tight example, or find a better ...
1
vote
0answers
136 views

Estimation for ramsey number $R(3,k)$.

Previously I have shown that for any positive integers $k,l$, and any real number $p\in (0,1)$, ramsey number $R(l,k) \geq n- {n\choose k} p^{{k \choose 2}} - {n\choose l} (1-p)^{{l \choose 2}}$. Now ...
1
vote
1answer
120 views

Upper bound for the number of open disks containing $k$ points in the plane

I hope that you can help me with this. Let P be a set of points in the plane, such that $|P|=n$, what is the maximal number of open disks containing at least $k$ points for some $k$, two discs are ...
1
vote
1answer
219 views

How do I approach this combinatorics problem about composition?

The question is from Bogart's A composition of the integer k into n parts is a list of n positive integers that add to k. How many compositions are there of an integer k into n parts. To ...
2
votes
1answer
236 views

Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$

Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$. For example the permutation ...