Top 10 Arxiv Papers Today in Combinatorics


2.061 Mikeys
#1. Separating many words by counting occurrences of factors
Aleksi Saarela
For a given language $L$, we study the languages $X$ such that for all distinct words $u, v \in L$, there exists a word $x \in X$ that appears a different number of times as a factor in $u$ and in $v$. In particular, we are interested in the following question: For which languages $L$ does there exist a finite language $X$ satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.
more | pdf | html
Figures
None.
Tweets
mathCObot: Aleksi Saarela : Separating many words by counting occurrences of factors https://t.co/vBLp7MQCyu https://t.co/hsVbEqaGb0
elcaborotativo: RT @mathCObot: Aleksi Saarela : Separating many words by counting occurrences of factors https://t.co/vBLp7MQCyu https://t.co/hsVbEqaGb0
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8196
Unqiue Words: 1576

2.061 Mikeys
#2. Brualdi's conjecture is true for group-based latin squares
Kevin Halasz
A near transversal of a latin square of order $n$ is a collection of $n-1$ cells which intersects each row, column, and symbol class at most once. A longstanding conjecture, commonly attributed to Brualdi, asserts that every latin square possesses a near transversal. We show that this conjecture is true for every latin square that is main class equivalent to the Cayley table of a finite group.
more | pdf | html
Figures
None.
Tweets
mathCObot: Kevin Halasz : Brualdi's conjecture is true for group-based latin squares https://t.co/g80YyliINi https://t.co/1ZYG1Xxev4
elcaborotativo: RT @mathCObot: Kevin Halasz : Brualdi's conjecture is true for group-based latin squares https://t.co/g80YyliINi https://t.co/1ZYG1Xxev4
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.061 Mikeys
#3. The covering lemma and $q$-analogues of extremal set theory problems
Dániel Gerbner
We prove a general lemma (inspired by a lemma of Holroyd and Talbot) about the connection of the largest cardinalities (or weight) of structures satisfying some hereditary property and substructures satisfying the same hereditary property. We use it to show how results concerning forbidden subposet problems in the Boolean poset imply analogous results in the poset of subspaces of a finite vector space. We also study generalized forbidden subposet problems in the poset of subspaces.
more | pdf | html
Figures
None.
Tweets
mathCObot: Dániel Gerbner : The covering lemma and $q$-analogues of extremal set theory problems https://t.co/nSUYuOMfuC https://t.co/h9MBSoI9hb
elcaborotativo: RT @mathCObot: Dániel Gerbner : The covering lemma and $q$-analogues of extremal set theory problems https://t.co/nSUYuOMfuC https://t.co/h…
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6603
Unqiue Words: 1509

2.061 Mikeys
#4. The worst way to collapse a simplex
Davide Lofano, Andrew Newman
In general a contractible complex need not be collapsible. Moreover, there exist complexes which are collapsible but even so admit a collapsing sequence where one "gets stuck", that is one can choose the collapses in such a way that one arrives at a nontrivial complex which admits no collapsing moves. Here we examine this phenomenon in the case of a simplex. In particular we characterize all values of $n$ and $d$ so that the $n$-simplex may collapse to a $d$-complex from which no further collapses are possible. Equivalently and in the language of high-dimensional generalizations of trees, we construct hypertrees that are anticollapsible, but not collapsible. Furthermore we examine anticollapsibility in random simplicial complexes.
more | pdf | html
Figures
Tweets
mathCObot: Davide Lofano, Andrew Newman : The worst way to collapse a simplex https://t.co/gVxHr7Dg2C https://t.co/6T74VKAVsM
elcaborotativo: RT @mathCObot: Davide Lofano, Andrew Newman : The worst way to collapse a simplex https://t.co/gVxHr7Dg2C https://t.co/6T74VKAVsM
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 12064
Unqiue Words: 2170

2.029 Mikeys
#5. Daisy cubes: a characterization and a generalization
Andrej Taranenko
Daisy cubes are a recently introduced class of isometric subgraphs of hypercubes $Q_n$. They are induced with intervals between chosen vertices of $Q_n$ and the vertex $0^n\in V(Q_n)$. In this paper we characterize daisy cubes in terms of an expansion procedure thus answering an open problem proposed by Klav\v{z}ar and Mollard, 2018, in the introductory paper of daisy cubes \cite{KlaMol-18}. To obtain such a characterization several interesting properties of daisy cubes are presented. For a given graph $G$ isomorphic to a daisy cube, but without the corresponding embedding into a hypercube, we present an algorithm which finds a proper embedding of $G$ into a hypercube in $O(mn)$ time. Finally, daisy graphs of a rooted graph are introduced and shown to be a generalization of daisy cubes.
more | pdf | html
Figures
None.
Tweets
mathCObot: Andrej Taranenko : Daisy cubes: a characterization and a generalization https://t.co/Cdd2Zfcogj https://t.co/pWJRrsZjkq
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.029 Mikeys
#6. $b$-invariant edges in cubic near-bipartite brick
Fuliang Lu, Xing Feng, Yan Wang
A brick is a non-bipartite graph without non-trivial tight cuts. Bricks are building blocks of matching covered graphs. We say that an edge $e$ in a brick $G$ is $b$-invariant if $G-e$ is matching covered and it contains exactly one brick. Kothari, Carvalho, Lucchesi, and Little shown that each essentially 4-edge-connected cubic non-near-bipartite brick $G$, distinct from Petersen graph, has at least $|V(G)|$ $b$-invariant edges. Moreover, they made a conjecture: every essentially 4-edge-connected cubic near-bipartite brick $G$, distinct from $K_4$, has at least $|V(G)|/2$ $b$-invariant edges. We confirm the conjecture in this paper. Furthermore, we characterized when equality holds.
more | pdf | html
Figures
None.
Tweets
mathCObot: Fuliang Lu, Xing Feng, Yan Wang : $b$-invariant edges in cubic near-bipartite brick https://t.co/3ExhEJJ4ol https://t.co/1qSBmdVFcl
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.029 Mikeys
#7. A gap in the slice rank of $3$-tensors
Simone Costa, Marco Dalai
It is proved that the asymptotic slice rank of any $3$-tensor in any field is either $1$ or at least $3/(2^{2/3})$. The motivation for this work comes from the study of possible applications of the slice rank method to the problem of bounding the size of trifferent sets of sequences, which constitutes a long-standing open problem in information theory and in theoretical computer science. Our results show that the straight-forward application cannot give improvements over known bounds.
more | pdf | html
Figures
None.
Tweets
mathCObot: Simone Costa, Marco Dalai : A gap in the slice rank of $3$-tensors https://t.co/rogzKzgMJT https://t.co/6hoVLplTeT
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.029 Mikeys
#8. Flexible Schemes
Yonah Biers-Ariel
We modify the enumeration schemes of Zeilberger and Vatter so that they can efficiently enumerate many new pattern-avoidance classes including all such classes with a regular insertion encoding. We also show an experimental condition which guarantees the absence of a finite enumeration scheme.
more | pdf | html
Figures
None.
Tweets
mathCObot: Yonah Biers-Ariel : Flexible Schemes https://t.co/SYZx4gYTQ1 https://t.co/dv1btbCrey
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.029 Mikeys
#9. Cometric Association Schemes
Brian G. Kodalen
One may think of a $d$-class association scheme as a $(d+1)$-dimensional matrix algebra over $\mathbb{R}$ closed under Schur products. In this context, an imprimitive scheme is one which admits a subalgebra of block matrices, also closed under the Schur product. Such systems of imprimitivity provide us with quotient schemes, smaller association schemes which are often easier to understand, providing useful information about the structure of the larger scheme. For any association scheme we find a basis of $d+1$ idempotent matrices for the algebra. A cometric scheme is one whose idempotent basis may be ordered $E_0,E_1,...,E_d$ with polynomials $f_0,f_1,...,f_d$ giving $f_i\circ(E_1)=E_i$ and deg$(f_i)=i$ for each $i$. Throughout this thesis we are primarily interested in three goals: building new examples of cometric schemes, drawing connections between cometric schemes and other objects, and finding new realizability conditions on feasible parameter sets --- using these conditions to rule out open parameter sets when possible....
more | pdf | html
Figures
Tweets
mathCObot: Brian G. Kodalen : Cometric Association Schemes https://t.co/nfydccufnf https://t.co/xMCnGoKfFO
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 63375
Unqiue Words: 7128

2.029 Mikeys
#10. Tiling Enumeration of Hexagons with Off-central Holes
Tri Lai
In the prequel of the paper (arXiv:1803.02792), we considered exact enumerations of the cored versions of a doubly-intruded hexagon. The result generalized Ciucu's work about $F$-cored hexagons (Adv. Math. 2017). In this paper, we provide an extensive list of 30 tiling enumerations of hexagons with three collinear chains of triangular holes with alternating orientations. Besides two chains of holes attaching to the boundary of the hexagon, we remove one more chain of triangles that is slightly off the center of the hexagon. Two of our enumerations imply two conjectures posed by Ciucu, Eisenk\"{o}lbl, Krattenthaler, and Zare (J. Combin. Theory Ser. A 2001) as two very special cases.
more | pdf | html
Figures
None.
Tweets
mathCObot: Tri Lai : Tiling Enumeration of Hexagons with Off-central Holes https://t.co/SGVnMr4Z4d https://t.co/OpeCsJ5qmI
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

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 128,326 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 128,326 papers.