## Finding maximal cardinal independent set given oracle

The problem is given an oracle $$O(G, k)$$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I’m just really stuck after that and was wondering if any hint could be given.

Posted on Categories proxies

## A problem with the greedy approach to finding a maximal matching

Suppose I have an undirected graph with four vertices $$a,b,c,d$$ which are connected as in a simple path from $$a$$ to $$d$$, i.e. the edge set $$\{(a,b), (b,c), (c,d)\}$$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)

Maximal Matching (G, V, E): M = [] While (no more edges can be added)      Select an edge which does not have any vertex in common with edges in M      M.append(e) end while return M 

It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $$(b,c)$$ first, then the you will have a matching that consists only of $$(b,c)$$.

Whereas if you choose $$(a,b)$$ as your starting edge, then the next edge chosen will be $$(c,d)$$ and you have a matching of cardinality 2.

Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.

Posted on Categories proxies

## The optimal asymptotic behavior of the coefficient in the Hardy-Littlewood maximal inequality

It is well-known that for $$f \in L^1(\mathbb{R^n})$$,$$\mu(x \in \mathbb{R^n} | Mf(x) > \lambda) \le \frac{C_n}{\lambda} \int_{\mathbb{R^n}} |f| \mathrm{d\mu}$$, where $$C_n$$ is a constant only depends on $$n$$.

It is easy to see $$C_n \le 2^n$$, but how to determine its optimal asymptotic behavior? For example, does $$C_n$$ bounded in $$n$$? Is $$C_n$$ bounded by polynomial in $$n$$?

## Proving NP completeness of maximal length path

I have this question to answer:

For each node i in an undirected network $$G = (N,E)$$, let $$N(i) = \{j \in N : \{i, j\} \in E\}$$ denote the set of neighbors of node $$i$$ and let $$c_e\geq0$$ denote the length of edge $$e \in E$$. For each node $$i \in N$$, suppose the set $$N(i)$$ is partitioned into two subsets, $$N^+(i)$$ and $$N^-(i)$$ such that $$j \in N^+(i)(j \in N^-(i))$$ is referred to as a positive (negative) neighbor of $$i$$. (Note: Regardless of whether $$j$$ is a positive or negative neighbor of $$i$$, $$i$$ can be either a positive or negative neighbor of j.) Consider the problem of ﬁnding a maximum-length path $$(s =) i(0)–i(1)–···–i(h)(= t)$$ in $$G$$ between two nodes $$s ∈ N$$ and $$t ∈ N$$ subject to the following restriction: For each internal node $$i(k)(k \in\{1,…,h − 1\})$$ on the path, the set $$\{i(k − 1),i(k + 1)\}$$ must contain exactly one positive neighbor and one negative neighbor of $$i(k)$$. Prove NP-completeness of the decision problem and state whether it strongly NP-complete or not.

I wonder about the steps of the proof and whether shall I start from the longest path problem or from another problem instance.

Posted on Categories proxies

## How can I find explicit examples of maximal orders of quaternion algebras that are not isomorphic?

I know that there exist algorithms that will construct maximal orders of a quaternion algebra over, say, $$\mathbb{Q}$$. However, the implemented algorithms that I know of require that you input an order that is not necessarily maximal, which the algorithm then completes. Unfortunately, this does not help if you want examples of orders that are not isomorphic to one another.

The more examples (at least over $$\mathbb{Q}$$, but preferably over other number fields) that I can get, the better, but I would be happy even with a table of some known examples.

## Decision table with maximal number of reducts

I need to create decision table with 4 attributes and 2 decision classes: yes and no. It must have at most 20 objects and maximum number of reducts. I have no clue how to do this.

Posted on Categories shared proxies

## Maximal chains of nested subspaces

I need to answer the following question:

Let $$V_n(q)$$ be $$n$$-dimensional vector space over $$\mathbb {F}_q$$ with $$\mathbb{F}_q$$ fields with $$q$$ elements. How many different maximal chains of nested subspaces of $$V_n(q)$$ are there?

I know what a maximal chain of an ordered set is but have no idea how to connect it with a vector space. I was desperatedly looking for some explanation but didn’t find anything. Any help of you would be very much appreciated!

## Maximal unramified quotient of $E[p]$ for the action of $G_{\mathbb{Q}_p}$

Let $$E$$ be an elliptic curve with good and ordinary reduction at an odd prime $$p$$. Suppose $$E[p]$$ denotes the $$p$$-torsion points of $$E$$ and $$G_{\mathbb{Q}_p} := \text{Gal}(\overline{\mathbb{Q}_p}/\mathbb{Q}_p)$$.

In the article Selmer group and congruences (page 6)’, Greenberg says that one can characterize $$\widetilde{E}[p]$$ as the maximal unramified quotient of $$E[p]$$ for the action of $$G_{\mathbb{Q}_p}$$ where $$\widetilde{E}$$ denotes the reduction of $$E$$ in $$\mathbb{F}_p$$.

This is so because $$p$$ is assumed to be odd and therefore the action of the inertia subgroup of $$G_{\mathbb{Q}_p}$$ on the kernel of the reduction map $$\pi: E[p] \longrightarrow \widetilde{E}[p]$$ is nontrivial.

It will be every helpful if someone can explain how $$p$$ being odd’ is playing a role in proving the non trivial action of the inertia subgroup on the kernel of the reduction map $$\pi$$ ?

## Can a bramble of maximal order be efficiently found from a tree decomposition of minimal width?

Let $$G$$ be a connected graph with vertices $$V(G)$$. A bramble of $$G$$ is a set of connected subgraphs $$H_1,\ldots,H_n$$ such that for each $$i$$ and $$j$$, $$H_i$$ touches $$H_j$$; that is, either $$H_i$$ intersects $$H_j$$ in a vertex, or there is an edge in $$G$$ that connects a vertex of $$H_i$$ to a vertex of $$H_j$$. The order of a bramble is the minimum size of a set $$S\subset V(G)$$ such that $$S\cap H_i$$ is nonempty for all 𝑖.

It was shown by Seymour and Thomas (in “Graph Searching and a Min-Max Theorem for Tree-Width”) that $$G$$ has tree-width at least $$k-1$$ if and only if and only if $$G$$ has a bramble of order at least $$k$$. Suppose we know that a graph has tree-width equal to $$k-1$$. Are there any computational tools out there to find a bramble of order $$k$$? (I am happy to assume that we have an explicit tree decomposition of width $$k-1$$, if this is useful for finding the bramble.)

There are certainly papers that present algorithms for finding such brambles (e.g. “A Branch-and-Price-and-Cut Method for Computing an Optimal Bramble” by Sonuc, Smith and Hicks); I am interested in actual implementations that are available.

## How do the balls maximizing the maximal function depend on their centers?

Let $$\mu$$ be a finite Borel measure on $$\mathbb R^N$$ and let $$f\in L^1(\mu)$$ be a non-negative function. Let $$M_\mu f$$ denote the maximal function of $$f$$ relative to $$\mu$$, i.e. $$(M_\mu f)(x)=0$$ if $$\mu(B(x,r))=0$$ for some $$r>0$$ and $$(M_\mu f)(x) = \sup_{0 otherwise. (Here $$B(x,r)$$ denotes the open ball of radius $$r$$ centered at $$x$$.)

Suppose that $$a>0$$ and $$K\subset \mathbb R^N$$ is a compact such that $$M_\mu f > a$$ on $$K$$. Then for each $$x\in K$$ there exists $$r_x>0$$ such that $$\frac{1}{\mu(B(x,r_x))} \int_{B(x,r_x)}f \, d\mu > a. \tag{1}$$

Question. Is it possible to choose for each $$x\in K$$ the radius $$r_x>0$$ in such a way that (1) holds and the mapping $$x\mapsto r_x$$ is continuous or at least Borel?

This question is inspired by another recent question about Besicovich type covering theorem.