Top 10 Arxiv Papers Today in Discrete Mathematics


0.0 Mikeys
#1. A note on simultaneous representation problem for interval and circular-arc graphs
Jan Bok, Nikola Jedličková
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
Figures
None.
Tweets
MathPaper: A note on simultaneous representation problem for interval and circular-arc graphs. https://t.co/b6W1Bk9sSI
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1229
Unqiue Words: 427

0.0 Mikeys
#2. Supermodular Locality Sensitive Hashes
Maxim Berman, Matthew B. Blaschko
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8478
Unqiue Words: 1835

0.0 Mikeys
#3. Packing colouring of some classes of cubic graphs
Eric Sopena, Daouya Laïche
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
Figures
None.
Tweets
ComputerPapers: Packing colouring of some classes of cubic graphs. https://t.co/qWjKtdtN9f
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11916
Unqiue Words: 1492

0.0 Mikeys
#4. Partially perfect hash functions for intersecting families
Tapas Kumar Mishra
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
Figures
None.
Tweets
ComputerPapers: Partially perfect hash functions for intersecting families. https://t.co/tczEmtL2Y3
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 2855
Unqiue Words: 685

0.0 Mikeys
#5. The Second Neighborhood Conjecture for some Special Classes of Graphs
Suresh Dara, Mathew C. Francis, Dalu Jacob, N. Narayanan
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
Figures
None.
Tweets
MathPaper: The Second Neighborhood Conjecture for some Special Classes of Graphs. https://t.co/pcp3bnYlNo
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 17666
Unqiue Words: 1686

0.0 Mikeys
#6. Corrigendum to New Generalized Cyclotomic Binary Sequences of Period $p^2$
Zibi Xiao, Xiangyong Zeng, Chunlei Li, Tor Helleseth
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 8250
Unqiue Words: 1513

0.0 Mikeys
#7. Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
Michael T. Schaub, Santiago Segarra
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
Figures
None.
Tweets
SRoyLee: Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space - https://t.co/4rDWJpAzIx
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 4849
Unqiue Words: 1691

0.0 Mikeys
#8. Computing Minimum Weight Cycles to Leverage Mispricings in Cryptocurrency Market Networks
Francesco Bortolussi, Zeger Hoogeboom, Frank W. Takes
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
Figures
Tweets
ComputerPapers: Computing Minimum Weight Cycles to Leverage Mispricings in Cryptocurrency Market Networks. https://t.co/VtMjETFBZ3
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 6705
Unqiue Words: 1745

0.0 Mikeys
#9. On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem
Yotaro Takazawa, Shinji Mizuno
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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1665
Unqiue Words: 571

0.0 Mikeys
#10. Optimal conditions for connectedness of discretized sets
Boris Brimkov, Valentin E. Brimkov
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 4414
Unqiue Words: 1398

About

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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 57,756 papers.