In this short note, we show two NP-completeness results regarding the
\emph{simultaneous representation problem}, introduced by Lubiw and Jampani.
The simultaneous representation problem for a given class of intersection
graphs asks if some $k$ graphs can be represented so that every vertex is
represented by the same interval in each representation. We prove that it is
NP-complete to decide this for the class of interval and circular-arc graphs in
the case when $k$ is a part of the input and graphs are not in a sunflower
position.

more |
pdf
| html
None.

MathPaper:
A note on simultaneous representation problem for interval and circular-arc graphs. https://t.co/b6W1Bk9sSI

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 1229

Unqiue Words: 427

In this work, we show deep connections between Locality Sensitive Hashability
and submodular analysis. We show that the LSHablility of the most commonly
analyzed set similarities is in one-to-one correspondance with the
supermodularity of these similarities when taken with respect to the symmetric
difference of their arguments. We find that the supermodularity of equivalent
LSHable similarities can be dependent on the set encoding. While monotonicity
and supermodularity does not imply the metric condition necessary for
supermodularity, this condition is guaranteed for the more restricted class of
supermodular Hamming similarities that we introduce. We show moreover that LSH
preserving transformations are also supermodular-preserving, yielding a way to
generate families of similarities both LSHable and supermodular. Finally, we
show that even the more restricted family of cardinality-based supermodular
Hamming similarities presents promising aspects for the study of the link
between LSHability and supermodularity. We hope that the...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 8478

Unqiue Words: 1835

The packing chromatic number $\chi$ $\rho$ (G) of a graph G is the smallest
integer k such that its set of vertices V (G) can be partitioned into k
disjoint subsets V 1 ,. .. , V k , in such a way that every two distinct
vertices in V i are at distance greater than i in G for every i, 1 $\le$ i
$\le$ k. Recently, Balogh, Kostochka and Liu proved that $\chi$ $\rho$ is not
bounded in the class of subcubic graphs [Packing chromatic number of subcubic
graphs, Discrete Math. 341 (2018), 474483], thus answering a question
previously addressed in several papers. However, several subclasses of cubic or
subcubic graphs have bounded packing chromatic number. In this paper, we
determine the exact value of, or upper and lower bounds on, the packing
chromatic number of some classes of cubic graphs, namely circular ladders, and
so-called H-graphs and generalised H-graphs.

more |
pdf
| html
None.

ComputerPapers:
Packing colouring of some classes of cubic graphs. https://t.co/qWjKtdtN9f

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 11916

Unqiue Words: 1492

Consider a large network with unknown number of nodes. Some of these nodes
coordinate to perform tasks. The number of such coordination groups is also
unknown. The only information about the network available is that any two
coordinating groups share at least $t$ nodes. To complete a particular task in
a day, at least $p$ nodes of the corresponding coordinating group must get
different time slots out of the $r$ available slots per day. Is there a way of
estimating the number of days required such that every coordinating group gets
at least one day where it can complete the task? As it turns out, this problem
is a special case of \textit{partially} perfect hash functions for intersecting
families.

more |
pdf
| html
None.

ComputerPapers:
Partially perfect hash functions for intersecting families. https://t.co/tczEmtL2Y3

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 2855

Unqiue Words: 685

An oriented graph is a directed graph with no loops or digons. The second
out-neighbors of a vertex $u$ in an oriented graph are the vertices to which
there exist directed paths of length 2 from $u$, but are not out-neighbors of
$u$. The Second Neighborhood Conjecture, first stated by Seymour, asserts that
in every oriented graph, there is a vertex which has at least as many second
out-neighbors as out-neighbors. We prove that the conjecture is true for two
special classes of oriented graphs. We first show that any oriented graph whose
vertex set can be partitioned into an independent set and 2-degenerate graph
satisfies the conjecture. Fidler and Yuster ["Remarks on the second
neighborhood problem", Journal of Graph Theory, 55(3):208--220, 2007] showed
that the conjecture is true for graphs obtained by removing a matching from a
tournament. We improve this result by showing that for graphs that can be
obtained by removing a matching from a tournament and contain no sink, there
exist two vertices with as many second out-neighbors...

more |
pdf
| html
None.

MathPaper:
The Second Neighborhood Conjecture for some Special Classes of Graphs. https://t.co/pcp3bnYlNo

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 17666

Unqiue Words: 1686

New generalized cyclotomic binary sequences of period $p^2$ are proposed in
this paper, where $p$ is an odd prime. The sequences are almost balanced and
their linear complexity is determined. The result shows that the proposed
sequences have very large linear complexity if $p$ is a non-Wieferich prime.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 8250

Unqiue Words: 1513

This paper focuses on devising graph signal processing tools for the
treatment of data defined on the edges of a graph. We first show that
conventional tools from graph signal processing may not be suitable for the
analysis of such signals. More specifically, we discuss how the underlying
notion of a `smooth signal' inherited from (the typically considered variants
of) the graph Laplacian are not suitable when dealing with edge signals that
encode a notion of flow. To overcome this limitation we introduce a class of
filters based on the Edge-Laplacian, a special case of the Hodge-Laplacian for
simplicial complexes of order one. We demonstrate how this Edge-Laplacian leads
to low-pass filters that enforce (approximate) flow-conservation in the
processed signals. Moreover, we show how these new filters can be combined with
more classical Laplacian-based processing methods on the line-graph. Finally,
we illustrate the developed tools by denoising synthetic traffic flows on the
London street network.

more |
pdf
| html
None.

SRoyLee:
Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space - https://t.co/4rDWJpAzIx

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 4849

Unqiue Words: 1691

Cryptocurrencies such as Bitcoin and Ethereum have recently gained a lot of
popularity, not only as a digital form of currency but also as an investment
vehicle. Online marketplaces and exchanges allow users across the world to
convert between dozens of different cryptocurrencies and regular currencies
such as euros or dollars. Due to the novelty of this concept, the volatility of
these markets and the differences in maturity and usage of particular
marketplaces, currency pairs may appear at multiple marketplaces but at
different trading prices. This paper proposes a novel algorithmic approach to
take advantage of these mispricings and capitalize upon the pricing differences
that exist between exchanges and currency pairs. To do so, we model each
combination of a currency and a market as one node in a graph. A directed link
between two nodes indicates that a conversion between these two currency/market
pairs is possible. The weight of the link relates to the exchange rate of
executing this particular currency exchange. To leverage...

more |
pdf
| html
ComputerPapers:
Computing Minimum Weight Cycles to Leverage Mispricings in Cryptocurrency Market Networks. https://t.co/VtMjETFBZ3

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 6705

Unqiue Words: 1745

We study the weighted induced bipartite subgraph problem (WIBSP). The goal of
WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W
of nodes with the maximum total weight such that a subgraph induced by W is
bipartite. WIBSP is also referred as to the graph bipartization problem or the
odd cycle transversal problem. In this paper, we show that WIBSP can be reduced
to the weighted independent set problem (WISP) where the number of nodes
becomes twice and the maximum degree increase by 1. WISP is a well-studied
combinatorial optimization problem. Thus, by using the reduction and results
about WISP, we can obtain nontrivial approximation and exact algorithms for
WIBSP.

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 1665

Unqiue Words: 571

Constructing a discretization of a given set is a major problem in various
theoretical and applied disciplines. An offset discretization of a set $X$ is
obtained by taking the integer points inside a closed neighborhood of $X$ of a
certain radius. In this note we determine a minimum threshold for the offset
radius, beyond which the discretization of a disconnected set is always
connected. The results hold for a broad class of disconnected and unbounded
subsets of $R^n$, and generalize several previous results. Algorithmic aspects
and possible applications are briefly discussed.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 4414

Unqiue Words: 1398

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 57,756 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible